GRASP and Path Relinking for the Two-Dimensional Two-Stage Cutting-Stock Problem

We develop a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional two-stage cutting-stock problem. This is a special cutting problem in which the cut is performed in two phases. In the first phase, the stock rectangle is slit down its width into different vertical strips and in the second phase, each of these strips is processed to obtain the final pieces. We propose two different algorithms based on GRASP methodology. One is “piece-oriented” while the other is “strip-oriented.” Both procedures are fast and provide solutions of different structures to this cutting problem. We also propose a path-relinking algorithm, which operates on a set of elite solutions obtained with both GRASP methods, to search for improved outcomes. We perform extensive computational experiments with a wide range of instances, first to study the effect of changes in critical search parameters, and then to compare the efficiency of alternative solution procedures. The experiments establish the effectiveness of our procedure in relation to approaches previously identified as best, especially in large-scale instances.