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. Articles by Whitwell, G. Search for Related Content

A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing 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
School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Nottingham NG8 1BB, United Kingdom
ekb{at}cs.nott.ac.uk
rsh{at}cs.nott.ac.uk
gxk{at}cs.nott.ac.uk
gxw{at}cs.nott.ac.uk

This paper presents a new heuristic algorithm for the two-dimensional irregular stock-cutting problem, which generates significantly better results than the previous state of the art on a wide range of established benchmark problems. The developed algorithm is able to pack shapes with a traditional line representation, and it can also pack shapes that incorporate circular arcs and holes. This in itself represents a significant improvement upon the state of the art. By utilising hill climbing and tabu local search methods, the proposed technique produces 25 new best solutions for 26 previously reported benchmark problems drawn from over 20 years of cutting and packing research. These solutions are obtained using reasonable time frames, the majority of problems being solved within five minutes. In addition to this, we also present 10 new benchmark problems, which involve both circular arcs and holes. These are provided because of a shortage of realistic industrial style benchmark problems within the literature and to encourage further research and greater comparison between this and future methods.

Subject classifications: search production/scheduling; cutting-stock/trim; production/scheduling; approximations/heuristic; computers/computer science; artificial intelligence.
History: Received November 2003; revision received August 2004; accepted April 2005.

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]