Title: An improved best fit heuristic for the orthogonal strip packing problem
Authors: Verstichel, Jannes ×
De Causmaecker, Patrick
Vanden Berghe, Greet #
Issue Date: 27-Jun-2013
Publisher: Pergamon
Series Title: International Transactions in Operational Research vol:20 issue:5 pages:711-730
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.
ISSN: 0969-6016
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Computer Science, Campus Kulak Kortrijk
Informatics Section
Computer Science Technology TC, Technology Campuses Ghent and Aalst
Technologiecluster Computerwetenschappen
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science