Fast algorithms for fragmentable items bin packing

A1 Journal article (refereed)


Internal Authors/Editors


Publication Details

List of Authors: Benjamin Byholm, Ivan Porres
Publisher: Springer
Publication year: 2018
Journal: Journal of Heuristics
Volume number: 24
Issue number: 5
Start page: 697
End page: 723
eISSN: 1572-9397


Abstract

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92% of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99% of all 4500 runs. No run lasted longer than 220 ms.


Documents


Last updated on 2019-19-11 at 05:51