已知总和的可中断半在线排序算法

Preemptive Semi-online Algorithm with Known Total Size

文章研究了平行机上的一个半在线排序问题.假定预先已知所有工件的加工时间总和,工件的加工可中断,目标是极大化最小的机器完工时间和极小化最大的机器完工时间.针对这两种目标情形,分别给出了竞争比为1的半在线算法,从而是最优的.

This paper considers preemptive semi-online scheduling problems,where the total processing time of all jobs is known in advance.The goal is to maximize the minimum machine completion time or to minimize the maximum machine completion time.For the two objectives,optimal semi-online algorithms with competitive ratio 1are present,respectively.