郑州大学学报（理学版）2006，Vol.38Issue(3)：1-3,3.
平行批排序最小化最大完工时间在线算法的一个注记
A Note on an On-line Algorithm for the Parallel-batching Scheduling to Minimize Makespan
摘要
Abstract
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.关键词
排序/在线算法/平行批/最大完工时间/渐近最优Key words
scheduling/on-line algorithm/parallel-batching/makespan/asymptotically optimal分类
数理科学引用本文复制引用
原晋江,农庆琴..平行批排序最小化最大完工时间在线算法的一个注记[J].郑州大学学报（理学版）,2006,38(3):1-3,3.基金项目
国家自然科学基金资助项目,编号10371112 （）
国家教委留学回国人员基金资助项目. （）
