A Scalable Approach for the K-Staged Two-Dimensional Cutting Stock Problem

Abstract

This work focuses on the K-staged two-dimensional cutting stock problem with variable sheet size. High-quality solutions are computed by an efficient beam-search algorithm that exploits the congruency of subpatterns and takes informed decisions on which of the available sheet types to use for the solutions. We extend this algorithm by embedding it in a sequential value-correction framework that runs the algorithm multiple times while adapting element type values in each iteration and thus constitutes a guided diversification process for computing a solution. Experiments demonstrate the effectiveness of the approach and that the sequential value-correction further increases the overall quality of the constructed solutions.