A patterning algorithm for the dynamic bin packing problem with placement groups
https://doi.org/10.18255/1818-1015-2025-2-110-131
Abstract
About the Authors
Evgeniy A. BrazhnikovRussian Federation
Artem A. Panin
Russian Federation
Alexey V. Ratushnyi
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