A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem

Citation

Burke E, Kendall G & Whitwell G (2009) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem. INFORMS Journal on Computing, 21 (3), pp. 505-516. https://doi.org/10.1287/ijoc.1080.0306

Abstract
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.

Keywords
stock cutting; simulated annealing; heuristics; industries; manufacturing

Journal
INFORMS Journal on Computing: Volume 21, Issue 3