研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达，目标是最小化最大完工时间.在有界平行分批排序中，容量有限制机器最多可将b个工件形成一批同时加工，每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.
We consider on-line scheduling on a parallel batching machine with two incompatible families of unit-length jobs, where the batch capacity is bounded. In this paper, online means that jobs arrive over time. The objective is to mininize the makespan. In bounded parallel batch scheduling, a finite capacity machine can process b jobs simultaneously as a batch, and the processing time of a batch is equal to 1. Incompatible job families mean that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio √17+3/4.
[1] Zhang G C, Cai X Q, Wong C K. On-line algorithms for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48:241-258.
[2] Zhang G C, Cai X Q, Wong C K. Optimal on-line algorithms for scheduling on parallel batch processing machines[J]. IIE Transactions, 2003, 35:175-181.
[3] Tian J, Cheng T C E, Ng C T, et al. Online scheduling on unbounded parallel-batch machines to minimize the makespan[J]. Information Processing Letters, 2009, 109:1211-1215.
[4] Deng X T, Poon C K, Zhang Y Z. Approximation algorithms in batch processing[J]. Journal of Combinatorial Optimization, 2003, 7:247-257.
[5] Nong Q Q, Yuan J J, Fu R Y, et al. The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan[J]. International Journal of Production Economics, 2008, 111:435-440.
[6] Li W J, Li S S, Feng Q. Online batch scheduling with kind release times and incompatible families to minimize makespan[J]. Optimization Letters, 2018, 12:301-310.
[7] Fu R Y, Tian J, Yuan J J. On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs[J]. Journal of Scheduling, 2009, 12:91-97.
[8] Fu R Y, Cheng T C E, Ng C T, et al. An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan[J]. Operations Research Letters, 2013, 41:216-219.
[9] 李文华, 柴幸, 袁航, 等. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19:121-126.
[10] Tian J, Fu R Y, Yuan J J. Online over time scheduling on parallel-batch machines:A survey[J]. Journal of the Operations Research Society of China, 2014, 2:445-454.
