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.
LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao
. On-line bounded-batching scheduling of unit-length jobs with two families[J]. Operations Research Transactions, 2019
, 23(4)
: 105
-110
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.009
[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.
