On‐line algorithms for minimizing makespan on batch processing machines
On‐line algorithms for minimizing makespan on batch processing machines
复制标题
DOI：
10.1002/nav.5
复制
发表时间：
2001-04
期刊：
影响因子：
--
通讯作者：
Gouchuan Zhang;Xiaoqiang Cai;C. Wong
中科院分区：
文献类型：
--
作者：
Gouchuan Zhang;Xiaoqiang Cai;C. Wong
研究了工件到达时间为动态的批处理机上工件的在线调度问题，目标是最小化完工时间。一台批处理机最多可以同时处理B个作业。从批处理中一起处理的作业，以及批处理中的所有作业同时开始和完成。批处理的处理时间由批处理中任何作业的最长处理时间给出。每个作业在其到达时间变得可用，而该到达时间事先是未知的，并且其处理时间在其到达时变得已知。在本文的第一部分中，我们研究了单台批处理机的排序问题。首先，我们处理两个变种：无界模型，其中B是足够大的有界模型，其中工作有两个不同的到达时间。对于这两种变体，我们提供了最坏情况下的比率$（\sqrt{5}+1）/2$（黄金比例的倒数）的在线算法，并证明这些结果是最好的。此外，我们将我们的算法推广到一般情况，并显示最坏情况下的比率为2。然后，我们考虑无界的情况下，并行批处理机调度。给出了下界，并给出了两个在线算法. John Wiley & Sons，Inc.海军研究后勤48：241-258，2001年
We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio $(\sqrt{5}+1)/2$ (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001