Abstract
We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than \(1+(\sqrt{m^{2}+4}-m)/2\) , where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.
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., Kovalyvov, M. Y., Potts, C. N., Tautehahn, T., & Velde, S. L. (1998). Scheduling a batching machine. Journal of Scheduling, 1, 31–54.
Chen, B., Deng, X., & Zang, W. (2001). On-line scheduling a batch processing system to minimize total weighted job completion time. In Lecture notes in computer science (Vol. 2223, pp. 380–389). Berlin: Springer.
Cheng, T. C. E., Ng, C. T., Yuan, J. J., & Liu, Z. H. (2004). Single machine parallel batch scheduling subject to precedence constraints. Naval Research Logistics, 51, 949–958.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals Discrete Mathematics, 5, 287–326.
Lee, C. Y., & Uzsoy, R. (1999). Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research, 37, 219–236.
Lee, C. Y., Uzsoy, R., & Martin Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40, 764–775.
Li, S., Li, G., Wang, X., & Liu, Q. (2005). Minimizing makespan on a single batching machine with release times and non-identical job sizes. Operations Research Letters, 33, 157–164.
Liu, Z., & Yu, W. (2000). Scheduling one batch processor subject to job release dates. Discrete Applied Mathematics, 105, 129–136.
Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2002). A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints. Operations Research Letters, 30, 66–68.
Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2003). The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard. Journal of Scheduling, 6, 483–490.
Nong, Q. Q., Cheng, T. C. E., & Ng, C. T. (2008). An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines. Operations Research Letters, 36, 584–588.
Tian, J., Fu, R., & Yuan, J. (2009). A best online algorithm for scheduling on two parallel batch machines. Theoretical Computer Science, 410, 2291–2294.
Uzsoy, R. (1994). A single batch processing machine with non-identical job sizes. International Journal of Production Research, 32, 1615–1635.
Yuan, J. J., Liu, Z. H., Ng, C. T., & Cheng, T. C. E. (2004). The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. Theoretical Computer Science, 320, 199–212.
Zhang, G., Cai, X., & Wong, C. K. (2001). On-line algorithms for minimizing makespan on batch processing machines. Naval Research Logistics, 48, 241–258.
Zhang, G., Cai, X., & Wong, C. K. (2003). Optimal on-line algorithms for scheduling on parallel batch processing machines. IIE Transactions, 35, 175–181.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, P., Lu, X. & Fang, Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines. J Sched 15, 77–81 (2012). https://doi.org/10.1007/s10951-009-0154-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-009-0154-4