A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
复制标题
DOI：
10.1137/s0895480196296823
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
H. Hoogeveen;Arjen P. A. Vestjens
中科院分区：
文献类型：
--
作者：
H. Hoogeveen;Arjen P. A. Vestjens
考虑工件到达时间随时间变化的单机在线排序问题。一组独立的工件必须在机器上调度，其中不允许抢占，工件的数量是事先未知的。每个作业在其发布日期变得可用，这是事先不知道的，其特征，即，处理要求和交货时间，在货物到达时就知道了。目标是最小化所有工作交付的时间。我们提出并分析了一个在线算法的基础上，以下的想法：一旦机器成为可用于处理，选择一个可用的作业具有最高的优先级，并调度它，如果它的处理要求不是太大。否则，请推迟此作业的开始。我们证明了我们的算法有性能界$（\sqrt{5}+1）/2 \approximat1.61803 $，我们表明，不可能存在一个确定性的在线算法具有更好的性能比这个问题。
We consider a single-machine on-line scheduling problem 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, i.e., processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. 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. We prove that our algorithm has performance bound $(\sqrt{5}+1)/2 \approx 1.61803$, and we show that there cannot exist a deterministic on-line algorithm with a better performance ratio for this problem.