Vector bin packing with heterogeneous bins: application to the machine reassignment problem

Michaël Gabay () and Sofia Zaourar ()
Additional contact information
Michaël Gabay: Univ. Grenoble Alpes
Sofia Zaourar: UJF, Inria Grenoble

Annals of Operations Research, 2016, vol. 242, issue 1, No 8, 194 pages

Abstract: Abstract In this paper, we introduce a generalization of the vector bin packing problem, where the bins have variable sizes. This generalization can be used to model virtual machine placement problems and in particular to build feasible solutions for the machine reassignment problem. We propose several families of greedy heuristics for this problem and show that they are flexible and can be adapted to handle additional constraints. We present structural properties of the machine reassignment problem, that allow us to decompose it into smaller subproblems and adapt our heuristics to them. We evaluate our heuristics on academic benchmarks of the vector bin packing problem, a randomly generated vector bin packing problem with heterogeneous bins benchmark as well as Google’s realistic instances of the machine reassignment problem.

Keywords: Vector bin packing with heterogeneous bins; Machine reassignment problem; Heuristics; Virtual machine placement; Vector bin packing (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-1973-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:242:y:2016:i:1:d:10.1007_s10479-015-1973-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-1973-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().