Heuristics for Vector Bin Packing

Abstract

Inspired by virtual machine placement problems, we study heuristics for the Vector Bin Packing problem, where we are required to pack n items represented by d-dimensional vectors, into as few bins of size 1 each as possible. We systematically study variants of the First Fit Decreasing (FFD) algorithm that have been proposed for this problem. Inspired by bad instances for FFD-type algorithms, we propose new geometric heuristics that run nearly as fast as FFD for reasonable values of n and d. We report on empirical evaluations of the FFD-based, as well as the new heuristics on large families of distributions. We identify which FFD variants work best in most cases and show that our new heuristics usually outperform FFD-based heuristics and can sometimes reduce the number of bins used by up to ten percent. Further, in all cases where we were able to compute the optimal solution we found our new heuristics within few percent of optimal. We conclude that these new heuristics are an excellent alternative to FFD-based heuristics and are prime candidates to be used in practice.