Optimal online-list batch scheduling. (English) Zbl 1206.68374
Summary: We consider the online-list batch scheduling problem. Jobs arrive one by one and have to be assigned upon arrival to a scheduled batch such that the makespan is minimized. Each batch can accommodate up to \(B\) jobs. We give a complete classification of the tractability of this online problem.
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Baeza-Yates, R. A.; Culberson, J. C.; Rawlins, G. J.E., Searching in the plane, Information and Computation, 106, 2, 234-252 (1993) · Zbl 0781.68044 |
| [2] | Bein, W. W.; Epstein, L.; Larmore, L. L.; Noga, J., Optimally competitive list batching, (Algorithm Theory - SWAT2004. Algorithm Theory - SWAT2004, Lecture Notes in Computer Science, vol. 3111 (2004)), 77-89 · Zbl 1095.90546 |
| [3] | Brucker, P., Scheduling Algorithms (2004), Springer-Verlag · Zbl 1060.90034 |
| [4] | Chrobak, M.; Kenyon, C., Competitiveness via doubling, SIGACT News, 37, 4, 115-126 (2006) |
| [5] | Chrobak, M.; Kenyon, C.; Noga, J.; Young, N. E., Incremental medians via online bidding, Algorithmica, 50, 4, 455-478 (2008) · Zbl 1216.90057 |
| [6] | Deng, X.; Poon, C. K.; Zhang, Y., Approximation algorithms in batch processing, Journal of Combinatorial Optimization, 7, 3, 247-257 (2003) · Zbl 1053.90033 |
| [7] | Lee, C. Y.; Uzsoy, R., Minimizing makespan on a single batch processing machine with dynamic job arrivals, International Journal on Production Research, 37, 1, 219-236 (1999) · Zbl 0939.90537 |
| [8] | Lee, C. Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, 4, 764-775 (1992) · Zbl 0759.90046 |
| [9] | Nong, Q.; Yuan, J.; Fu, R.; Lin, L.; Tian, J., The single-machine parallel-batch on-line scheduling problem with family jobs to minimize makespan, International Journal of Production Economics, 111, 2, 435-440 (2008) |
| [10] | Poon, C. K.; Yu, W., A flexible on-line scheduling algorithm for batch machine with infinite capacity, Annals of Operations Research, 133, 1, 175-181 (2005) · Zbl 1119.90021 |
| [11] | Poon, C. K.; Yu, W., On-line scheduling algorithms for a batch machine with finite capacity, Journal of Combinatorial Optimization, 9, 2, 167-186 (2005) · Zbl 1079.90060 |
| [12] | Zhang, G.; Cai, X.; Wong, C. K., On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48, 3, 241-258 (2001) · Zbl 1018.90017 |
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.
