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 dicult 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 prots 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 dicult 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 prots 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 | 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.


