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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/656345
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact