【摘要】 讨论了一个可重排平行机半在线排序问题.设有两台同型平行机,加工速度相同,工件以列表在线方式依次到达,当且仅当当前工件安排后,下一个工件才到达,目标是使两台机器中的较小负荷最大化.进一步在所有工件预排完毕后,允许重排任意k个工件.提出竞争比为3/2的最优算法H,且该算法只需重排一个工件.更多还原

【Abstract】 This paper studies a semi-online machine covering problem with reassignment on two identical machines.Given two identical machines and a set of jobs,jobs come one by one over list.After all jobs are assigned,k already scheduled jobs can be reassigned from one machine to the another.The objective is to maximize the minimum load taken over all machines.An optimal algorithm with competitive ratio 3/2 is proposed.更多还原