平行批排序最小化最大完工时间在线算法的一个注记(英文)

A Note on an On-line Algorithmfor the Parallel-batching Scheduling to Mini mize Makespan

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5+1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1+α)r+αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.

Consider the on-line scheduling problem of jobs with release dates on a single parallel batching machine which can process infinite jobs at a time. The scheduling problem involves assigning all jobs to batches and determining the starting times of the resulted batches in such a way that the maximum completion time of the jobs （makespan） is minimized. In [G. Zhang,X. Cai and C. K. Wong,On line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics,48 （ 2001 ）, 241-258） ] and [ X. Deng, C. K. Poon and Y. Z. Zhang, Approximation algorithms in batch processing, Journal of Combinatorial Optimization, 7 （ 2003）, 247 257 ], the two groups of authors independently gave the same on-line algorithm with competitive ratio （√5＋1 ）/2 and proved that the on-line algorithm is the best possible. In their algorithms,a job （which has the maximum processing time in a batch） with release date r and processing time p will be delayed until time （1 ＋a）r＋ap if possible,where a= （√5 -1 ）/2. In this note, a modified on-line algorithm is derived for the same problem in which a job with processing time p will be delayed only until time ap if possible. It is shown that the modified on-line algorithm is still best possible,and is asymptotically optimal in a weakened version.