Алгоритм шаблонизации для динамической задачи упаковки в контейнеры с группами размещения

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

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/.