Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups | Sciact - Система учета научной деятельности ИМ СО РАН

Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups Научная публикация

Конференция

XXIII International Conference Mathematical Optimization Theory and Operations Research
30 июн. - 6 июл. 2024 , Омск

Сборник

Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings
Сборник, Springer Cham. Switzerland.2024. 464 c. ISBN 978-3-031-62792-7.

Журнал

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Вых. Данные

Год: 2024, Том: 14766, Страницы: 199-211 Страниц : 13 DOI: 10.1007/978-3-031-62792-7_14

Ключевые слова

Stochastic algorithms, temporal bin packing, first-fit · placement groups, placement constraints

Авторы

Turnaev Alexander ^1,2 , Panin Artem ²

Организации

1	Novosibirsk State University
2	Sobolev Institute of Mathematics

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

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.

Turnaev A. , Panin A.
Stochastic Greedy Algorithms for a Temporal Bin Packing Problem with Placement Groups
В сборнике 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

Поступила в редакцию:	29 мар. 2024 г.
Опубликована в печати:	18 июн. 2024 г.
Опубликована online:	18 июн. 2024 г.

Scopus:	2-s2.0-85198482440
OpenAlex:	W4399743091

Пока нет цитирований