An improved best-fit heuristic for the orthogonal strip packing problem

作者：Verstichel Jannes^*; De Causmaecker Patrick; Vanden Berghe Greet

来源：International Transactions in Operational Research, 2013, 20(5): 711-730.

DOI：10.1111/itor.12030

• heuristics
• cutting stock
• optimization
• packing problems

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.

• 出版日期2013-9