An improved best‐fit heuristic for the orthogonal strip packing problem. (27th June 2013)

• Record Type: Journal Article
• Authors: Verstichel, Jannes; De Causmaecker, Patrick; Berghe, Greet Vanden
• Other Names: Viana Ana guestEditor.; Gomes A. Miguel guestEditor.; Costa Teresa guestEditor.
• Is Part Of: International transactions in operational research. Volume 20:Number 5(2013:Sep.)
• Page Start: 711
• Page End: 730
• Publication Date: 2013-06-27
• Subjects: heuristics -- cutting stock -- optimization -- packing problems; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12030
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: The best‐fit heuristic is a simple and powerful tool for solving the two‐dimensional orthogonal strip packing problem. It is the most efficient constructive heuristic on a wide range of rectangular strip packing benchmark problems. In this paper, the results of the original best‐fit heuristic are further improved by adding new item orderings and item placement strategies, resulting in the three‐way best‐fit heuristic. By applying these steps, significantly better results are obtained in comparable computation time. Furthermore, some data structures are implemented, which increase the scalability of the heuristic for large problem instances and a slightly altered heuristic with an optimal O ( n log n ) time complexity is proposed. Both heuristics produce similar results, but the optimal time heuristic is significantly faster than the three‐way best‐fit heuristic on all but the smallest instances.