Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups

The paper considers a temporal bin packing problem, where bins are servers using the Non-Uniform Memory Access architecture, and items are virtual machines. Bins are grouped together into racks. The main difference from the classical bin packing problem is that items are organized into placement groups, which are subdivided into subgroups. Items from different subgroups of the same group conflict and cannot be placed on the same rack. The additional constraints considered are relevant to cloud computing. Service reliability is essential for both service providers and their customers. This is achieved by isolating subgroups of virtual machines from the same placement group within a failure domain. Several stochastic algorithms have been developed to solve this problem. They are based on the classical first-fit algorithm, reordering of the packing sequence, and the bisection method. The algorithms give good results even for a rather naive initial solution (ordering). Moreover, they are easily parallelizable, which allows them to have an acceptable speed even for large problems.