Where academic tradition
meets the exciting future

Fast Algorithms for Fragmentable Items Bin Packing

Benjamin Byholm, Ivan Porres, Fast Algorithms for Fragmentable Items Bin Packing. TUCS Technical Reports 1181, TUCS, 2017.

Abstract:

Bin packing with fragmentable items is a variant of the classic bin packing
problem where items may be cut into smaller fragments. Models based on
packing fragmentable items are useful for representing finite shared resources.
The objective is to minimize the number of item fragments, or equivalently,
to minimize the number of cuts, for a given number of bins. 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 set,
consisting of 450 problems with up to 1024 items, the lower bound performs no
worse than a 9/10-approximation. The algorithm found an optimal solution in
97 % of all 4500 runs. Most runs finished in less than 6 generations, or 4 ms.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tByPo17a,
  title = {Fast Algorithms for Fragmentable Items Bin Packing},
  author = {Byholm, Benjamin and Porres, Ivan},
  number = {1181},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2017},
  keywords = {Packing, Combinatorial optimization, Metaheuristics},
  ISBN = {978-952-12-3559-7},
}

Belongs to TUCS Research Unit(s): Software Engineering Laboratory (SE Lab)

Edit publication