Optimal multi-dimensional vector bin packing using simulated evolution

The use of the evolutionary heuristic simulated evolution for the optimization of the multi-dimensional vector bin packing problem, which is encountered in several industrial applications, is described. These applications range from production planning and steel fabrication to assignment of virtual machines (VMs) onto physical hosts at cloud-based data centers. The dimensions of VMs can include demands of CPU, memory, bandwidth, disk space etc. The generalized goodness functions that aid traversing the search space in an intelligent manner are designed to cater to the multidimensional nature of items (VMs). The efficiency of heuristics is tested by considering phase transition in the generation of difficult test cases. The quality of the heuristics is judged by determining how close the solution is to the estimated lower bound. A new implementation of a tighter lower bound is proposed. Experiments show that superior quality results are obtained by employing the proposed strategy.