Analysis of heuristics for vector scheduling and vector bin packing

Fundamental problems in operational research are vector scheduling and vector bin packing where a set of vectors or items must be packed into a fixed set of bins or a minimum number of bins such that, in each bin, the sum of the vectors does not exceed the bin’s vector capacity. They have many applications such as scheduling virtual machines in compute clouds where the virtual and physical machines can be regarded as items and bins, respectively. As vector scheduling and vector bin packing are NP-hard, no efficient exact algorithms are known.

In this paper we introduce new heuristics and provide the first extensive evaluation of heuristics and algorithms for vector scheduling and bin packing including several heuristics from the literature. The new heuristics are a local search algorithm, a game-theoretic approach and a best-fit heuristic. Our experiments show a general trade-off between running time and packing quality. The new local search algorithm outperforms almost all other heuristics while maintaining a reasonable running time.