The Single Batch-Processing Machine Scheduling Problem, with Non-identical Jobs, Compatible Families and Sequence-dependent Setups (SBPM-NCS), was recently introduced by Castelletti et al. (2025) as a challenging extension of the classical single-machine parallel-batching problem Uzsoy et al. (1994). Jobs can be processed simultaneously in batches, the processing time of each batch is determined by its longest job, and the objective is to minimize the makespan in presence of family compatibility constraints and sequence-dependent setup times. The mixed-integer linear formulation proposed in earlier work captures these features exactly, but becomes dicult to solve on medium- and large-size instances. To address this issue, we propose a column generation–based approach relying on an arc-ow formulation, building upon the frameworks of Druetto et al. (2023). Feasible solutions are represented as paths in a directed multigraph, where nodes encode both the position in the sequence and the dominant family of the current processed batch. Each arc corresponds to a feasible batch and is associated with a cost accounting for both batch processing times and sequence-dependent setup contributions. The formulation involves an exponential number of variables and is solved via a Restricted Master Problem, which is iteratively enriched through column generation. The pricing problem consists in identifying batches (columns) with negative reduced cost. We derive its structure and show that it can be reformulated, for xed positions, as a cardinality-constrained knapsack problem, where item prots are given by dual variables, while weights correspond to job sizes, and feasibility is enforced through capacity and cardinality constraints, together with family constraints. The resulting pricing problem is solved to optimality via a pseudo-polynomial dynamic programming algorithm. Preliminary computational results indicate an improvement in the initial lower bound and competitive solution quality within reasonable computational times.

A column generation approach for the Single Batch-Processing Machine Scheduling Problem, with Non-identical jobs, Compatible families and Sequence-dependent setups

Castelletti Annalisa
;
Mansini Renata;
2026-01-01

Abstract

The Single Batch-Processing Machine Scheduling Problem, with Non-identical Jobs, Compatible Families and Sequence-dependent Setups (SBPM-NCS), was recently introduced by Castelletti et al. (2025) as a challenging extension of the classical single-machine parallel-batching problem Uzsoy et al. (1994). Jobs can be processed simultaneously in batches, the processing time of each batch is determined by its longest job, and the objective is to minimize the makespan in presence of family compatibility constraints and sequence-dependent setup times. The mixed-integer linear formulation proposed in earlier work captures these features exactly, but becomes dicult to solve on medium- and large-size instances. To address this issue, we propose a column generation–based approach relying on an arc-ow formulation, building upon the frameworks of Druetto et al. (2023). Feasible solutions are represented as paths in a directed multigraph, where nodes encode both the position in the sequence and the dominant family of the current processed batch. Each arc corresponds to a feasible batch and is associated with a cost accounting for both batch processing times and sequence-dependent setup contributions. The formulation involves an exponential number of variables and is solved via a Restricted Master Problem, which is iteratively enriched through column generation. The pricing problem consists in identifying batches (columns) with negative reduced cost. We derive its structure and show that it can be reformulated, for xed positions, as a cardinality-constrained knapsack problem, where item prots are given by dual variables, while weights correspond to job sizes, and feasibility is enforced through capacity and cardinality constraints, together with family constraints. The resulting pricing problem is solved to optimality via a pseudo-polynomial dynamic programming algorithm. Preliminary computational results indicate an improvement in the initial lower bound and competitive solution quality within reasonable computational times.
File in questo prodotto:
File Dimensione Formato  
abstract_EUROyoung_26.pdf

accesso aperto

Descrizione: Abstract
Tipologia: Abstract
Licenza: Non specificato
Dimensione 138.13 kB
Formato Adobe PDF
138.13 kB Adobe PDF Visualizza/Apri
boa_lugano_26.pdf

accesso aperto

Descrizione: Book of abstracts
Tipologia: Abstract
Licenza: Non specificato
Dimensione 33.54 MB
Formato Adobe PDF
33.54 MB 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/656348
 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