Abstract
We consider the problem of scheduling n jobs on an unbounded batching machine that can process any number of jobs belonging to the same family simultaneously in the same batch. All jobs in the same batch complete at the same time. Jobs belonging to different families cannot be processed in the same batch, and setup times are required to switch between batches that process jobs from different families. For a fixed number of families m, we present a generic forward dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. We also present a polynomial-time backward dynamic programming algorithm with time complexity O (mn(n/m+1)m) for minimizing any additive regular minsum objective function and any incremental regular minmax objective function. The effectiveness of our dynamic programming algorithm is shown by computational experiments based on the scheduling of the heat-treating process in a steel manufacturing plant.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Brucker P, Gladky A, Hoogeveen H, Kovalyvov MY, Potts CN, Tautenhahn T and Van de Velde SL (1998). Scheduling a batching machine. J Sched 1: 31–54.
Chandru V, Lee CY and Uzsoy R (1993a). Minimizing total completion time on batch processing machines. Int J Prod Res 31: 2097–2122.
Chandru V, Lee CY and Uzsoy R (1993b). Minimizing total completion time on a batch processing machine with job families. Opns Res Lett 13: 61–65.
Hochbaum DS and Landy D (1997). Scheduling semiconductor burn-in operations to minimize total flowtime. Opns Res 45: 874–885.
Jolai F (2005). Minimizing number of tardy jobs on a batch processing machine with incompatible job families. Eur J Opl Res 162: 184–190.
Kashan AH and Karimi B (2008). Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: An ant colony framework. J Opl Res Soc 59: 1269–1280.
Lee CY, Uzsoy R and Martin-Vega LA (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Opns Res 40: 764–775.
Nong QQ, Ng CT and Cheng TCE (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Opns Res Lett 36: 61–66.
Petrovic D and Aköz O (2008). A fuzzy goal programming approach to integrated loading and scheduling of a batch processing machine. J Opl Res Soc 59: 1211–1219.
Sung CS and Rim HC (2004). Receiver set partitioning and sequencing for multicasting traffic in a WDM lightwave single-hop network. J Opl Res Soc 55: 630–639.
Uzsoy R (1995). Scheduling batch processing machines with incompatible job families. Int J Prod Res 33: 2685–2708.
Uzsoy R and Yang Y (1997). Minimizing total weighted completion time on a single batch processing machine. Prod Opns Manage 6: 57–73.
Yuan JJ, Liu ZH, Ng CT and 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.
Acknowledgements
The authors thank Professor Steef van de Velde for his advice on the first draft of this paper, and thank the anonymous referee for the valuable comments on improving an earlier version. This research was supported in part by projects of National Natural Science Foundation of China (No. 70832002 and No. 10971034).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zheng, R., Li, H. & Zhang, X. Scheduling an unbounded batching machine with family jobs and setup times. J Oper Res Soc 63, 160–167 (2012). https://doi.org/10.1057/jors.2010.187
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.187