A New Placement Heuristic for the Orthogonal Stock-Cutting Problem

E. K. Burke (), G. Kendall () and G. Whitwell ()
Additional contact information
E. K. Burke: School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, United Kingdom
G. Kendall: School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, United Kingdom
G. Whitwell: School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, United Kingdom

Operations Research, 2004, vol. 52, issue 4, 655-671

Abstract: This paper presents a new best-fit heuristic for the two-dimensional rectangular stock-cutting problem and demonstrates its effectiveness by comparing it against other published approaches. A placement algorithm usually takes a list of shapes, sorted by some property such as increasing height or decreasing area, and then applies a placement rule to each of these shapes in turn. The proposed method is not restricted to the first shape encountered but may dynamically search the list for better candidate shapes for placement. We suggest an efficient implementation of our heuristic and show that it compares favourably to other heuristic and metaheuristic approaches from the literature in terms of both solution quality and execution time. We also present data for new problem instances to encourage further research and greater comparison between this and future methods.

Keywords: production/scheduling; cutting stock/trim; production/scheduling; approximations/heuristic; computers/computer science; artificial intelligence (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (51)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0109 (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:52:y:2004:i:4:p:655-671

Access Statistics for this article

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