Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review
Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups. / Turnaev, Alexander; Panin, Artem.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Science and Business Media Deutschland GmbH, 2024. p. 199-211 14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14766 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review
}
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 -
ID: 60501072