Temporal Bin Packing Problems with Placement Constraints: MIP-Models and Complexity 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: 157-169 Pages count : 13 DOI: 10.1007/978-3-031-62792-7_11 | ||||
| Tags | Temporal Bin Packing · Placement groups · Virtual machines · Complexity · Inapproximability · MIP model | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
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.
Cite:
Borisovsky P.
, Eremeev A.
, Panin A.
, Sakhno M.
Temporal Bin Packing Problems with Placement Constraints: MIP-Models and Complexity
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.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
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.157-169. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_11 Scopus OpenAlex
Dates:
| Submitted: | Mar 29, 2024 |
| Published print: | Jun 18, 2024 |
| Published online: | Jun 18, 2024 |
Identifiers:
| Scopus: | 2-s2.0-85198486850 |
| OpenAlex: | W4399742907 |