maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2025-2-110-131mais-1936Research ArticleDiscrete Mathematics in Relation to Computer ScienceАлгоритм шаблонизации для динамической задачи упаковки в контейнеры с группами размещенияA patterning algorithm for the dynamic bin packing problem with placement groupshttps://orcid.org/0009-0004-3414-5176БражниковЕвгений АлександровичBrazhnikovEvgeniy A.brazhnikov.eugene@gmail.comhttps://orcid.org/0000-0002-1844-6276ПанинАртём АлександровичPaninArtem A.aapanin1988@gmail.comhttps://orcid.org/0000-0001-5173-3536РатушныйАлексей ВладленовичRatushnyiAlexey V.alexeyratushny@gmail.comИнститут математики им. С. Л. Соболева СО РАНРоссияSobolev Institute of Mathematics of the Siberian Branch of the RASRussian Federation202528062025322110131Copyright © Бражников Е.А., Панин А.А., Ратушный А.В., 20252025Бражников Е.А., Панин А.А., Ратушный А.В.Brazhnikov E.A., Panin A.A., Ratushnyi A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1936

Рассматривается NP-трудная задача динамического распределения виртуальных машин по серверам с группами размещения. Для каждой виртуальной машины известны такие параметры, как необходимое количество ресурсов и временные метки создания и удаления. Каждый сервер представляет собой композицию NUMA-узлов и размещается в некоторой стойке. Рассматриваются большие виртуальные машины, размещаемые на два узла одного сервера, и маленькие, что накладывает дополнительные условия для их размещения. Группы размещения представляют собой объединения подмножеств виртуальных машин с условиями конфликта между подмножествами. Задача состоит в том, чтобы упаковать все виртуальные машины с использованием минимального количества стоек серверов в течение рассматриваемого временного горизонта. Для решения данной задачи предлагается эвристика, основанная на методе генерации столбцов. Анализируется набор статических задач в различные моменты времени, необходимых для формирования общего набора шаблонов, используемых при построении верхних оценок. Результаты вычислительных экспериментов на реальных открытых примерах указывают на незначительные расхождения между нижними и верхними границами.

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.

задача упаковки в контейнерывиртуальные машиныэвристикигруппы размещениягенерация столбцовbin packing problemvirtual machinesheuristicsplacement groupscolumn generationFWNF–2022–0019FWNF–2022–0019ReferencesZ. 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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.F. Furini and X. Shen, “Matheuristics for the Temporal Bin Packing Problem,” in Recent Developments in Metaheuristics, 2018, pp. 333–345.F. Furini and X. Shen, “Matheuristics for the Temporal Bin Packing Problem,” in Recent Developments in Metaheuristics, 2018, pp. 333–345.D. Grushin and N. Kuzyurin, “On Effective Scheduling in Computing Clusters,” Programming and Computer Software, vol. 45, pp. 398–404, 2019.D. Grushin and N. Kuzyurin, “On Effective Scheduling in Computing Clusters,” Programming and Computer Software, vol. 45, pp. 398–404, 2019.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.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.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.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.A. Verma, P. Ahuja, and A. Neogi, “pMapper: Power and Migration Cost Aware Application Placement in Virtualized Systems,” in Middleware, 2008, pp. 243–264.A. Verma, P. Ahuja, and A. Neogi, “pMapper: Power and Migration Cost Aware Application Placement in Virtualized Systems,” in Middleware, 2008, pp. 243–264.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.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.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.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.C. Lameter, “NUMA (Non-Uniform Memory Access): An Overview,” Queue, vol. 11, no. 7, pp. 40–51, 2013.C. Lameter, “NUMA (Non-Uniform Memory Access): An Overview,” Queue, vol. 11, no. 7, pp. 40–51, 2013.“Placement groups for your Amazon EC2 instances.” [Online]. Available: https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/placement-groups.html.“Placement groups for your Amazon EC2 instances.” [Online]. Available: https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/placement-groups.html.“Temporal Bin Packing Problem with Placement Groups.” [Online]. Available: http://old.math.nsc.ru/AP/benchmarks/Temporal%20Bin%20Packing/binpack.html.“Temporal Bin Packing Problem with Placement Groups.” [Online]. Available: http://old.math.nsc.ru/AP/benchmarks/Temporal%20Bin%20Packing/binpack.html.“SCIP. Solving Constraint Integer Programs.” [Online]. Available: https://www.scipopt.org/.“SCIP. Solving Constraint Integer Programs.” [Online]. Available: https://www.scipopt.org/.

The authors declare that there are no conflicts of interest present.