Abstract
Motivated by the existence of an APTAS(Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number α such that p j = αs j for every 1 ≤ j ≤ n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS for it. Our basic idea is quite simple: we first enumerate all the partial schedules of relatively large jobs; Then for every partial schedule we insert the small jobs, split them if necessary; Further then, we choose the best of all the obtained schedules; Finally, we collect the split small jobs and put them into new batches. As we can round the large jobs into only a constant number of different kinds at a reasonable expense of accuracy, the running time can be bounded. When the optimal objective value of instances in our consideration can not be arbitrarily small, \(\inf \limits_{I}\{P_{\rm max}: P_{\rm max}\) is the largest processing time in I } ≠ 0 for instance, our result is perfect in the sense of worst-case performance.
Supported by NNSF of China(NO.10671108).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Azizoglu, M., Webster, S.: Scheduling a batch processing machine with non-identical job sizes. International Journal of Production Research 38(10) (2000)
Brucker, P., Gladky, A., Hoogeveen, H., Kovalyow, M.Y., Potts, C.N., Tautenhahn, T., van de Velde, S.L.: Scheduling a batching machine. Journal of Scheduling 1, 31–54 (1998)
Dupont, L., Dhaenens-Flipo, C.: Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Computer & Operations Research 29, 807–819 (2002)
Deng, X.T., Feng, H.D., Zhang, P.X., Zhang, Y.Z., Zhu, H.: Minimizing mean completion time in batch processing system. Algorithmica 38(4), 513–528 (2004)
Deng, X.T., Poon, C.K., Zhang, Y.Z.: Approximation Algorithms in batch scheduling. Journal of Combinational Optimization 7, 247–257 (2003)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling. Annals of Discrete Mathematics 5, 287–326 (1979)
Jolai, F., Ghazvini, Pupont, L.: Minimizing mean flow times criteria on a single batch processing machine with nonidentical job sizes. International Journal of Production Econonmics 55, 273–280 (1998)
Li, S.G., Li, G.J., Wang, X.L., Liu, Q.M.: Minimizing makespan on a single batching machine with release times and non-identical jog sizes. Operations Research Letters 33, 157–164 (2005)
Lenstra, J.K., Shmoys, D.R.: Computing near-optimal schedules. In: Chétienne, P., et al. (eds.) Scheduling theory and its applications, Wiley, New York (1995)
Potts, C.N., Lovalyov, M.Y.: Scheduling with batching: a review. European Journal of Operational Research 120, 228–249 (2000)
Uzsoy, R.: Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research 32(7), 1615–1635 (1994)
de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within in linear time. Combinatorica 1(4), 349–355 (1981)
Zhang, G.C., Cai, X.Q., Lee, C.Y., Wong, C.K.: Minimizing makespan on a single batch processing machine with non-identical job sizes. Naval Research Logistics 48, 226–247 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, Y., Cao, Z. (2007). An Asymptotic PTAS for Batch Scheduling with Nonidentical Job Sizes to Minimize Makespan. In: Dress, A., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2007. Lecture Notes in Computer Science, vol 4616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73556-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-73556-4_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73555-7
Online ISBN: 978-3-540-73556-4
eBook Packages: Computer ScienceComputer Science (R0)