The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio

摘要

We investigate the best-fit heuristic algorithm by Burke et al. [2004. A new placement heuristic for the orthogonal stock-cutting problem. Operations Research 52, 655-671] for the rectangular strip packing problem. For its simplicity and good performance, the best-fit heuristic has become one of the most significant algorithms for the rectangular strip packing. In this paper, we propose an efficient implementation of the best-fit heuristic that requires O(n) space and O(n log n) time, where n is the number of rectangles. We prove that this complexity is optimal, and we also show the practical usefulness of our implementation via computational experiments. Furthermore, we give the worst-case approximation ratio of the best-fit heuristic.