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 Google Scholar Google Scholar Articles by Burke, E. K. Articles by Whitwell, G. Search for Related Content

A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem

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

The best-fit heuristic is a simple yet powerful one-pass approach for the two-dimensional rectangular stock-cutting problem. It had achieved the best published results on a wide range of benchmark problems until the development of the approaches described in this paper. Here, we illustrate how improvements in solution quality can be achieved by the hybridisation of the best-fit heuristic together with simulated annealing and the bottom-left-fill algorithm. We compare and contrast the new hybrid approach with other approaches from the literature in terms of execution times and the quality of the solutions achieved. Using a range of standard benchmark problems from the literature, we demonstrate how the new approach achieves significantly better results than previously published methods on almost all of the problem instances. In addition, we provide results on 10 new benchmark problems to encourage further research and greater comparison between current and future methods.

Key words: stock cutting; simulated annealing; heuristics; industries; manufacturing
History: received July 2004; revised June 2008; accepted July 2008.