Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead. (English) Zbl 1237.68036

Summary: We consider online scheduling of unit length jobs on m parallel-batch machines with lookahead to minimize makespan. A parallel-batch machine can handle up to \(b\) jobs simultaneously as a batch with processing time equal to the maximum processing time of the jobs included in the batch. In the lookahead model, at a time instant \(t\), an online algorithm can foresee all the jobs that will arrive in the time segment \((t,t+\beta ]\). In this paper, we deal with two variants: the unbounded model with \(b=\infty \) and the bounded model with \(b<\infty \). For the unbounded model, we present an optimal online algorithm for \(\beta \geq 1/m\), and provide a best possible online algorithm of competitive ratio \(1+\alpha_m\) for \(0\leq \beta <1/m\), where \(\alpha_m\) is the positive root of \((1+\alpha)^{(m+1)} = \alpha + 2 - \beta\sum_{i=1} ^m (1+\alpha)^i\). For the bounded model, we establish a lower bound with a form of a piecewise function, and provide an online algorithm with competitive ratios \(1+\alpha ^{\ast}\) for \(0\leq\beta\leq\frac{1}{6}\) and \(\frac{3}{2}\) for \(\beta>\frac{1}{6}\), respectively, where \(\alpha^{\ast}\) is the positive root of \(\alpha ^{2}+(\beta +1)\alpha +\beta - 1=0\). The online algorithm is the best possible when \(0\leq\beta\leq\frac{1}{6}\).


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W27 Online algorithms; streaming algorithms
90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Avramidis, A. N.; Healy, K. J.; Uzsoy, R., Control of a batch-processing machine: a computational approach, International Journal of Production Research, 36, 3167-3181 (1998) · Zbl 0946.90510
[2] Deng, X. T.; Poon, C. K.; Zhang, Y. Z., Approximation algorithms in batch processing, Journal of Combinatorial Optimization, 7, 247-257 (2003) · Zbl 1053.90033
[3] P. Keskinocak, Online algorithms with lookahead: A survey, ISYE working paper, 1999.; P. Keskinocak, Online algorithms with lookahead: A survey, ISYE working paper, 1999.
[4] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Graves, S. C.; Zipkin, P. H.; Rinnooy Kan, A. H.G., Logistics of Production and Inventory. Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, vol. 4 (1993), North-Holland: North-Holland Amsterdam), 445-522 · Zbl 0798.90028
[5] Li, W. J.; Yuan, J. J.; Cao, J. F.; Bu, H. L., Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead, Theoretical Computer Science, 410, 5182-5187 (2009) · Zbl 1194.68089
[6] P.H. Liu, X.W. Lu, Y. Fang, A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines, Journal of Scheduling, doi:10.1007/s10951-009-0154-4; P.H. Liu, X.W. Lu, Y. Fang, A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines, Journal of Scheduling, doi:10.1007/s10951-009-0154-4 · Zbl 1280.68298
[7] Mao, W.; Kincaid, R. K., A look-ahead heuristic for scheduling jobs with release dates on a single machine, Computers and Operations Research, 21, 1041-1050 (1994) · Zbl 0812.90069
[8] Mandelbaum, M.; Shabtay, D., Scheduling unit length jobs on parallel machines with lookahead information, Journal of Scheduling, 14, 335-350 (2011) · Zbl 1229.90063
[9] Nong, Q. Q.; Cheng, T. C.E.; Ng, C. T., An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines, Operations Research Letters, 36, 584-588 (2008) · Zbl 1210.90094
[10] Poon, C. K.; Yu, W. C., On-line scheduling algorithms for a batch machine with finite capacity, Journal of Combinatorial Optimization, 9, 167-186 (2005) · Zbl 1079.90060
[11] Tian, J.; Fu, R. Y.; Yuan, J. J., A best online algorithm for scheduling on two parallel batch machines, Theoretical Computer Science, 410, 2291-2294 (2009) · Zbl 1166.90341
[12] Tian, J.; Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Online scheduling on unbounded parallel-batch machines to minimize the makespan, Information Processing Letters, 109, 1211-1215 (2009) · Zbl 1206.68072
[13] Uzsoy, R.; Lee, C. Y.; Martin-Vega, L. A., A review of production planning and scheduling models in the semiconductor industry, part I: System characteristics, performance evaluation and production planning, IIE Transactions on Scheduling and Logistics, 24, 47-61 (1992)
[14] Yuan, J. J.; Ng, C. T.; Cheng, T. C.E., Best semi-online algorithms for unbounded parallel batch scheduling, Discrete Applied Mathematics, 159, 838-847 (2011) · Zbl 1213.68714
[15] Zhang, G. C.; Cai, X. Q.; Wong, C. K., Online algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48, 241-258 (2001) · Zbl 1018.90017
[16] Zhang, G. C.; Cai, X. Q.; Wong, C. K., Optimal online algorithms for scheduling on parallel batch processing machines, IIE Transactions, 35, 175-181 (2003)
[17] Zheng, F. F.; Xu, Y. F.; Zhang, E., How much can lookahead help in online single machine scheduling, Information Processing Letters, 106, 70-74 (2008) · Zbl 1186.68079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.