Multi-objective adaptive large neighborhood search for virtual machine placement problem

Dindar ÖZ; Tolga Bugra ALTUNTAS; Dindar ÖZ; Tolga Bugra ALTUNTAS

doi:10.3934/jimo.2026134

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 8: 3741-3760. doi: 10.3934/jimo.2026134

Previous Article Next Article

Research article

Multi-objective adaptive large neighborhood search for virtual machine placement problem

Dindar ÖZ ¹,
Tolga Bugra ALTUNTAS ^{1,2
,
,}

1.
Department of Software Engineering, Yaşar University, Turkey
2.
Department of Computer Science, OsloMet - Oslo Metropolitan University, Norway

Received: 13 July 2024 Revised: 12 March 2025 Accepted: 05 June 2026 Published: 16 July 2026
Primary: 90C59, 90C27; Secondary: 90C29

Cloud computing enables the delivery of various services over the Internet. Cloud Service Providers manage these services using Virtual Machines, which emulate physical machines to provide the necessary computing resources. Efficiently managing and allocating these resources is essential for achieving optimal performance and cost-effectiveness. Yet, the increasing complexity and size of cloud environments pose issues for Virtual Machine Placement (VMP), a problem acknowledged as NP-hard because of its complicated and exponentially growing solution space. This paper addresses the multi-objective VMP problem, focusing on energy management and resource utilization. We adapted the Adaptive Large Neighborhood Search (ALSN) algorithm for VMP by using five problem-specific destroy and repair operators to generate new solutions. These operators are selected adaptively by changing their probabilities according to their performance on runtime. Also, a weight value is utilized to improve the spread of solutions on the Pareto set generated by ALNS. To the best of our knowledge, ALNS has never been used in multi-objective VMP. Extensive experiments are conducted on problem instances using both legacy and modern physical machine configurations. The results show that the ALNS algorithm outperforms state-of-the-art algorithms such as the strength Pareto evolutionary algorithm II (SPEA-II), the non-dominated sorting genetic algorithm II (NSGA-II), and the epsilon dominance NSGA-II ($ \epsilon $-NSGAII), achieving up to $ 4.2× $ higher hypervolume in large-scale scenarios and maintaining solution diversity where others fail. The experimental results demonstrate the robustness and adaptability of the ALNS algorithm in varying hardware configurations and large-scale instances.
- virtual machine placement problem,
- multiobjective optimization problem,
- adaptive large neighborhood algorithm,
- cloud computing,
- multiobjective algorithms
Citation: Dindar ÖZ, Tolga Bugra ALTUNTAS. Multi-objective adaptive large neighborhood search for virtual machine placement problem[J]. Journal of Industrial and Management Optimization, 2026, 22(8): 3741-3760. doi: 10.3934/jimo.2026134

Related Papers:

Abstract

Cloud computing enables the delivery of various services over the Internet. Cloud Service Providers manage these services using Virtual Machines, which emulate physical machines to provide the necessary computing resources. Efficiently managing and allocating these resources is essential for achieving optimal performance and cost-effectiveness. Yet, the increasing complexity and size of cloud environments pose issues for Virtual Machine Placement (VMP), a problem acknowledged as NP-hard because of its complicated and exponentially growing solution space. This paper addresses the multi-objective VMP problem, focusing on energy management and resource utilization. We adapted the Adaptive Large Neighborhood Search (ALSN) algorithm for VMP by using five problem-specific destroy and repair operators to generate new solutions. These operators are selected adaptively by changing their probabilities according to their performance on runtime. Also, a weight value is utilized to improve the spread of solutions on the Pareto set generated by ALNS. To the best of our knowledge, ALNS has never been used in multi-objective VMP. Extensive experiments are conducted on problem instances using both legacy and modern physical machine configurations. The results show that the ALNS algorithm outperforms state-of-the-art algorithms such as the strength Pareto evolutionary algorithm II (SPEA-II), the non-dominated sorting genetic algorithm II (NSGA-II), and the epsilon dominance NSGA-II ($ \epsilon $-NSGAII), achieving up to $ 4.2× $ higher hypervolume in large-scale scenarios and maintaining solution diversity where others fail. The experimental results demonstrate the robustness and adaptability of the ALNS algorithm in varying hardware configurations and large-scale instances.

References

[1]	Y. Qin, H. Wang, S. Yi, X. Li, L. Zhai, Virtual machine placement based on multi-objective reinforcement learning, Appl. Intell., 50 (2020), 2370–2383. https://doi.org/10.1007/s10489-020-01633-3 doi: 10.1007/s10489-020-01633-3
[2]	S. Yang, P. Wieder, R. Yahyapour, S. Trajanovski, X. Fu, Reliable Virtual Machine Placement and Routing in Clouds, IEEE Trans. Parallel Distrib. Syst., 28 (2017), 2965–2978. https://doi.org/10.1109/TPDS.2017.2693273 doi: 10.1109/TPDS.2017.2693273
[3]	S. Kumaraswamy, N. Mydhili, Bin packing algorithms for virtual machine placement in cloud computing: A review, Int. J. Electr. Comput. Eng., 9 (2019), 512–524. https://doi.org/10.11591/ijece.v9i1.pp512-524 doi: 10.11591/ijece.v9i1.pp512-524
[4]	T. Tlili, S. Krichen, Best Fit Decreasing Algorithm for Virtual Machine Placement Modeled as a Bin Packing Problem, in 2023 9th International Conference on Control, Decision and Information Technologies (CoDIT), IEEE, Rome, Italy, 2023, 1261–1266. https://doi.org/10.1109/CoDIT58514.2023.10284347
[5]	R. S. Moorthy, U. Fareentaj, T. K. Divya, An Effective Mechanism for Virtual Machine Placement using Aco in IAAS Cloud, IOP Conf. Ser.: Mater. Sci. Eng., 225 (2017), 012227. https://doi.org/10.1088/1757-899X/225/1/012227 doi: 10.1088/1757-899X/225/1/012227
[6]	K. Braiki, H. Youssef, Multi-Objective Virtual Machine Placement Algorithm Based on Particle Swarm Optimization, in 2018 14th International Wireless Communications & Mobile Computing Conference (IWCMC), IEEE, Limassol, 2018,279–284. https://doi.org/10.1109/IWCMC.2018.8450527
[7]	J. Lu, W. Zhao, H. Zhu, J. Li, Z. Cheng, G. Xiao, Optimal machine placement based on improved genetic algorithm in cloud computing, J. Supercomput., 78 (2022), 3448–3476. https://doi.org/10.1007/s11227-021-03953-8 doi: 10.1007/s11227-021-03953-8
[8]	Y. Gao, H. Guan, Z. Qi, Y. Hou, L. Liu, A multi-objective ant colony system algorithm for virtual machine placement in cloud computing, J. Comput. Syst. Sci., 79 (2013), 1230–1242. https://doi.org/10.1016/j.jcss.2013.02.004 doi: 10.1016/j.jcss.2013.02.004
[9]	K. Erdoğdu, K. Karabulut, Bi-objective green vehicle routing problem, Int. Trans. Oper. Res., 29 (2022), 1602–1626. https://doi.org/10.1111/itor.13044 doi: 10.1111/itor.13044
[10]	E. Demir, T. Bektaş, G. Laporte, An adaptive large neighborhood search heuristic for the Pollution-Routing Problem, Eur. J. Oper. Res., 223 (2012), 346–359. https://doi.org/10.1016/j.ejor.2012.06.044 doi: 10.1016/j.ejor.2012.06.044
[11]	S. T. W. Mara, R. Norcahyo, P. Jodiawan, L. Lusiantoro, A. P. Rifai, A survey of adaptive large neighborhood search algorithms and applications, Comput. Oper. Res., 146 (2022), 105903. https://doi.org/10.1016/j.cor.2022.105903 doi: 10.1016/j.cor.2022.105903
[12]	S. Ropke, D. Pisinger, An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, Transp. Sci., 40 (2006), 455–472. https://doi.org/10.1287/trsc.1050.0135 doi: 10.1287/trsc.1050.0135
[13]	S. Challita, F. Paraiso, P. Merle, A Study of Virtual Machine Placement Optimization in Data Centers, in Proceedings of the 7th International Conference on Cloud Computing and Services Science (CLOSER), SciTePress, Porto, Portugal, 2017,343–350. https://doi.org/10.5220/0006236503430350
[14]	S. Azizi, M. Shojafar, J. Abawajy, R. Buyya, GRVMP: A Greedy Randomized Algorithm for Virtual Machine Placement in Cloud Data Centers, IEEE Syst. J., 15 (2021), 2571–2582. https://doi.org/10.1109/JSYST.2020.3002721 doi: 10.1109/JSYST.2020.3002721
[15]	J. Wang, J. Yu, R. Zhai, X. He, Y. Song, GMPR: A Two-Phase Heuristic Algorithm for Virtual Machine Placement in Large-Scale Cloud Data Centers, IEEE Syst. J., 17 (2023), 1419–1430. https://doi.org/10.1109/JSYST.2022.3187971 doi: 10.1109/JSYST.2022.3187971
[16]	K. Braiki, H. Youssef, Fuzzy-logic-based multi-objective best-fit-decreasing virtual machine reallocation, J. Supercomput., 76 (2020), 427–454. https://doi.org/10.1007/s11227-019-03029-8 doi: 10.1007/s11227-019-03029-8
[17]	C. Bhatt, S. Singhal, Multi-objective reinforcement learning for virtual machines placement in cloud computing, Int. J. Adv. Comput. Sci. Appl., 15 (2024). https://doi.org/10.14569/IJACSA.2024.01503105
[18]	D. Pisinger, S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403–2435. https://doi.org/10.1016/j.cor.2005.09.012 doi: 10.1016/j.cor.2005.09.012
[19]	A. P. Rifai, H. T. Nguyen, S. Z. Md Dawal, Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling, Appl. Soft Comput., 40 (2016), 42–57. https://doi.org/10.1016/j.asoc.2015.11.034 doi: 10.1016/j.asoc.2015.11.034
[20]	W. Liao, L. Zhang, Z. Wei, Multi-objective green meal delivery routing problem based on a two-stage solution strategy, J. Clean. Prod., 258 (2020), 120627. https://doi.org/10.1016/j.jclepro.2020.120627 doi: 10.1016/j.jclepro.2020.120627
[21]	J. Dong, H. Wang, S. Cheng, Energy-performance tradeoffs in IaaS cloud with virtual machine scheduling, China Commun., 12 (2015), 155–166. https://doi.org/10.1109/CC.2015.7084410 doi: 10.1109/CC.2015.7084410
[22]	Z. Tang, Y. Mo, K. Li, K. Li, Dynamic forecast scheduling algorithm for virtual machine placement in cloud computing environment, J. Supercomput., 70 (2014), 1279–1296. https://doi.org/10.1007/s11227-014-1227-5 doi: 10.1007/s11227-014-1227-5
[23]	R. Basmadjian, P. Bouvry, G. Da Costa, L. Gyarmati, D. Kliazovich, S. Lafond, et al., Green Data Centers, in Large-Scale Distributed Systems and Energy Efficiency, John Wiley & Sons, 2015,159–196. https://doi.org/10.1002/9781118981122.ch6
[24]	A. Beloglazov, J. Abawajy, R. Buyya, Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing, Future Gener. Comput. Syst., 28 (2012), 755–768. https://doi.org/10.1016/j.future.2011.04.017 doi: 10.1016/j.future.2011.04.017
[25]	E. Falkenauer, A hybrid grouping genetic algorithm for bin packing, J. Heuristics, 2 (1996), 5–30. https://doi.org/10.1007/BF00226291 doi: 10.1007/BF00226291
[26]	E. Zitzler, M. Laumanns, L. Thiele, SPEA2: Improving the Strength Pareto Evolutionary Algorithm, TIK-Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, 2001. https://doi.org/10.3929/ethz-a-004284029
[27]	K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6 (2002), 182–197. https://doi.org/10.1109/4235.996017 doi: 10.1109/4235.996017
[28]	V. Devireddy, P. Reed, Efficient and reliable evolutionary multiobjective optimization using $\epsilon$-dominance archiving and adaptive population sizing, in Genetic and Evolutionary Computation – GECCO 2004, Lecture Notes in Computer Science, vol. 3103, Springer, Berlin, Heidelberg, 2004,390–391. https://doi.org/10.1007/978-3-540-24855-2_38
[29]	N. Riquelme, C. Von Lücken, B. Baran, Performance metrics in multi-objective optimization, in 2015 Latin American Computing Conference (CLEI), IEEE, Arequipa, Peru, 2015, 1–11. https://doi.org/10.1109/CLEI.2015.7360024

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)