Abstract
We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J j , its processing time and delivery time are denoted by p j and q j , respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J j , q j ≤p j ; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J i and J j , p i >p j implies q i ≥q j . We provide an on-line algorithm with competitive ratio \((\sqrt{5}+1)/2\) for both problems, and the results are the best possible.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bartholdi JJ (1988) Unpublished result
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 XT, Poon CK, Zhang YZ (2003) Approximation algorithms in batch processing. J Comb Optim 7:247–257
Epstein L, Favrholdt LM, Kohrt JS (2006) Separating on-line scheduling algorithms with the relative worst order ratio. J Comb Optim 12:337–350
Graham RL, Lawer EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326
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 (1999) Minimizing makespan on a single batch processing machine with dynamic job arrivals. Int J Prod Res 37:219–236
Lee CY, Uzsoy R, Martin-Vega LA (1992) Efficient algorithms for scheduling semi-conductor burn-in operations. Oper Res 40:764–775
Liu ZH, Yu WC (2000) Scheduling one batch processor subject to job release dates. Discrete Appl Math 105:129–136
Poon CK, Yu WC (2005) On-line scheduling algorithms for a batch machine with finite capacity. J Comb Optim 9:167–186
Tian J, Fu RY, Yuan JJ (2007) On-line scheduling with delivery time on a single batch machine. Theor Comput Sci 374:49–57
Zhang GC, Cai XQ, 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
Additional information
Project supported by NSFC (10671183).
Rights and permissions
About this article
Cite this article
Yuan, J., Li, S., Tian, J. et al. A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times. J Comb Optim 17, 206–213 (2009). https://doi.org/10.1007/s10878-007-9108-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-007-9108-y