УДК 517.977
MSC: 80M50, 90C27
DOI: 10.21538/0134-4889-2024-30-1-109-127
Работа выполнена в рамках государственного задания ИМ СО РАН (FWNF 2022-0019)
Рассматривается новая задача динамической упаковки в контейнеры, возникающая в облачных вычислениях. Имеется конечное множество виртуальных машин. Для каждой машины задано временное окно для обслуживания и два размера: число ядер и объем оперативной памяти. Все машины делятся на два типа: большие и малые. Каждый сервер состоит их двух одинаковых узлов. Малые машины помещаются полностью на один из них. Большие машины делятся пополам и помещаются на оба узла. Требуется разместить все машины в минимальное число серверов. Для решения задачи разработана эвристика, основанная на методе генерации столбцов. Для получения нижних оценок оптимума выбираются моменты времени с большой суммарной нагрузкой и для них решается статическая задача. Для построения верхних оценок решение статической задачи расширяется на все моменты времени известным алгоритмом “Первый подходящий” (First Fit). Приводятся теоретические утверждения о точности оценок в худшем случае. Вычислительные эксперименты для реальных тестовых примеров указывают на небольшой разрыв между границами, не более 0.9% для недельного интервала, 50000 машин и среднем времени расчетов 26 с на персональном компьютере. В работе удалось улучшить некоторые известные результаты на открытых примерах.
Ключевые слова: задача о рюкзаке, метод генерации столбцов, NUMA-архитектура, виртуальная машина
СПИСОК ЛИТЕРАТУРЫ
1. Johnson D.S. Near-optimal bin packing algorithms: Ph.D. dissertation / Department of Mathematics, Massachusetts Institute of Technology. Cambridge: MA, 1973.
2. Christensen H.I., Khan A., Pokutta S., Tetali P. Multidimensional bin packing and other related problems: A survey // Computer Science Review. 2017. Vol. 24. P. 63–79. doi: 10.1016/j.cosrev.2016.12.001
3. Aggoun A., Rhiat A., Fages A. Panorama of real-life applications in logistics embedding bin packing optimization algorithms, robotics and cloud computing technologies // Proc. of 3rd Internat. Conf. on Logistics Operations Management (GOL). 2016. P. 1–4. doi: 10.1109/GOL.2016.7731693
4. Shi J., Luo J., Dong F., Jin J., Shen J. Fast multi-resource allocation with patterns in large scale cloud data center // J. Comput. Sci. 2018. Vol. 26. P. 389–401. doi: 10.1016/j.jocs.2017.05.005
5. Furini F., Shen X. Matheuristics for the temporal bin packing problem // Oper. Res./Comput. Sci. Interfaces Series (book series). 2018. Vol. 62. P. 333–345. doi: 10.1007/978-3-319-58253-5_19
6. Aydin N., Muter I., Birbil I.S. Multi-objective temporal bin packing proble: An application in cloud computing // Comput. Oper. Res. 2021. Vol. 121. Article no. 104959. doi: 10.1016/j.cor.2020.104959
7. de Cauwer M., Mehta D., O’Sullivan B. The temporal bin packing problem: An application to workload management in data centres. // IEEE 28th Internat. Conf. on Tools with Artificial Intelligence (ICTAI 2016). P. 157–164. doi: 10.1109/ICTAI.2016.0033
8. Bartlett M., Frisch A.M., Hamadi Y., Miguel I., Tarim S.A., Unsworth C. The Temporal Knapsack Problem and its solution // Proc. of the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: Second Internat. Conf. (CPAIOR 2005) / eds. R. Barták, M. Milano. Berlin; Heidelberg: Springer, 2005. P. 34–48. (Lecture Notes in Comp. Sci. 2005; vol. 3524). doi:10.1007/11293853_5
9. Caprara A., Furini F., Malaguti E. Uncommon Dantzig–Wolfe reformulation for the Temporal Knapsack Problem // INFORMS J. Comput. 2013. Vol. 25. P. 560–571. doi: 10.1287/ijoc.1120.0521
10. Pires F.L., Baran B. A virtual machine placement taxonomy // Proc. of the 15th IEEE/ACM Internat. Symposium on Cluster, Cloud, and Grid Computing. 2015. P. 159–168. doi: 10.1109/CCGrid.2015.15
11. Wolsey L.A. Valid inequalities, covering problems and discrete dynamic programs // Annal. Discrete Math. 1977. Vol. 1. P. 527–538. doi: 10.1016/S0167-5060(08)70758-1
12. Clautiaux F., Sadykov R., Vanderbeck F., Viaud Q. Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem // Discr. Optim. 2018. Vol. 29. P. 18–44. doi: 10.1016/j.disopt.2018.02.003
13. Delorme M., Iori M., Martello S. Bin packing and cutting stock problems: mathematical models and exact algorithms // Eur. J. Oper. Res. 2016. Vol. 255. P. 1–20. doi:10.1016/j.ejor.2016.04.030
14. Macedo R., Alves C., Valério de Carvalho J.M. Arc-flow model for the two-dimensional guillotine cutting stock problem // Comput. Oper. Res. 2010. Vol. 37. P. 991–1001.
15. Martinovic J., Scheithauer G. Integer linear programming models for the skiving stock problem // Eur. J. Oper. Res. 2016. Vol. 251, no. 2. P. 356–368. doi: 10.1016/j.ejor.2015.11.005
16. Valério de Carvalho J.M. Exact solution of cutting stock problems using column generation and branch-and-bound // Int. Trans. Oper. Res. 1998. Vol. 5. P. 35–44.
17. Brandao F., Pedroso J.P. Bin packing and related problems: general arc-flow formulation with graph compression // Comput. Oper. Res. 2016. Vol. 69. P. 56–67. doi: 10.1016/j.cor.2015.11.009
18. Delorme M., Iori M. Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems // INFORMS J. Comput. 2020. Vol. 32, no. 1. P. 101–119. doi: 10.1287/ijoc.2018.0880
19. Cote J.-F., Iori M. The meet-in-the-middle principle for cutting and packing problems // INFORMS J. Comput. 2018. Vol. 30, no. 4. P. 625–786 . doi: 10.1287/ijoc.2018.0806
20. Dell’Amico M., Furini F., Iori M. A branch-and-price algorithm for the temporal bin packing problem // Comput. Oper. Res. 2020. Vol. 112. Article no. 104825. doi: 10.1016/j.cor.2019.104825
21. Martinovic J., Strasdat N., Selch M. Compact Integer Linear Programming Formulations for the temporal bin packing problem with fire-ups // Comput. Oper. Res. 2021. Vol. 132. Article no. 105288. doi: 10.1016/j.cor.2021.105288
22. Martinovic J., Strasdat N., Valerio de Carvalho J.M., Furini F. Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups // Optim. Letters. 2021. Vol. 16. P. 2333–2358. doi: 10.1007/s11590-021-01825-x
23. Martinovic J., Strasdat N. Theoretical insights and a new class of valid inequalities for the temporal bin packing problem with fire-ups. Preprint MATH-NM-01-2022 / Technische Universitat Dresden. 2022. Available at: http://www.optimization-online.org/DB_HTML/2022/02/8791.html
24. Valerio de Carvalho J.M. LP Models for bin packing and cutting stock problems // Eur. J. Oper. Res. 2002. Vol. 141, no. 2. P. 253–273. doi: 10.1016/S0377-2217(02)00124-8
25. Manchanda N., Anand K. Non-uniform memory access (NUMA). NY: New York University, 2014.
26. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin, Heidelberg: Springer, 2004. 548 p. doi: 10.1007/978-3-540-24777-7
27. Канторович Л.В., Залгаллер В.А. Расчет рационального раскроя промышленных материалов. Л.: Лениздат, 1951. 198 с.
28. Johnson D.S. Fast algorithms for bin packing // J. Comp. System Sci. 1974. Vol. 8, no. 3. P. 272–314. doi: 10.1016/S0022-0000(74)80026-7
29. Ratushnyi A., Kochetov Y. A column generation based heuristic for a temporal bin packing problem // Mathematical Optimization Theory and Operations Research: Proc. of 20th Internat. Conf. (MOTOR 2021) / eds. P. Pardalos, M. Khachay, A. Kazakov. 2021. P. 96–110. (Lecture Notes Comp. Sci.; vol. 12755). doi: 10.1007/978-3-030-77876-7_7
30. Mathematical Optimization Theory and Operations Research: Proc. of 20th Internat. Conf. (MOTOR 2021) / eds. P. Pardalos, M. Khachay, A. Kazakov. Cham: Springer, 2021. 493 p. doi: 10.1007/978-3-030-77876-7
31. Ratushnyi A. A pattern-based heuristic for a temporal bin packing problem with conflicts // Mathematical Optimization Theory and Operations Research: Recent Trends: Proc. of 22nd Internat. Conf. (MOTOR 2023) / eds. M. Khachay et al. 2023. P. 152–166. (Communications in Computer and Information Sci.; vol. 1881). doi: 10.1007/978-3-031-43257-6_13
32. Martello S., Toth P. Lower bounds and reduction procedures for the bin packing problem // Discrete Appl. Math. 1990. Vol. 28. P. 59–70.
33. Kochetov Yu., Kondakov A. A hybrid VNS matheuristic for a bin packing problem with a color constraint // Yugoslav J. Oper. Res. 2021. Vol. 31, no. 3. P. 285–298. doi:10.2298/YJOR200117009K
34. Gurobi optimization: Gurobi optimizer reference manual. 2021. Available at: http://www.gurobi.com .
35. Scheithauer G., Terno J. The modified integer round-up property of the one- dimensional cutting stock problem // Eur. J. Oper. Res. 1995. Vol. 84. P. 562–571.
Поступила 30.05.2023
После доработки 18.09.2023
Принята к публикации 2.10.2023
Кочетов Юрий Андреевич
д-р физ.-мат. наук, профессор
главный науч. сотрудник
Институт математики имени С.Л. Соболева СО РАН
г. Новосибирск
e-mail: jkochet@math.nsc.ru
Ратушный Алексей Владленович
аспирант
Институт математики имени С.Л. Соболева СО РАН
г. Новосибирск
e-mail: alexeyratushny@gmail.com
Ссылка на статью: Ю.А. Кочетов, А.В. Ратушный. Верхние и нижние оценки оптимума для задачи динамической упаковки в контейнеры // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 1. С. 109-127
English
Yu.A. Kochetov, A.V. Ratushnyi. Upper and lower bounds for the optimum in a temporal bin packing problem
A new temporal bin packing problem originating from cloud computing is introduced. There is a finite set of virtual machines. For each machine, the time window for processing, the number of cores, and the RAM size are known. Each machine can be of one of two types: large or small. Each server consists of two identical nodes. Each small machine is placed completely on one of the nodes, and each large machine is divided into two identical parts placed on both nodes of a server. The goal is to pack all the machines into the minimum number of servers. For this problem, we develop a heuristic based on the column generation method. To get lower bounds of the optimum, we choose the times with the greatest total load and solve the static problem for them. To derive upper bounds, we extend the solution of the static problem to all times using the well-known First Fit algorithm. Computational experiments for real test instances indicate a small gap between the bounds, which is at most 0.9% for a week horizon, 50 000 machines, and 26 s average running time on a personal computer. We manage to improve some well-known results for open instances.
Keywords: knapsack problem, column generation method, NUMA architecture, virtual machine
Received May 30, 2023
Revised September 18, 2023
Accepted October 2, 2023
Funding Agency: The research was carried out within the State Contract of the Sobolev Institute of Mathematics (FWNF-2022-0019).
Yury Andreevich Kochetov, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberia Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: jkochet@math.nsc.ru
Alexey Vladlenovich Ratushnyi, doctoral student, Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia, e-mail: alexeyratushny@gmail.com
Cite this article as: Yu.A. Kochetov, A.V. Ratushnyi. Upper and lower bounds for the optimum in a temporal bin packing problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 30, no. 1, pp. 109–127.
[References -> on the "English" button bottom right]
