Preview

Modeling and Analysis of Information Systems

Advanced search

A patterning algorithm for the dynamic bin packing problem with placement groups

https://doi.org/10.18255/1818-1015-2025-2-110-131

Abstract

We consider an NP-hard problem of dynamically distributing virtual machines to servers with placement groups. For each virtual machine, parameters such as required number of resources and creation and deletion timestamps are known. Each server is a composition of NUMA nodes and is placed in a rack. Large virtual machines, which are placed on two nodes of a single server, and small virtual machines, which impose additional conditions on their placement, are considered. Placement groups are associations of subsets of virtual machines with conflict conditions between the subsets. The goal is to pack all virtual machines using the minimum number of server racks within the considered time horizon. A heuristic based on the column generation method is proposed to solve this problem. We analyze a set of static problems at different time points necessary to form a common set of patterns used in the construction of upper bounds. The results of computational experiments on real open instances show an insignificant difference between the lower and upper bounds.

About the Authors

Evgeniy A. Brazhnikov
Sobolev Institute of Mathematics of the Siberian Branch of the RAS
Russian Federation


Artem A. Panin
Sobolev Institute of Mathematics of the Siberian Branch of the RAS
Russian Federation


Alexey V. Ratushnyi
Sobolev Institute of Mathematics of the Siberian Branch of the RAS
Russian Federation


References

1. Z. Farahmandpour, M. Seyedmahmoudian, and A. Stojcevski, “A Review on the Service Virtualisation and Its Structural Pillars,” Applied Sciences, vol. 11, no. 5, p. 2381, 2021.

2. M. de Cauwer, D. Mehta, and B. O'Sullivan, “The Temporal Bin Packing Problem: An Application to Workload Management in Data Centres,” in IEEE 28th International Conference on Tools with Artificial Intelligence, 2016, pp. 157–164.

3. M. Dell'Amico, F. Furini, and M. Iori, “A Branch-and-Price Algorithm for the Temporal Bin Packing Problem,” Computers & Operations Research, vol. 114, p. 104825, 2019.

4. A. Ratushnyi and Y. Kochetov, “A Column Generation Based Heuristic for a Temporal Bin Packing Problem,” in Mathematical Optimization Theory and Operations Research, 2021, pp. 96–110.

5. M. Sakhno, “A Grouping Genetic Algorithm for the Temporal Vector Bin Packing Problem,” in 19th International Asian School-Seminar on Optimization Problems of Complex Systems, 2023, pp. 94–99.

6. D. Lazarev and N. Kuzyurin, “On Online Algorithms for Bin, Strip, and Box Packing, and Their Worst-Case and Average-Case Analysis,” Programming and Computer Software, vol. 45, no. 4, pp. 448–457, 2020.

7. V. Toporkov, D. Yemelyanov, and A. Bulkhak, “Machine Learning-Based Online Scheduling in Distributed Computing,” in Parallel Processing and Applied Mathematics, 2023, pp. 248–259.

8. T. Wood, P. Shenoy, A. Venkataramani, and M. Yousif, “Sandpiper: Black-box and gray-box resource management for virtual machines,” Computer Networks, vol. 53, no. 17, pp. 2923–2938, 2009.

9. V. Ivannikov, D. Grushin, N. Kuzyurin, A. Pospelov, and S. A., “Software for improving the energy efficiency of a computer cluster,” Programming and Computer Software, vol. 36, pp. 327–336, 2010.

10. F. Furini and X. Shen, “Matheuristics for the Temporal Bin Packing Problem,” in Recent Developments in Metaheuristics, 2018, pp. 333–345.

11. D. Grushin and N. Kuzyurin, “On Effective Scheduling in Computing Clusters,” Programming and Computer Software, vol. 45, pp. 398–404, 2019.

12. A. Beloglazov, J. Abawajy, and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing,” Future Generation Computer Systems, vol. 28, no. 5, pp. 755–768, 2012.

13. D. Kusic, J. Kephart, J. Hanson, N. Kandasamy, and G. Jiang, “Power and Performance Management of Virtualized Computing Environments Via Lookahead Control,” Cluster Computing, vol. 12, pp. 1–15, 2009.

14. A. Verma, P. Ahuja, and A. Neogi, “pMapper: Power and Migration Cost Aware Application Placement in Virtualized Systems,” in Middleware, 2008, pp. 243–264.

15. M. Mao and M. Humphrey, “A Performance Study on the VM Startup Time in the Cloud,” in IEEE Fifth International Conference on Cloud Computing, 2012, pp. 423–430.

16. A. Ratushnyi, “A Pattern-Based Heuristic for a Temporal Bin Packing Problem with Conflicts,” in Mathematical Optimization Theory and Operations Research: Recent Trends, 2023, pp. 161–175.

17. C. Lameter, “NUMA (Non-Uniform Memory Access): An Overview,” Queue, vol. 11, no. 7, pp. 40–51, 2013.

18. “Placement groups for your Amazon EC2 instances.” [Online]. Available: https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/placement-groups.html.

19. “Temporal Bin Packing Problem with Placement Groups.” [Online]. Available: http://old.math.nsc.ru/AP/benchmarks/Temporal%20Bin%20Packing/binpack.html.

20. “SCIP. Solving Constraint Integer Programs.” [Online]. Available: https://www.scipopt.org/.


Review

For citations:


Brazhnikov E.A., Panin A.A., Ratushnyi A.V. A patterning algorithm for the dynamic bin packing problem with placement groups. Modeling and Analysis of Information Systems. 2025;32(2):110-131. (In Russ.) https://doi.org/10.18255/1818-1015-2025-2-110-131

Views: 22


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)