Двухстадийный алгоритм для динамической задачи упаковки в контейнеры с группами размещения

Двухстадийный алгоритм для динамической задачи упаковки в контейнеры с группами размещения

Ратушный А. В., Кочетов Ю. А.
Дискретный анализ и исследование операций, 32, 1, 99-121 (2025)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2025.32.813

Аннотация:

Рассматривается новая задача динамической упаковки в контейнеры, актуальная для облачных вычислений. Для каждого предмета (виртуальной машины) известны время создания, удаления и требуемые ресурсы. Контейнеры (серверы) имеют NUMA-архитектуру и определённые правила при размещении машин. Серверы собраны в стойки, а некоторые машины образуют группы. Каждая группа разделена на партиции. Машины из разных партиций нельзя размещать на одной стойке для обеспечения отказоустойчивости системы. Требуется упаковать все машины в минимальное число стоек на заданном горизонте планирования. Для решения задачи разработан двухстадийный алгоритм: построение начального решения, в котором нарушается часть ограничений, и итеративное улучшение с помощью локального поиска, направленное на устранение нарушений. Применяя предложенный подход на открытых тестовых примерах, удалось достичь среднего отклонения от нижней границы в 3,8%. 

Табл. 3, ил. 4, библиогр. 27.

Литература:
  1. Lameter C. NUMA (Non-uniform memory access): An overview // Queue. 2013. V. 11. P. 40–51. DOI: 10.1145/2508834.2513149.
     
  2. Li P., Wu X., Luo Y., Wang L.-M., Yadav N., Pepin M., Morgan J. NUMAware: Accelerate VM-to-VM I/O performance in NUMA servers for NFV applications // IEEE Conf. Network Function Virtualization and Software Defined Networks (Palo Alto, CA, USA, Nov. 7–9, 2016). Piscataway: IEEE, 2016. URL: nfvsdn2016.ieee-nfvsdn.org/program/demonstrations/index.html (accessed: 20.08.2024).
     
  3. Placement groups for your Amazon EC2 instances // Amazon elastic compute cloud: User guide. Seattle: Amazon Web Serv., 2024. URL: docs.aws. amazon.com/AWSEC2/latest/UserGuide/placement-groups.html (accessed: 20.08.2024).
     
  4. Ratushnyi A. V., Kochetov Yu. A. A column generation based heuristic for a temporal bin packing problem // Mathematical optimization theory and operations research. Proc. 20th Int. Conf. MOTOR 2021 (Irkutsk, Russia, July 5–10, 2021). Cham: Springer, 2021. P. 96–110. (Lect. Notes Comput. Sci.; V. 12755). DOI: 10.1007/978-3-030-77876-7_7.
     
  5. Ratushnyi A. V. A pattern-based heuristic for a temporal bin packing problem with conflicts // Mathematical optimization theory and operations research. Proc. 22nd Int. Conf. MOTOR 2023 (Yekaterinburg, Russia, July 2–8, 2023). Cham: Springer, 2023. P. 161–175. (Commun. Comput. Inf. Sci.; V. 1881). DOI: 10.1007/978-3-031-43257-6_13.
     
  6. Borisovsky P. A., Eremeev A. V., Panin A. A., Sakhno M. A. Temporal bin packing problems with placement constraints: MIP-models and complexity // Mathematical optimization theory and operations research. Proc. 23rd Int. Conf. MOTOR 2024 (Omsk, Russia, June 30 – July 6, 2024). Cham: Springer, 2024. P. 157–169. (Lect. Notes Comput. Sci.; V. 14766). DOI: 10.1007/978-3-031-62792-7_11.
     
  7. Grushin D. A., Kuzyurin N. N. On effective scheduling in computing clusters // Program. Comput. Softw. 2019. V. 45. P. 398–404. DOI: doi.org/10. 1134/S0361768819070077.
     
  8. Spencer K. Y., Tsvetkov P. V., Jarrell J. J. A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects // J. Heuristics. 2019. V. 25. P. 1–45. DOI: 10.1007/s10732-018-9382-0.
     
  9. Li Y., Tang X., Cai W. Dynamic bin packing for on-demand cloud resource allocation // IEEE Trans. Parallel Distrib. Syst. 2016. V. 27, No. 1. P. 157–170. DOI: 10.1109/TPDS.2015.2393868.
     
  10. Gupta N., Gupta K., Gupta D. [et al.]. Enhanced virtualization-based dynamic bin-packing optimized energy management solution for heterogeneous clouds // Math. Probl. Eng. 2022. V. 2022, No. 1. Article ID 8734198. 11 p. DOI: 10.1155/2022/8734198.
     
  11. Beloglazov A., Buyya R. Energy efficient allocation of virtual machines in cloud data centers // 10th IEEE/ACM Int. Conf. Cluster, Cloud and Grid Computing (Melbourne, Australia, May 17–20, 2010). Piscataway: IEEE, 2014. P. 577–578. DOI: 10.1109/CCGRID.2010.45.
     
  12. Berndt S., Jansen K., Klein K.-M. Fully dynamic bin packing revisited // Math. Program. 2020. V. 179. P. 109–155. DOI: 10.1007/s10107-018-1325-x.
     
  13. Murhekar A., Arbour D., Mai T., Rao A. Brief announcement: Dynamic vector bin packing for online resource allocation in the cloud // Proc. 35th ACM Symp. Parallelism in Algorithms and Architectures (Orlando, FL, USA, June 17–19, 2023). New York: ACM, 2023. P. 307–310. DOI: 10.1145/3558481. 3591314.
     
  14. Daudjee K., Kamali S., López-Ortiz A. On the online fault-tolerant server consolidation problem // Proc. 26th ACM Symp. Parallelism in Algorithms and Architectures (Prague, Czech Rep., June 23–25, 2014). New York: ACM, 2014. P. 12–21. DOI: 10.1145/2612669.2612686.
     
  15. Hubbs C., Perez H., Sarwar O., Sahinidis N., Grossmann I., Wassick J. OR-Gym: A reinforcement learning library for operations research problem. Ithaca, NY: Cornell Univ., 2020. 29 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2008.06319). DOI: 10.48550/arXiv.2008.06319.
     
  16. Wan C., Li T., Wang J. RLOR: A flexible framework of deep reinforcement learning for operation research. Ithaca, NY: Cornell Univ., 2023. 21 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2303.13117). DOI: 10.48550/arXiv.2303. 13117.
     
  17. Balaji B., Bell-Masterson J., Bilgin E. [et al.]. ORL: Reinforcement learning benchmarks for online stochastic optimization problems. Ithaca, NY: Cornell Univ., 2019. 12 p. (Cornell Univ. Libr. e-Print Archive; arXiv:1911.10641). DOI: 10.48550/arXiv.1911.10641.
     
  18. Yang T., Luo F., Fuentes J., Ding W., Gu C. A flexible reinforced bin packing framework with automatic slack selection // Math. Probl. Eng. 2021. V. 2021. Article ID 6653586. 15 p. DOI: 10.1155/2021/6653586.
     
  19. Mao F., Blanco E., Fu M. [et al]. Small boxes big data: A deep learning approach to optimize variable sized bin packing // Proc. IEEE 3rd Int. Conf. Big Data Computing Service and Applications (San Francisco, CA, USA, Apr. 6–9, 2017). Piscataway: IEEE, 2017. P. 80–89. DOI: 10.1109/BigDataService. 2017.18.
     
  20. Nomer H. A., Alnowibet K. A., Elsayed A., Mohamed A. W. Neural knapsack: A neural network based solver for the knapsack problem // IEEE Access. 2020. V. 8. P. 224200–224210. DOI: 10.1109/ACCESS.2020.3044005.
     
  21. Toporkov V. V., Yemelyanov D. M., Bulkhak A. N. Machine learningbased online scheduling in distributed computing // Parallel processing and applied mathematics. Rev. Sel. Pap. 14th Int. Conf. PPAM 2022 (Gdansk, Poland, Sept. 11–14, 2022). Pt. II. Cham: Springer, 2023. P. 248–259. (Lect. Notes Comput. Sci.; V. 13827). DOI: 10.1007/978-3-031-30445-3_21.
     
  22. Turnaev A. M., Panin A. A. Stochastic greedy algorithms for a temporal bin packing problem with placement groups // Mathematical optimization theory and operations research. Proc. 23rd Int. Conf. MOTOR 2024 (Omsk, Russia, June 30 – July 6, 2024). Cham: Springer, 2024. P. 199–211. (Lect. Notes Comput. Sci.; V. 14766). DOI: 10.1007/978-3-031-62792-7_14.
     
  23. Johnson D. S. Fast algorithms for bin packing // J. Comput. Syst. Sci. 1974. V. 8. P. 272–314. DOI: 10.1016/S0022-0000(74)80026-7. 24. Amazon EC2 instance types // Amazon elastic compute cloud documentation. Seattle: Amazon Web Serv., 2024. URL: docs.aws.amazon.com/ec2/latest/ instancetypes/instance-types.html (accessed: 20.08.2024).
     
  24. Munien C., Ezugwu A. Metaheuristic algorithms for one-dimensional binpacking problems: A survey of recent advances and applications // J. Intell. Syst. 2021. V. 30. P. 636–663. DOI: 10.1515/jisys-2020-0117.
     
  25. Kosub S. A note on the triangle inequality for the Jaccard distance // Pattern Recognit. Lett. 2019. V. 120. P. 36–38. DOI: 10.1016/j.patrec.2018.12.007.
     
  26. Temporal bin packing problem with placement groups // Discrete location problems. Benchmark library. Novosibirsk: Sobolev Inst. Math., 2024. URL: old.math.nsc.ru/AP/benchmarks/Temporal%20Bin%20Packing/ binpack.html (accessed: 20.08.2024).

Исследование выполнено в рамках гос. задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Ратушный Алексей Владленович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: alexeyratushny@gmail.com

Кочетов Юрий Андреевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: jkochet@math.nsc.ru

Статья поступила 11 сентября 2024 г.
После доработки — 17 сентября 2024 г.
Принята к публикации 22 сентября 2024 г.

Abstract:

A new dynamic bin packing problem relevant to cloud computing is considered. The creation time, deletion time, and required resources are known for each item (virtual machine). The containers (servers) have a NUMA architecture and specific rules for placing the machines. The servers are grouped into racks, and some machines form groups. Each group is divided into partitions. Machines from different partitions cannot be placed on the same rack to ensure system fault tolerance. The objective is to pack all the machines into the minimum number of racks over a given planning horizon. A two-stage algorithm is developed to solve the problem: an initial solution is constructed, where some constraints may be violated, followed by iterative improvement using local search aimed at eliminating the violations. Using the proposed approach, an average deviation of 3.8% from the lower bound was achieved on open test cases. 

Tab. 3, illustr. 4, bibliogr. 27.

References:
  1. C. Lameter, NUMA (Non-uniform memory access): An overview, Queue 11, 40–51 (2013), DOI: 10.1145/2508834.2513149.
     
  2. P. Li, X. Wu, Y. Luo, L.-M. Wang, N. Yadav, M. Pepin, and J. Morgan, NUMAware: Accelerate VM-to-VM I/O performance in NUMA servers for NFV applications, in IEEE Conf. Network Function Virtualization and Software Defined Networks, Palo Alto, CA, USA, Nov. 7–9, 2016 (IEEE, Piscataway, 2016), URL: nfvsdn2016.ieee-nfvsdn.org/program/ demonstrations/index.html (accessed: 20.08.2024).
     
  3. Placement groups for your Amazon EC2 instances, in Amazon Elastic Compute Cloud: User Guide (Amazon Web Serv., Seattle, 2024), URL: docs.aws. amazon.com/AWSEC2/latest/UserGuide/placement-groups.html (accessed: 20.08.2024).
     
  4. A. V. Ratushnyi and Yu. A. Kochetov, A column generation based heuristic for a temporal bin packing problem, in Mathematical Optimization Theory and Operations Research (Proc. 20th Int. Conf. MOTOR 2021, Irkutsk, Russia, July 5–10, 2021) (Springer, Cham, 2021), pp. 96–110 (Lect. Notes Comput. Sci., Vol. 12755), DOI: 10.1007/978-3-030-77876-7_7.
     
  5. A. V. Ratushnyi, A pattern-based heuristic for a temporal bin packing problem with conflicts, in Mathematical Optimization Theory and Operations Research (Proc. 22nd Int. Conf. MOTOR 2023, Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 161–175 (Commun. Comput. Inf. Sci., Vol. 1881), DOI: 10.1007/978-3-031-43257-6_13.
     
  6. P. A. Borisovsky, A. V. Eremeev, A. A. Panin, and M. A. Sakhno, Temporal bin packing problems with placement constraints: MIP-models and complexity, in Mathematical Optimization Theory and Operations Research (Proc. 23rd Int. Conf. MOTOR 2024, Omsk, Russia, June 30 – July 6, 2024) (Springer, Cham, 2024), pp. 157–169 (Lect. Notes Comput. Sci., Vol. 14766), DOI: 10.1007/978-3-031-62792-7_11.
     
  7. D. A. Grushin and N. N. Kuzyurin, On effective scheduling in computing clusters, Program. Comput. Softw. 45, 398–404 (2019), DOI: doi.org/10. 1134/S0361768819070077.
     
  8. K. Y. Spencer, P. V. Tsvetkov, and J. J. Jarrell, A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects, J. Heuristics 25, 1–45 (2019), DOI: 10.1007/s10732-018-9382-0.
     
  9. Y. Li, X. Tang, and W. Cai, Dynamic bin packing for on-demand cloud resource allocation, IEEE Trans. Parallel Distrib. Syst. 27 (1), 157–170 (2016), DOI: 10.1109/TPDS.2015.2393868.
     
  10. N. Gupta, K. Gupta, D. Gupta, [et al.], Enhanced virtualization-based dynamic bin-packing optimized energy management solution for heterogeneous clouds, Math. Probl. Eng. 2022 (1), ID 8734198 (2022), DOI: 10.1155/2022/ 8734198.
     
  11. A. Beloglazov and R. Buyya, Energy efficient allocation of virtual machines in cloud data centers, in 10th IEEE/ACM Int. Conf. Cluster, Cloud and Grid Computing, Melbourne, Australia, May 17–20, 2010 (IEEE, Piscataway, 2014), pp. 577–578, DOI: 10.1109/CCGRID.2010.45.
     
  12. S. Berndt, K. Jansen, and K.-M. Klein, Fully dynamic bin packing revisited, Math. Program. 179, 109–155 (2020), DOI: 10.1007/ s10107-018-1325-x.
     
  13. A. Murhekar, D. Arbour, T. Mai, and A. Rao, Brief announcement: Dynamic vector bin packing for online resource allocation in the cloud, in Proc. 35th ACM Symp. Parallelism in Algorithms and Architectures, Orlando, FL, USA, June 17–19, 2023 (ACM, New York, 2023), pp. 307–310, DOI: 10.1145/ 3558481.3591314.
     
  14. K. Daudjee, S. Kamali, and A. López-Ortiz, On the online fault-tolerant server consolidation problem, in Proc. 26th ACM Symp. Parallelism in Algorithms and Architectures, Prague, Czech Rep., June 23–25, 2014 (ACM, New York, 2014), pp. 12–21, DOI: 10.1145/2612669.2612686.
     
  15. C. Hubbs, H. Perez, O. Sarwar, N. Sahinidis, I. Grossmann, and J. Wassick, OR-Gym: A reinforcement learning library for operations research problem (Cornell Univ., Ithaca, NY, 2020) (Cornell Univ. Libr. e-Print Archive; arXiv:2008.06319), DOI: 10.48550/arXiv.2008.06319.
     
  16. C. Wan, T. Li, and J. Wang, RLOR: A flexible framework of deep reinforcement learning for operation research (Cornell Univ., Ithaca, NY, 2023) (Cornell Univ. Libr. e-Print Archive; arXiv:2303.13117), DOI: 10.48550/arXiv.2303. 13117.
     
  17. B. Balaji, J. Bell-Masterson, E. Bilgin, [et al.], ORL: Reinforcement learning benchmarks for online stochastic optimization problems (Cornell Univ., Ithaca, NY, 2019) (Cornell Univ. Libr. e-Print Archive; arXiv:1911.10641), DOI: 10.48550/arXiv.1911.10641.
     
  18. T. Yang, F. Luo, J. Fuentes, W. Ding, and C. Gu, A flexible reinforced bin packing framework with automatic slack selection, Math. Probl. Eng. 2021, ID 6653586 (2021), DOI: 10.1155/2021/6653586.
     
  19. F. Mao, E. Blanco, M. Fu, [et al], Small boxes big data: A deep learning approach to optimize variable sized bin packing, in Proc. IEEE 3rd Int. Conf. Big Data Computing Service and Applications, San Francisco, CA, USA, Apr. 6–9, 2017 (IEEE, Piscataway, 2017), pp. 80–89, DOI: 10.1109/BigDataService. 2017.18.
     
  20. H. A. Nomer, K. A. Alnowibet, A. Elsayed, and A. W. Mohamed, Neural knapsack: A neural network based solver for the knapsack problem, IEEE Access 8, 224200–224210 (2020), DOI: 10.1109/ACCESS.2020.3044005.
     
  21. V. V. Toporkov, D. M. Yemelyanov, and A. N. Bulkhak, Machine learning-based online scheduling in distributed computing, in Parallel Processing and Applied Mathematics (Rev. Sel. Pap. 14th Int. Conf. PPAM 2022, Gdansk, Poland, Sept. 11–14, 2022) (Springer, Pt. II. Cham, 2023), pp. 248–259 (Lect. Notes Comput. Sci., Vol. 13827), DOI: 10.1007/978-3-031-30445-3_21.
     
  22. A. M. Turnaev and A. A. Panin, Stochastic greedy algorithms for a temporal bin packing problem with placement groups, in Mathematical Optimization Theory and Operations Research (Proc. 23rd Int. Conf. MOTOR 2024, Omsk, Russia, June 30 – July 6, 2024) (Springer, Cham, 2024), pp. 199–211 (Lect. Notes Comput. Sci., Vol. 14766), DOI: 10.1007/978-3-031-62792-7_14.
     
  23. D. S. Johnson, Fast algorithms for bin packing, J. Comput. Syst. Sci. 8, 272–314 (1974), DOI: 10.1016/S0022-0000(74)80026-7.
     
  24. Amazon EC2 instance types, in Amazon Elastic Compute Cloud Documentation (Amazon Web Serv., Seattle, 2024), URL: docs.aws.amazon.com/ec2/ latest/instancetypes/instance-types.html (accessed: 20.08.2024).
     
  25. C. Munien and A. Ezugwu, Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications, J. Intell. Syst. 30, 636–663 (2021), DOI: 10.1515/jisys-2020-0117.
     
  26. S. Kosub, A note on the triangle inequality for the Jaccard distance, Pattern Recognit. Lett. 120, 36–38 (2019), DOI: 10.1016/j.patrec.2018.12.007.
     
  27. Temporal bin packing problem with placement groups, in Discrete Location Problems. Benchmark Library (Sobolev Inst. Math., Novosibirsk, 2024), URL: old.math.nsc.ru/AP/benchmarks/Temporal%20Bin% 20Packing/binpack.html (accessed: 20.08.2024).