Abstract
In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling.
Similar content being viewed by others
References
Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27, 219–239.
Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032.
Almeder, C., & Mönch, L. (2011). Metaheuristics for scheduling jobs with incompatible families on parallel batching machines. Journal of the Operational Research Society, 62(12), 2083–2096.
Buscher, U., & Shen, L. (2009). An integrated tabu search algorithm for the lot streaming problem in job shops. European Journal of Operational Research, 199, 395–399.
Cheng, T. C. E., Chen, Z.-L., Kovalyov, M. Y., & Lin, B. M. T. (1996). Parallel-machine batching and scheduling to minimize total completion time. IIE Transactions, 28, 953–956.
Coffman, E. G., Nozari, A., & Yannakakis, M. (1989). Optimal scheduling of products with two subassemblies on a single machine. Operations Research, 37, 426–436.
Crauwels, H. A. J., Potts, C. N., & Van Wassenhove, L. N. (1996). Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs. European Journal of Operational Research, 90, 200–213.
Crauwels, H. A. J., Potts, C. N., & Van Wassenhove, L. N. (1997). Local search heuristics for single-machine scheduling with batch set-up times to minimize total weighted completion time. Annals of Operations Research, 70, 261–279.
Driessel, R., & Mönch, L. (2011). Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times. Computers & Industrial Engineering, 61(2), 336–345.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic machine scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.
Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449–467.
Jin, F., Song, S., & Wu, C. (2009). A simulated annealing algorithm for single machine scheduling problems with family setups. Computers & Operations Research, 36, 2133–2138.
Laguna, M. (1999). A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times. IIE Transactions, 31, 125–134.
Luu, D. T., Bohez, E. L. J., & Techanitisawad, A. (2002). A hybrid genetic algorithm for the batch sequencing problem on identical parallel machines. Production Planning & Control, 13(3), 243–252.
Mehta, S. V., & Uzsoy, R. (1998). Minimizing total tardiness on a batch processing machine with incompatible job families. IIE Transactions, 30, 165–178.
Mladenovic, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.
Monma, C., & Potts, C. (1989). On the complexity of scheduling with batch setups. Operations Research, 37, 798–804.
Mosheiov, G., Oron, D., & Ritov, Y. (2005). Minimizing flow-time on a single-machine with integer size batches. Operations Research Letters, 33, 497–501.
Naddef, D., & Santos, C. (1988). One-pass batching algorithms for the one-machine problem. Discrete Applied Mathematics, 21, 133–145.
Pinedo, M. (2008). Scheduling: theory, algorithms, and systems (3rd ed.). New York: Springer.
Potts, C. N., & Kovalyov, M. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120, 228–249.
Rinnooy Kan, A. H. G. (1976). Machine scheduling problems: classification, complexity and computations. The Hague: Nijhoff.
Rocha, M. L., Ravetti, M. G., Mateus, G. R., & Pardalos, P. M. (2007). Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighbourhood search. IMA Journal of Management Mathematics, 18, 101–115.
Santos, C. A., & Magazine, M. (1985). Batching in single operation manufacturing systems. Operations Research Letters, 4, 99–103.
Shallcross, D. (1992). A polynomial algorithm for a one machine batching problem. Operations Research Letters, 11, 213–218.
Wang, G., & Cheng, T. C. E. (2000). Parallel machine scheduling with batch delivery costs. International Journal of Production Economics, 68(2), 177–183.
Wang, X., & Tang, L. (2009). A population-based variable neighborhood search for the single machine total weighted tardiness problem. Computers & Operations Research, 36(6), 2105–2110.
Acknowledgements
The authors would like to thank the anonymous referees for their constructive comments and helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Here we present an alternative MIP formulation which is linear.
Additional notations
- \(\tilde{B}\) :
-
maximum number of batches on each machine
- C j :
-
completion time of job j
- t bk :
-
start time of batch b on machine k
- α bfk :
-
binary variable, equals 1 if batch b on machine k belongs to family f
- β jf :
-
parameter, equals 1 if job j belongs to family f and 0 otherwise
- δ jbk :
-
binary variable, equals 1 if job j is assigned to batch b on machine k
Objective:
Subject to:
Constraints (25) ensure that each job is grouped into one and only one batch, while constraints (26) indicate that the first batch on each machine is not empty.
Constraints (27) ensure that a batch contains jobs of the same family. They are relevant when jobs i and j belong to different families, and job j is assigned to batch b on machine k. In this case, the right side of the inequality equals 0 forcing the binary variable δ ibk taking the value of 0. Consequently, jobs of different families cannot be included in the same batch.
Constraints (28) then determine to which family a batch belongs. Similar to (27), α bfk equals 1 if job j is grouped into batch b on machine k and belongs to family f, that is, δ jbk =β jf =1. In the other cases, α bfk takes the value 0 as a result of the minimization objective.
Constraints (29) and (30) are then incorporated to determine batch sequences regarding setup times. It should be pointed out that batches are ordered according to their indices. Thus, the initial setup time is incurred before processing the first batch. Due to the triangular inequality, this can be generalized as written in (29), where the corresponding initial setup s 0f is included if this batch indeed belongs to family f ((1−α bfk )M=0).
According to constraints (30), the start time of a following batch c on machine k is determined by the completion time of its previous batch b on the same machine and the corresponding setups. Here, batches on each machine are ordered in terms of their indices. Since batch compositions can be inconsistent on machines (δ jbk ≠δ jbk′), a batch here is merely a symbol containing certain jobs. Thus, the predetermination of batch sequences does not restrict the flexibility of the formulation.
Based on the term −(3−δ jbk −α bfk −α cgk )M, constraints (30) are only relevant when batch b on machine k is not empty (δ jbk =1), and batches b and c belong to families f and g (α bfk =α cgk =1), respectively. Using this term thus serves the following purpose: First, empty batches are generally not to be considered. Moreover, it ensures that the associated p f and s fg are correctly identified in these constraints. As a result, t ck is determined by the start time of its previous batch (t bk ) and the aggregate processing time of jobs (\(\sum^{n}_{i=1}\delta_{ibk}\) indicates the number of jobs grouped into batch b, which is then multiplied by the corresponding processing time p f ). Setup times s fg are included in (30) as well, where batch b is a subset of family f and batch c belongs to family g.
According to constraints (31), the completion time of each job is determined by the start time of the batch to which it belongs, adding its processing time. Again, these constraints are only binding when the batch considered, in fact, contains the associated job j and belongs to family f, in which case δ jbk =α bfk =1 and (2−δ jbk −α bfk )M=0 hold.
In summary, the evaluation of this model is as follows:
-
Total number of variables: \({\tilde{B}}mn+{\tilde{B}}Fm+{\tilde{B}}m+n\)
-
Total number of constraints:
\(\frac{1}{2}{\tilde{B}}^{2}F^{2}mn-\frac{1}{2}{\tilde{B}}F^{2}mn+ \frac{1}{2}{\tilde{B}}Fmn^{2}+\frac{3}{2}{\tilde{B}}Fmn+{\tilde{B}}Fm+m+n\)
-
Total number of nonzeros:
\(\frac{1}{2}{\tilde{B}}^{2}F^{2}mn^{2}-\frac{1}{2}{\tilde{B}}F^{2}mn^{2}+2{\tilde{B}}^{2} F^{2}mn-2{\tilde{B}}F^{2}mn+2{\tilde{B}}Fmn^{2}+4{\tilde{B}}Fmn+2{\tilde{B}}Fm+{\tilde{B}}n+2mn\).
Rights and permissions
About this article
Cite this article
Shen, L., Mönch, L. & Buscher, U. An iterative approach for the serial batching problem with parallel machines and job families. Ann Oper Res 206, 425–448 (2013). https://doi.org/10.1007/s10479-013-1339-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-013-1339-y