Column Generation-Based Heuristic for Stochastic Bin Packing with One Defect per Pattern

In manufacturing systems where industrial components are produced by cutting bars of raw material, production efficiency can be significantly compromised by unpredictable defects occurring along the bars. Similarly, in non-preemptive parallel machine scheduling, machines may become temporarily unavailable due to unforeseen disruptions, thereby delaying job completion. Altogether, these uncertainties can pose a serious threat to process reliability and economic performance.
In this work, a 0-1 pattern-based formulation is proposed to deal with such disruptions – up to one per pattern – and is solved through column generation. Specifically, by solving the pricing problem we compute a one-dimensional cutting pattern (or job-to-machine assignment) that can be reconfigured in response to the defect (or machine downtime) observed: the objective is to maximize resource utilization and, consequently, save economic value. To the best of our knowledge, this model represents the first exact formulation devised for the problem addressed.
Numerical tests on benchmark instances derived from literature assess the quality of the model under the assumption of uniform defect distribution. Primal bounds obtained by means of Price-and-Branch procedure are compared with the heuristic framework developed in Arbib et al. (2023). The effectiveness of the methodology to cope with stochastic disruptions is finally discussed.