Abstract
We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b<n, and in the unbounded model, b=∞. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time (makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time approximation schemes (PTAS).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Afrati F, Bampis E, Chekuri C, Karger D, Kenyon C, Khanna S, Milis I, Queyranne M, Skutella M, Stein C, Sviridenko M (1999) Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th annual IEEE symposium on foundations of computer science (New York). IEEE Comput Soc, Los Alamitos, pp 32–44
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
Brucker P (2001) Scheduling algorithms. Springer, Berlin
Brucker P, Knust S (2007) Complexity results for scheduling problem. http://www.mathematik.uniosnabrueck.de/reseach/OR/class/2007
Cheng TCE, Liu ZH, Yu WC (2001) Scheduling jobs with release dates and deadlines on a batching processing machine. IIE Trans 33:685–690
Deng XT, Poon CK, Zhang YZ (2003) Approximation algorithms in batch processing. J Comb Optim 7:247–257
Deng XT, Zhang YZ (1999) Minimizing mean response time for batch processing systems. Lect Notes Comput Sci 1627:231–240
Graham RL (1969) Bounds on multiprocessor timing anomalies. SIAM J Appl Math 17:416–429
Hall LA, Shmoys DB (1989) Approximation schemes of constrained scheduling problems. In: Proceedings of the 30th annual IEEE symposium on foundations of computer science, pp 134–139
Lee CY, Uzsoy R, Martin-Vega LA (1992) Efficient algorithms for scheduling semi-conductor burn-in operations. Oper Res 40:764–775
Lee CY, Uzsoy R (1999) Minimizing makespan on a single batch processing machine with dynamic job arrivals. Int J Prod Res 37:219–236
Li SG, Li GJ, Zhang SQ (2005) Minimizing makespan with release times on identical parallel batching machines. Discrete Appl Math 148:127–134
Liu ZH, Yu WC (2000) Scheduling one batch processor subject to job release dates. Discrete Appl Math 105:129–136
Liu ZH, Yuan JJ, Cheng TCE (2003) On scheduling an unbounded batch machine. Oper Res Lett 31:42–48
Nong QQ, Ng CT, Cheng TCE (2008) The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Oper Res Lett 111:435–440
Yuan JJ, Liu ZH, Ng CT, Cheng TCE (2004) The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. Theor Comput Sci 320:199–212
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by NSFC (10671183), NFSC-RGC (70731160633) and SRFDP (20070459002).
Rights and permissions
About this article
Cite this article
Li, S., Yuan, J. Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan. J Comb Optim 19, 84–93 (2010). https://doi.org/10.1007/s10878-008-9163-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-008-9163-z