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

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,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时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.

A Note on an On-line Algorithm for the Parallel-batching Scheduling to Minimize Makespan

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 determi ning 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, NavalResearch 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 +α)r+αp if possible, where α= ((√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 αp if possible. It is shown that the modified on-line algorithm is still best possible,and is asymptotically optimal in a weakened version.