TY - CHAP

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

AU - Turnaev, Alexander

AU - Panin, Artem

N1 - Conference code: 23

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - Stochastic algorithms

KW - first-fit

KW - placement constraints

KW - placement groups

KW - temporal bin packing

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85198482440&origin=inward&txGid=ddd6ba6edb8d8b554e79c58df3c0f5d8

UR - https://www.mendeley.com/catalogue/963d47d8-986f-362c-8da7-d7712fde41d5/

U2 - 10.1007/978-3-031-62792-7_14

DO - 10.1007/978-3-031-62792-7_14

M3 - Chapter

SN - 9783031627910

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 199

EP - 211

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Science and Business Media Deutschland GmbH

T2 - 23rd International Conference on Mathematical Optimization Theory and Operations Research

Y2 - 30 June 2024 through 6 July 2024

ER -