Operations Research Transactions >
2016 , Vol. 20 >Issue 1: 84 - 90
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.01.008
Online batch scheduling with known information in advance
Received date: 2015-05-27
Online published: 2016-03-15
We study a single online batch scheduling problem with known information in advance. The information arrives over time and the objective is to minimize the maximum completion time. The time between the information arrival of a job and its release time is constant $a$. The maximum of the processing times of all jobs $p_{{\rm max}}$ is known in advance too. A batch processing machine can handle up to $b$ jobs simultaneously. The processing time of a batch is given by the longest processing time of all jobs in the batch. When $b=\infty$, we provide an optimal online algorithm $\gamma H^\infty$ with a competitive ratio of $1+\gamma$, where $\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$.
Key words： batch scheduling; competitive ratio; online algorithm
WANG Chengfei, ZHANG Yuzhong . Online batch scheduling with known information in advance[J]. Operations Research Transactions, 2016 , 20(1) : 84 -90 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.008
[1] Hall N G, Potts C N. Online scheduling with known arrival times [J]. Mathematics of Operations Research, 2009, 34(1): 92-102.
[2] Lee C Y, Uzsoy R. Minimizing makespan on a single batch processing machine with dynamic job arrivals [J]. International Journal of Production Research, 1999, 37(1): 219-236.
[3] Poon C K, Zhang P. Minimizing makespan in batch machine scheduling [J]. Algorithmica, 2004, 39(2): 155-174.
[4] Deng X, Poon C K, Zhang Y. Approximation algorithms in batch scheduling [J]. Journal of Combinatorial Optimization, 2003, 7: 247-257.
[5] Zhang G, Cai X, Wong C K. On-line algorithms for minimizing makespan on batch processing machines [J]. Naval Research Logistics, 2001, 48(3): 241-258.
[6] 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(21-22): 1211-1215.
[7] Liu P, Lu X, Fang Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines [J]. Journal of Scheduling, 2012, 15(1): 77-81.
[8] Kellerer H, Kotov V, Speranza M G, et al. Semi on-line algorithms for the partition problem [J]. Operations Research Letters, 1997, 21: 235-242.
[9] He Y, Zhang G. Semi on-line scheduling on two identical machines [J]. Computing, 1999, 62: 179-187.
[10] Tan Z, He Y. Semi-on-line problems on two identical machines with combined partial information [J]. Operations Research Letters, 2002, 30: 408-414.
[11] Yuan J, Ng C T, Cheng T C E. Best semi-online algorithms for unbounded parallel batch scheduling [J]. Discrete Applied Mathematics, 2011, 159(8): 838-847.
/
| 〈 |
|
〉 |
