Motivated by heat treatment in metalworking, this study investigates a new scheduling problem involving a single batch-processing machine (industrial oven) with limited capacity, where jobs are semi-finished products to be treated. The non-identical jobs must be partitioned into batches for simultaneous processing, minimizing the overall makespan. All jobs in a batch start and end their processing together, with the processing time of the batch being determined by the longest job. Moreover, jobs are grouped into compatible families, each with a specific minimum processing temperature. Within a batch, the dominant family is the one with the highest temperature requirement. An innovative aspect of our work is the inclusion of sequence-dependent setup times between consecutive batches, determined by the dominant families of each batch. Following Graham et al. (1979) classification, we address the 1 | s_j , p − batch, SU_k^{fg} | Cmax problem. We call it the Single Batch-Processing Machine problem with Non-identical job sizes, Compatible families, and Sequence-dependent setup times. We develop two mixed-integer linear programming models for the problem, and enforce them with different valid inequalities and lower bounds on both the number of non-empty batches and the makespan. The first model extends the mathematical formulations of the problem proposed by Melouk et al. (2004) and Trindade et al. (2018), incorporating new constraints to capture family dominance and family sequence-dependent setup times. The second adopts a different set of decision variables, providing an alternative representation of the scheduling decisions. Computational experiments validate the effectiveness of both formulations and provide a performance comparison between them.
Formulations For Single Batch-Processing With Non-Identical Jobs, Compatible Families, And Sequence-Dependent Setups
Annalisa Castelletti
;Renata Mansini;Lorenzo Moreschini
2025-01-01
Abstract
Motivated by heat treatment in metalworking, this study investigates a new scheduling problem involving a single batch-processing machine (industrial oven) with limited capacity, where jobs are semi-finished products to be treated. The non-identical jobs must be partitioned into batches for simultaneous processing, minimizing the overall makespan. All jobs in a batch start and end their processing together, with the processing time of the batch being determined by the longest job. Moreover, jobs are grouped into compatible families, each with a specific minimum processing temperature. Within a batch, the dominant family is the one with the highest temperature requirement. An innovative aspect of our work is the inclusion of sequence-dependent setup times between consecutive batches, determined by the dominant families of each batch. Following Graham et al. (1979) classification, we address the 1 | s_j , p − batch, SU_k^{fg} | Cmax problem. We call it the Single Batch-Processing Machine problem with Non-identical job sizes, Compatible families, and Sequence-dependent setup times. We develop two mixed-integer linear programming models for the problem, and enforce them with different valid inequalities and lower bounds on both the number of non-empty batches and the makespan. The first model extends the mathematical formulations of the problem proposed by Melouk et al. (2004) and Trindade et al. (2018), incorporating new constraints to capture family dominance and family sequence-dependent setup times. The second adopts a different set of decision variables, providing an alternative representation of the scheduling decisions. Computational experiments validate the effectiveness of both formulations and provide a performance comparison between them.| File | Dimensione | Formato | |
|---|---|---|---|
|
ODS25_AbstractBook.pdf
accesso aperto
Descrizione: Book of Abstract
Tipologia:
Abstract
Licenza:
Non specificato
Dimensione
1.55 MB
Formato
Adobe PDF
|
1.55 MB | Adobe PDF | Visualizza/Apri |
|
ODS25_Abstract.pdf
accesso aperto
Descrizione: Abstract
Tipologia:
Abstract
Licenza:
Non specificato
Dimensione
84.57 kB
Formato
Adobe PDF
|
84.57 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


