An Algorithm for Two-Dimensional Cutting Problems

Nicos Christofides and Charles Whitlock
Additional contact information
Nicos Christofides: Imperial College, London, England
Charles Whitlock: Imperial College, London, England

Operations Research, 1977, vol. 25, issue 1, 30-44

Abstract: We present a tree-search algorithm for two-dimensional cutting problems in which there is a constraint on the maximum number of each type of piece that is to be produced. The algorithm limits the size of the tree search by deriving and imposing necessary conditions for the cutting pattern to be optimal. A dynamic programming procedure for the solution of the unconstrained problem and a node evaluation method based on a transportation routine are used to produce upper bounds during the search. The computational performance of the algorithm is illustrated by tests performed on a large number of randomly generated problems with constraints of varying “tightness.” The results indicate that the algorithm is an effective procedure for solving cutting problems of medium size.

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (96)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.25.1.30 (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:oropre:v:25:y:1977:i:1:p:30-44

Access Statistics for this article

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