Temporal Bin Packing Problems with Placement Constraints: MIP-Models and Complexity Научная публикация
| Конференция |
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, Страницы: 157-169 Страниц : 13 DOI: 10.1007/978-3-031-62792-7_11 | ||||
| Ключевые слова | Temporal Bin Packing · Placement groups · Virtual machines · Complexity · Inapproximability · MIP model | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Реферат:
In this paper, we investigate new problem statements, generalizing the Temporal Bin Packing Problem (TBPP) with possible applications in cloud computing. We suppose that items are organized into batches. All items in the same batch are placed simultaneously. In cloud computing, items correspond to virtual machines (VMs) and batches correspond to user requests for VM placement. In addition, cloud users can create placement groups consisting of VMs united by a single placement constraint named cluster: at any moment in time, VMs from the same placement group must be hosted on the same rack of servers. In this paper, we consider servers as one-dimensional bins. We investigate the computational complexity and inapproximability of different formulations of the TBPP with cluster placement constraint and suggest mixed integer programming models for them.
Библиографическая ссылка:
Borisovsky P.
, Eremeev A.
, Panin A.
, Sakhno M.
Temporal Bin Packing Problems with Placement Constraints: MIP-Models and Complexity
В сборнике Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings. – Springer Cham., 2024. – C.157-169. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_11 Scopus OpenAlex
Temporal Bin Packing Problems with Placement Constraints: MIP-Models and Complexity
В сборнике Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings. – Springer Cham., 2024. – C.157-169. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_11 Scopus OpenAlex
Даты:
| Поступила в редакцию: | 29 мар. 2024 г. |
| Опубликована в печати: | 18 июн. 2024 г. |
| Опубликована online: | 18 июн. 2024 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85198486850 |
| OpenAlex: | W4399742907 |