An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times. (English) Zbl 1260.68042

Summary: We consider the on-line version of the single machine unbounded parallel-batching scheduling with delivery times of jobs. Each job’s information, such as processing time \(p_j\) and delivery time \(q_j\), is not known in advance and becomes known at its arrival time. Once the processing of a job is completed, we deliver it to the destination. Here, the time is continuous. The objective is to minimize the time by which all jobs have been delivered. In this paper, we consider job system with large delivery times, i.e., \(q_j\geq p_j\), for each job \(J_j\). We provide an on-line algorithm with a competitive ratio \((\sqrt{5}+1)/2\approx 1.618\) and show that any on-line algorithm has a competitive ratio of at least \((\sqrt{3}+1)/2\approx 1.366\).


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W27 Online algorithms; streaming algorithms
Full Text: DOI


[1] 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
[2] Fang, Y.; Liu, P. H.; Lu, X. W., Optimal on-line algorithms for one batch machine with grouped processing times, Journal of Combinatorial Optimization · Zbl 1236.90052
[3] Hoogeveen, J. A.; Vestjens, A. P.A., A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine, SIAM Journal of Discrete Math., 13, 56-63 (2000) · Zbl 0944.90020
[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 Operation Research Management Science, vol. 4 (1993), North-Holland: North-Holland Amsterdam), 445-522 · Zbl 0798.90028
[5] Lee, C. Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semi-conductor burn-in operations, Operations Research, 40, 764-775 (1992) · Zbl 0759.90046
[6] Lee, C. Y.; Uzsoy, R., Minimizing makespan on a single batch processing machine with dynamic job arrivals, International Journal of Production Research, 37, 219-236 (1999) · Zbl 0939.90537
[7] Liu, P. H.; Lu, X. W., A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines, Journal of Scheduling · Zbl 1280.68298
[8] 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
[9] Tian, J.; Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Online scheduling on unbounded parallel-batch machines to minimize makespan, Information Processing Letters, 109, 1211-1215 (2009) · Zbl 1206.68072
[10] Tian, J.; Fu, R. Y.; Yuan, J. J., On-line scheduling with delivery time on a single batch machine, Theoretical Computer Science, 374, 49-57 (2007) · Zbl 1162.90405
[11] Uzsoy, R.; Lee, C. Y.; Martin-Vega, L. A., A survey of production planning and scheduling models in the semiconductor industry, part II: Shop-floor control, IIE Transaction on Scheduling and Logistics, 26, 44-55 (1994)
[12] Yuan, J. J.; Li, S. S.; Tian, J.; Fu, R. Y., A best on-line algorithm for the single machine parallel batch scheduling with restricted delivery times, Journal of Combinatorial Optimization, 17, 206-213 (2009) · Zbl 1170.90401
[13] Zhang, G. C.; Cai, X. Q.; Wong, C. K., On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48, 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.