Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem

The Cutting Stock Problem (CSP) is an optimization challenge that involves dividing large objects into smaller components while considering various managerial objectives. The problem’s complexity can differ based on factors such as object dimensionality, the number of cutting stages required, and any technological constraints. The demand for coils of varying sizes and quantities necessitates intermediate splitting and slitting stages to produce the finished rolls. Additionally, relationships between orders are affected by dimensional variations at each stage of processing. This specific variant of the problem is known as the One-and-a-Half Dimensional Two-Stage Cutting Stock Problem (1.5-D TSCSP). To address the 1.5-D TSCSP, two algorithmic approaches were developed: the Generate-and-Solve (G&S) method and a hybrid Row-and-Column Generation (R&CG) approach. Both aim to minimize total trim loss while navigating the complexities of the problem. Inspired by existing problems in the literature for simpler versions of the problem, a set of randomly generated test cases was prepared, as detailed in this paper. An implementation of the two approaches was used to obtain solutions for the generated test campaign. The simpler G&S approach demonstrated superior performance in solving smaller instances of the problem, while the R&CG approach exhibited greater efficiency and provided superior solutions for larger instances.