Optimal on-line algorithms for one batch machine with grouped processing times. (English) Zbl 1236.90052

Summary: In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in \([p, (1+\phi )p]\), where \(p>0\) and \(\phi=(\sqrt{5}-1)/2\). Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio \((\sqrt{5}+1)/2\) are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio \((\sqrt{5}+1)/2\). The two class of algorithms are optimal for the problems studied here.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Brucker P, Gladky A, Hoogeveen H, Kovalyov MY, Potts CN, Tautenhahn T, van de Velde SL (1998) Scheduling a batching machine. J Sched 1:31–54 · Zbl 0909.90172 · doi:10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R
[2] Deng X, Poon CK, Zhang Y (2003) Approximation algorithms in batch processing. J Comb Optim 7:247–257 · Zbl 1053.90033 · doi:10.1023/A:1027316504440
[3] Hoogeveen JA, Vestjens APA (2000) A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. SIAM J Discrete Math 13:56–63 · Zbl 0944.90020 · doi:10.1137/S0895480196296823
[4] Lee CY, Uzsoy R, MartinVega LA (1992) Efficient algorithms for scheduling semiconductor burn-in operations. Oper Res 40:764–775 · Zbl 0759.90046 · doi:10.1287/opre.40.4.764
[5] Liu Z, Yu W (2000) Scheduling one batch processor subject to job release dates. Discrete Appl Math 105:129–136 · Zbl 0969.90046 · doi:10.1016/S0166-218X(00)00181-5
[6] Poon CK, Yu W (2005) A flexible on-line scheduling algorithm for batch machine with infinite capacity. Ann Oper Res 133:175–181 · Zbl 1119.90021 · doi:10.1007/s10479-004-5031-0
[7] Poon CK, Yu W (2005) On-line scheduling algorithms for a batch machine with finite capacity. J Comb Optim 9:167–186 · Zbl 1079.90060 · doi:10.1007/s10878-005-6855-5
[8] Tian J, Fu R, Yuan J (2007) On-line scheduling with delivery time on a single batch machine. Theory Comput Sci 374:49–57 · Zbl 1162.90405 · doi:10.1016/j.tcs.2006.12.001
[9] Yuan J, Li S, Tian J, Fu R (2009) A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times. J Comb Optim 17:206–213 · Zbl 1170.90401 · doi:10.1007/s10878-007-9108-y
[10] Zhang G, Cai X, Wong CK (2001) On-line algorithms for minimizing makespan on batch processing machines. Nav Res Logist 48:241–258 · Zbl 1018.90017 · doi:10.1002/nav.5
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.