Restarts Can Help in the On-Line Minimization of the Maximum Delivery Time on a Single Machine
Restarts Can Help in the On-Line Minimization of the Maximum Delivery Time on a Single Machine
复制标题
DOI：
10.1007/3-540-45253-2_39
复制
发表时间：
2000-09
期刊：
影响因子：
--
通讯作者：
M. Akker;H. Hoogeveen;N. Vakhania
中科院分区：
文献类型：
--
作者：
M. Akker;H. Hoogeveen;N. Vakhania
我们考虑一个单机在线调度问题，工件随时间到达。必须在一台机器上调度一组独立的作业。每项工作在其发布日期时可用，而发布日期事先并不知道，其特征，即加工要求和交付时间，在其到达时就知道了。目标是最小化所有工作交付的时间。在我们的模型中，抢占是不允许的，但我们可以重新启动一个作业，也就是说，一个作业的处理可以中断，让机器可以处理一个紧急的作业，但已经花在处理这个中断的作业上的时间被认为是损失的。我们提出了一个在线算法，并表明其性能界等于1.5，这与Vestjens的已知下界相匹配。对于没有重启的相同问题，已知最佳最坏情况下的边界等于（\sqrt{5}+1）/2 \thickapprox 1.61803;这是第一个例子，其中应用重启的可能性降低了最坏情况下的性能边界，即使处理时间已知。版权所有© 2000约翰威利父子有限公司。
We consider a single‐machine on‐line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on a single machine. 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. In our model preemption is not allowed, but we are allowed to restart a job, that is, the processing of a job can be broken off to have the machine available to process an urgent job, but the time already spent on processing this interrupted job is considered to be lost. We propose an on‐line algorithm and show that its performance bound is equal to 1.5, which matches a known lower bound due to Vestjens. For the same problem without restarts the optimal worst‐case bound is known to be equal to (\sqrt{5}+1)/2 \thickapprox 1.61803; this is the first example of a situation in which the possibility of applying restarts reduces the worst‐case performance bound, even though the processing times are known. Copyright © 2000 John Wiley & Sons, Ltd.