【摘要】 该文首先指出Kellerer[2](1997)关于带缓冲区的两台平行机半在线排序问题竞争比为4/3最优算法证明中一个不够严密的环节,并给予修正。然后将情况推广到三台平行机,给出了竞争比为3/2的近似算法,并给出了一个15/11的下界。更多还原

【Abstract】 In this paper we first point out a flaw in the proof of the 4/3 competitive ratio of the approximation algorithm for two parallel machine scheduling with a buffer and give a revision. Then we extend to consider the three parallel machines scheduling problem with a buffer and a approximation algorithm with 3/2 competitive ratio is proposed .At last,we provide a lower bound of this version as 15/11.更多还原