On-line scheduling of a single machine to minimize total weighted completion time
On-line scheduling of a single machine to minimize total weighted completion time
复制标题
DOI：
10.1287/moor.1040.0092
复制
发表时间：
2002-01
期刊：
影响因子：
--
通讯作者：
E. Anderson;C. Potts
中科院分区：
文献类型：
--
作者：
E. Anderson;C. Potts
本文考虑单机在线调度问题，其中作业随时间到达，并且不允许抢占。目标是使总加权完成时间最小化。我们表明，对最短加权加工时间规则的一个简单修改具有2的竞争比。这个结果是使用一种新的证明技术得到的，该技术没有明确依赖于最优目标函数值的下界。由于已知没有在线算法能具有小于2的竞争比，我们已经解决了确定此问题最小竞争比的开放问题。
This paper considers the on-line scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of 2. This result is established using a new proof technique which does not rely explicitly on a lower bound on the optimal objective function value. Since it is known that no on-line algorithm can have a competitive ratio of less than 2, we have resolved the open issue of determining the minimum competitive ratio for this problem.