A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem

We consider the cutting of rectangular order pieces into stock pieces of sp ecified width and length. The cutting process involves three stages of orth ogonal guillotine cutting: Stock pieces are cut into sections that are cut into slits that are cut into order pieces. Restrictions imposed on the cutt ing process make the combinatorial structure of the problem more complex, b ut limit the scope of solution space. The objective of the problem is mainl y to minimize waste, but our model also accounts for other issues such as a ging stock pieces, urgent or optional orders, and fixed setup costs. Our so lution approach involves a nested decomposition of the problem and the recu rsive use of the column-generation technique: We use a column-generation fo rmulation of the problem (Gilmore and Gomory 1965) and the cutting-pattern- generation subproblem is itself solved using a column-generation algorithm. LP-based lower bounds on the minimum cost are computed and, by rounding th e LP solution, a feasible solution and associated upper bound is obtained. This approach could in principle be used in a branch-and-bound search to so lve the problem to optimality. We report computational results for industri al instances. The algorithm is being used in industry as a production-plann ing tool.