A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem

François Vanderbeck
Additional contact information
François Vanderbeck: MAB, Université de Bordeaux 1, 351, Cours de la Libération, F-33405 Talence Cedex, France

Management Science, 2001, vol. 47, issue 6, 864-879

Abstract: We consider the cutting of rectangular order pieces into stock pieces of specified width and length. The cutting process involves three stages of orthogonal guillotine cutting: Stock pieces are cut into sections that are cut into slits that are cut into order pieces. Restrictions imposed on the cutting process make the combinatorial structure of the problem more complex, but limit the scope of solution space. The objective of the problem is mainly to minimize waste, but our model also accounts for other issues such as aging stock pieces, urgent or optional orders, and fixed setup costs. Our solution approach involves a nested decomposition of the problem and the recursive use of the column-generation technique: We use a column-generation formulation 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 the 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 solve the problem to optimality. We report computational results for industrial instances. The algorithm is being used in industry as a production-planning tool.

Keywords: Cutting Stock; Trim Loss; Knapsack Problems; Integer Programming; Nested Decomposition (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.47.6.864.9809 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:47:y:2001:i:6:p:864-879

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().