Variable Cost and Size Cluster Vector Bin Packing – A Model and Heuristics for Cloud Capacity Planning

Vector bin packing is a problem in combinatorial optimization that is particularly relevant in the area of cloud computing but also finds application in various areas of logistics. The problem deals with how to optimally place items into bins with constraints on multiple separate resource dimensions. We extend the problem to a cluster structure of bins, including variable bin sizes and cluster costs. The proposed extension of vector bin packing, which we term VCSCVBP, allows us to model a practical problem in the area of cloud computing, namely, the cloud capacity planning problem, where servers are organized in clusters. Optimizing data center capacity in terms of costs and fulfillment of customer demands in the form of virtual machines has become crucial due to the increasing demand for computing resources. We introduce several novel heuristics, called CS-P heuristics, consisting of a packing and a cluster selection step. The algorithms are evaluated with a benchmark based on practically relevant cloud computing data. Substantial runtime improvements are demonstrated by the computational experiments. For two out of three considered cost scenarios, only a slight deviation of the objective value obtained by the CS-P heuristics from the objective value obtained by the solver is observed. ... mehrBy exploiting cluster information and discarding certain cluster types through an additional procedure, this is also achieved for the third cost scenario.