论文部分内容阅读
本文研究的是带服务器的平行机排序问题，它是经典平行机排序问题的一个推广，其中每个工件在由机器加工之前都必须由一个服务器安装在一台机器上，而一个服务器在同一时间只能安装一个工件。本文主要研究了带一个服务器的两台平行机排序问题，对以下两种情况设计了近似算法并分析了其性能比。
(1)对安装时间均为1的P2,S1｜Si=1｜Cmax问题，我们首先将其变换为经典的平行机排序问题P2‖Cmax，并用LPT算法得到其排序，而后利用此排序的工件集合构造P2，S1｜si=1｜Cmax问题的排序。对此算法证明了其性能比为7/6。
(2)对加工时间是常数的P2，S1｜Pi=p｜Cmax问题，分别研究离线和在线情况的近似算法，证明了离线情况时近似算法的性能比为7/6，在线情况时LS算法的性能比为3/2。