Optimal On-Line Algorithms for Single-Machine Scheduling
Optimal On-Line Algorithms for Single-Machine Scheduling
复制标题
DOI：
10.1007/3-540-61310-2_30
复制
发表时间：
1996-06
期刊：
影响因子：
--
通讯作者：
H. Hoogeveen;Arjen P. A. Vestjens
中科院分区：
文献类型：
--
作者：
H. Hoogeveen;Arjen P. A. Vestjens
我们考虑单机在线调度问题，其中作业随时间到达。必须在机器上调度一组独立的作业，其中不允许抢占，并且作业的数量事先未知。每个作业在其发布日期可用，而发布日期是事先不知道的，其特征，例如加工要求，在其到达时就知道了。我们处理两个问题：最小化总完成时间和最小化所有工作交付的最大时间。针对这两个问题，我们提出并分析了一种基于以下思想的在线算法：一旦机器可以进行加工，选择优先级最高的可用作业，如果其加工要求不是太大，则调度它。否则，推迟开始这项工作一段时间。我们证明了我们的算法的性能界分别为2和(√5 + 1)/2，并且我们证明了对于这两个问题不存在具有更好性能保证的在线算法。
We consider single-machine on-line scheduling problems where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, e.g., processing requirement, become known at its arrival. We deal with two problems: minimizing total completion time and minimizing the maximum time by which all jobs have been delivered. For both problems we propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job for a while. We prove that our algorithms have performance bound 2 and (√5 + 1)/2, respectively, and we show that for both problems there cannot exist an on-line algorithm with a better performance guarantee.