The Single Batch-Processing Machine Scheduling Problem with Non-identical Jobs, Compatible Families, and Sequence-dependent Setups (SBPM-NCS), recently introduced by Castelletti et al. (2025), extends the classical parallel-batching scheduling problem by incorporating family compatibilities and sequence-dependent setup times. Jobs are processed simultaneously in batches, whose processing time is determined by the longest job in the batch, while setup times depend on the dominant family of consecutive batches. The objective is to minimize the makespan. The original problem is decomposed into a master–pricing structure, following the framework presented in Druetto et al (2023). The master problem is formulated as an arc-flow set partitioning model and is solved via a restricted master problem, initially defined on a subset of variables and solved in its linear relaxation. It is progressively enriched through a column generation scheme driven by a pricing problem, which introduces new variables by identifying promising batch configurations (columns). In detail, the pricing problem is reformulated as a knapsack-type selection problem with capacity, cardinality, and family compatibility constraints, and solved to optimality via pseudo-polynomial dynamic programming. We further develop primal heuristics for constructing feasible integer solutions from fractional column generation lower bounds, including Price-and-Branch, Variable Rounding, Early Variable Rounding, and Global Variable Rounding, which exploit both the structure of the generated columns and the dual information of the master problem. Computational results on synthetic instances show that the proposed approach provides significantly improved lower bounds compared to existing formulations, while also yielding high-quality feasible solutions and competitive computational performance.
International Conference on Optimization and Decision Science (ODS) 2026
Annalisa Castelletti;Renata Mansini;
2026-01-01
Abstract
The Single Batch-Processing Machine Scheduling Problem with Non-identical Jobs, Compatible Families, and Sequence-dependent Setups (SBPM-NCS), recently introduced by Castelletti et al. (2025), extends the classical parallel-batching scheduling problem by incorporating family compatibilities and sequence-dependent setup times. Jobs are processed simultaneously in batches, whose processing time is determined by the longest job in the batch, while setup times depend on the dominant family of consecutive batches. The objective is to minimize the makespan. The original problem is decomposed into a master–pricing structure, following the framework presented in Druetto et al (2023). The master problem is formulated as an arc-flow set partitioning model and is solved via a restricted master problem, initially defined on a subset of variables and solved in its linear relaxation. It is progressively enriched through a column generation scheme driven by a pricing problem, which introduces new variables by identifying promising batch configurations (columns). In detail, the pricing problem is reformulated as a knapsack-type selection problem with capacity, cardinality, and family compatibility constraints, and solved to optimality via pseudo-polynomial dynamic programming. We further develop primal heuristics for constructing feasible integer solutions from fractional column generation lower bounds, including Price-and-Branch, Variable Rounding, Early Variable Rounding, and Global Variable Rounding, which exploit both the structure of the generated columns and the dual information of the master problem. Computational results on synthetic instances show that the proposed approach provides significantly improved lower bounds compared to existing formulations, while also yielding high-quality feasible solutions and competitive computational performance.| File | Dimensione | Formato | |
|---|---|---|---|
|
Abstracts -ods2026.pdf
accesso aperto
Descrizione: Abstract
Tipologia:
Abstract
Licenza:
Non specificato
Dimensione
79.75 kB
Formato
Adobe PDF
|
79.75 kB | Adobe PDF | Visualizza/Apri |
|
book-of-abstracts_ods26.pdf
accesso aperto
Descrizione: Book of Abstract
Tipologia:
Abstract
Licenza:
Non specificato
Dimensione
5.33 MB
Formato
Adobe PDF
|
5.33 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


