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

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

作　　者：原晋江[1] 农庆琴[1] 

机构地区：[1]郑州大学数学系,郑州450001

出　　处：《郑州大学学报（理学版）》2006年第3期1-3,共3页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家自然科学基金资助项目,编号10371112;国家教委留学回国人员基金资助项目

摘　　要：讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,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.

关 键 词：排序 在线算法 平行批 最大完工时间 渐近最优 

分 类 号：O224[理学—运筹学与控制论]