Abstract
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+φ)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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
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
Deng X, Poon CK, Zhang Y (2003) Approximation algorithms in batch processing. J Comb Optim 7:247–257
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
Lee CY, Uzsoy R, MartinVega LA (1992) Efficient algorithms for scheduling semiconductor burn-in operations. Oper Res 40:764–775
Liu Z, Yu W (2000) Scheduling one batch processor subject to job release dates. Discrete Appl Math 105:129–136
Poon CK, Yu W (2005) A flexible on-line scheduling algorithm for batch machine with infinite capacity. Ann Oper Res 133:175–181
Poon CK, Yu W (2005) On-line scheduling algorithms for a batch machine with finite capacity. J Comb Optim 9:167–186
Tian J, Fu R, Yuan J (2007) On-line scheduling with delivery time on a single batch machine. Theory Comput Sci 374:49–57
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
Zhang G, Cai X, Wong CK (2001) On-line algorithms for minimizing makespan on batch processing machines. Nav Res Logist 48:241–258
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fang, Y., Liu, P. & Lu, X. Optimal on-line algorithms for one batch machine with grouped processing times. J Comb Optim 22, 509–516 (2011). https://doi.org/10.1007/s10878-010-9298-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9298-6