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

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 [ABSTRACT FROM AUTHOR]