Skip to main content
Log in

An iterative approach for the serial batching problem with parallel machines and job families

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Coffman, E. G., Nozari, A., & Yannakakis, M. (1989). Optimal scheduling of products with two subassemblies on a single machine. Operations Research, 37, 426–436.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449–467.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Laguna, M. (1999). A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times. IIE Transactions, 31, 125–134.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • Mehta, S. V., & Uzsoy, R. (1998). Minimizing total tardiness on a batch processing machine with incompatible job families. IIE Transactions, 30, 165–178.

    Google Scholar 

  • Mladenovic, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.

    Article  Google Scholar 

  • Monma, C., & Potts, C. (1989). On the complexity of scheduling with batch setups. Operations Research, 37, 798–804.

    Article  Google Scholar 

  • Mosheiov, G., Oron, D., & Ritov, Y. (2005). Minimizing flow-time on a single-machine with integer size batches. Operations Research Letters, 33, 497–501.

    Article  Google Scholar 

  • Naddef, D., & Santos, C. (1988). One-pass batching algorithms for the one-machine problem. Discrete Applied Mathematics, 21, 133–145.

    Article  Google Scholar 

  • Pinedo, M. (2008). Scheduling: theory, algorithms, and systems (3rd ed.). New York: Springer.

    Google Scholar 

  • Potts, C. N., & Kovalyov, M. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120, 228–249.

    Article  Google Scholar 

  • Rinnooy Kan, A. H. G. (1976). Machine scheduling problems: classification, complexity and computations. The Hague: Nijhoff.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • Santos, C. A., & Magazine, M. (1985). Batching in single operation manufacturing systems. Operations Research Letters, 4, 99–103.

    Article  Google Scholar 

  • Shallcross, D. (1992). A polynomial algorithm for a one machine batching problem. Operations Research Letters, 11, 213–218.

    Article  Google Scholar 

  • Wang, G., & Cheng, T. C. E. (2000). Parallel machine scheduling with batch delivery costs. International Journal of Production Economics, 68(2), 177–183.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous referees for their constructive comments and helpful suggestions.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Liji Shen.

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:

$$ \min\sum^n_{j=1}C_{j}. $$
(24)

Subject to:

(25)
(26)
(27)
(28)
(29)
(30)
(31)

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

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-013-1339-y

Keywords

Navigation