Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups Full article
| Conference |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024 , Омск |
||||
|---|---|---|---|---|---|
| Source | Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings Compilation, Springer Cham. Switzerland.2024. 464 c. ISBN 978-3-031-62792-7. |
||||
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||
| Output data | Year: 2024, Volume: 14766, Pages: 199-211 Pages count : 13 DOI: 10.1007/978-3-031-62792-7_14 | ||||
| Tags | Stochastic algorithms, temporal bin packing, first-fit · placement groups, placement constraints | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
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.
Cite:
Turnaev A.
, Panin A.
Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups
In compilation Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings. – Springer Cham., 2024. – C.199-211. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_14 Scopus OpenAlex
Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups
In compilation Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings. – Springer Cham., 2024. – C.199-211. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_14 Scopus OpenAlex
Dates:
| Submitted: | Mar 29, 2024 |
| Published print: | Jun 18, 2024 |
| Published online: | Jun 18, 2024 |
Identifiers:
| Scopus: | 2-s2.0-85198482440 |
| OpenAlex: | W4399743091 |
Citing:
Пока нет цитирований