This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Burke, E. K. Articles by Whitwell, G. Search for Related Content

A New Placement Heuristic for the Orthogonal Stock-Cutting Problem

School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, United Kingdom
School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, United Kingdom
School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, United Kingdom
ekb{at}cs.nott.ac.uk
gxk{at}cs.nott.ac.uk
gxw{at}cs.nott.ac.uk

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.

Subject classifications: production/scheduling; cutting stock/trim; production/scheduling; approximations/heuristic; computers/computer science; artificial intelligence.
History: Received May 2002; revision received January 2003; accepted June 2003.

This article has been cited by other articles:

				E. K. Burke, G. Kendall, and G. Whitwell A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem INFORMS Journal on Computing, July 1, 2009; 21(3): 505 - 516. [Abstract] [PDF]

				R. Bai and G. Kendall A Model for Fresh Produce Shelf-Space Allocation and Inventory Management with Freshness-Condition-Dependent Demand INFORMS Journal on Computing, January 1, 2008; 20(1): 78 - 85. [Abstract] [PDF]

				E. Burke, R. Hellier, G. Kendall, and G. Whitwell A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem Operations Research, May 1, 2006; 54(3): 587 - 601. [Abstract] [PDF]