Classification and evaluation of the algorithms for vector bin packing - INRIA - Institut National de Recherche en Informatique et en Automatique
Journal Articles Computers and Operations Research Year : 2025

Classification and evaluation of the algorithms for vector bin packing

Abstract

Heuristics for Vector Bin Packing (VBP) play an important role in modern distributed computing systems and other applications aimed at optimizing the usage of multidimensional resources. In this paper we perform a systematic classication of heuristics for VBP, with the focus on construction heuristics. We bring together existing VBP algorithms and their tuning parameters, and propose new algorithms and new tuning parameters. For a less studied class of multi-bin algorithms, we explore their properties analytically, considering monotonic and anomalous behavior and approximation guarantees. For empirical evaluation, all algorithms are implemented as the Vectorpack library and assessed through extensive experiments. Our ndings may serve as the basis for the development of more complex, hybrid algorithms, hyperheuristics and machine learning algorithms. The Vectorpack library can also be adjusted for addressing enhanced VBP problems with additional features, which arise in applications, especially those typical for modern distributed computing systems.
Embargoed file
Embargoed file
0 4 29
Year Month Jours
Avant la publication
Tuesday, May 6, 2025
Embargoed file
Tuesday, May 6, 2025
Please log in to request access to the document

Dates and versions

hal-04769128 , version 1 (06-11-2024)

Licence

Identifiers

Cite

Clément Mommessin, Thomas Erlebach, Natalia Shakhlevich. Classification and evaluation of the algorithms for vector bin packing. Computers and Operations Research, 2025, 173, pp.106860. ⟨10.1016/j.cor.2024.106860⟩. ⟨hal-04769128⟩
0 View
0 Download

Altmetric

Share

More