A Hybrid Optimization Algorithm for Large-Scale Combinatorial Problems in Cloud Computing Environments
DOI:
https://doi.org/10.63846/v3km6g84Keywords:
Hybrid optimization, Cloud computing, Combinatorial problems, Task scheduling, Resource allocationAbstract
Combinatorial problems, such as task scheduling and resource allocation, present significant challenges in cloud computing due to the exponential growth of solution spaces. Conventional optimization algorithms often prove inadequate in efficiently handling large-scale problems, resulting in suboptimal resource utilization and increased operational costs. To address these limitations, this study proposes a hybrid optimization algorithm that combines the exploration capabilities of metaheuristic methods with the precision of exact optimization techniques. The proposed approach integrates genetic algorithms (GA) and particle swarm optimization (PSO) with branch-and-bound, facilitating efficient search and refinement of solutions. Furthermore, the algorithm incorporates domain-specific enhancements, including task prioritization heuristics and resource clustering, to reduce computational complexity. Learning-based adaptations, such as reinforcement learning and predictive modeling, are employed to dynamically adjust algorithm parameters and enhance adaptability to varying cloud loads. This ensures real-time responsiveness while maintaining cost-effectiveness. The performance of the hybrid algorithm is evaluated on benchmark datasets and compared with state-of-the-art optimization methods. Experimental results demonstrate significant improvements in scalability, solution quality, and execution time. The algorithm also exhibits robust adaptability to dynamic cloud environments, rendering it a practical and efficient tool for addressing large-scale combinatorial problems. This study highlights the potential of hybrid and adaptive optimization techniques to overcome the challenges of resource management in cloud computing, offering a scalable and cost-effective solution for modern cloud infrastructures.
References
W. C. Chung, T.-F. Wu, Y. Lee, K. C. Huang, H. C. Hsiao, and K. Lai, “Minimizing Resource Waste in Heterogeneous Resource Allocation for Data Stream Processing on Clouds,” Applied Sciences, 2020, doi: 10.3390/app11010149.
I. Petrovska, “Adaptive Resource Allocation Method for Data Processing and Security in Cloud Environment,” Advanced Information Systems, 2023, doi: 10.20998/2522-9052.2023.3.10.
S. Edavalath, “MARCR: Method of Allocating Resources Based on Cost of the Resources in a Heterogeneous Cloud Environment,” The Scientific Temper, 2023, doi: 10.58414/scientifictemper.2023.14.3.03.
R. Nair, “Dynamic Resource Allocation in Cloud Environments,” Int J Res Appl Sci Eng Technol, 2023, doi: 10.22214/ijraset.2023.53668.
Y. Gong, “Dynamic Resource Allocation for Virtual Machine Migration Optimization Using Machine Learning,” Applied and Computational Engineering, 2024, doi: 10.54254/2755-2721/57/20241348.
Y. Ou, “Dynamic Allocation Mechanism of Cloud Computing Resources Driven by Neural Network,” Frontiers in Computing and Intelligent Systems, 2023, doi: 10.54097/fcis.v6i1.03.
Z. Chen, J. Hu, G. Min, C. Luo, and T. El‐Ghazawi, “Adaptive and Efficient Resource Allocation in Cloud Datacenters Using Actor-Critic Deep Reinforcement Learning,” Ieee Transactions on Parallel and Distributed Systems, 2022, doi: 10.1109/tpds.2021.3132422.
T. Kniazhyk and O. Muliarevych, “Cloud Computing With Resource Allocation Based on Ant Colony Optimization,” Advances in Cyber-Physical Systems, 2023, doi: 10.23939/acps2023.02.104.
J. Wang, “Grey Wolf Optimization and Crow Search Algorithm for Resource Allocation Scheme in Cloud Computing,” Multimedia Research, 2021, doi: 10.46253/j.mr.v4i3.a3.
H. Du and J. Chen, “An Improved Ant Colony Algorithm for New Energy Industry Resource Allocation in Cloud Environment,” Tehnicki Vjesnik - Technical Gazette, 2023, doi: 10.17559/tv-20220712164019.
T. N. Gongada, “Optimizing Resource Allocation in Cloud Environments Using Fruit Fly Optimization and Convolutional Neural Networks,” International Journal of Advanced Computer Science and Applications, 2024, doi: 10.14569/ijacsa.2024.01505119.
Y. Wang, “QoS and Energy-Aware Resource Allocation in Cloud Computing Data Centers Using Particle Swarm Optimization Algorithm and Fuzzy Logic System,” International Journal of Advanced Computer Science and Applications, 2023, doi: 10.14569/ijacsa.2023.0141095.
K. Kumain, “Optimization Techniques for Resource Allocation in Cloud Computing Systems,” Turkish Journal of Computer and Mathematics Education (Turcomat), 2020, doi: 10.17762/turcomat.v11i3.13593.
S. Durairaj and S. Ramaswamy, “Task Scheduling to a Virtual Machine Using a Multi‐objective Mayfly Approach for a Cloud Environment,” Concurr Comput, 2022, doi: 10.1002/cpe.7236.
A. B. Tomasaz, R. Cordone, and P. Hosteins, “A Combinatorial Branch and Bound for the Safe Set Problem,” Networks, 2022, doi: 10.1002/net.22140.
J. Nababan, T. Tulus, and Z. Situmorang, “Analysis of Taklinear Performance and Integer Linear Programming Models in Nurses Scheduling Problems,” Sinkron, 2020, doi: 10.33395/sinkron.v4i2.10528.
A. Marendet, A. Goldsztejn, G. Chabert, and C. Jermann, “A Standard Branch-and-Bound Approach for Nonlinear Semi-Infinite Problems,” Eur J Oper Res, 2020, doi: 10.1016/j.ejor.2019.10.025.
N. Kämmerling and J. Kurtz, “Oracle-Based Algorithms for Binary Two-Stage Robust Optimization,” Comput Optim Appl, 2020, doi: 10.1007/s10589-020-00207-w.
Q. Wu, “A Study of the Strategies of the Combinatorial Game,” Applied and Computational Engineering, 2023, doi: 10.54254/2755-2721/17/20230913.
Z. Huang, B. Radunovic, M. Vojnovic, and Q. Zhang, “Communication Complexity of Approximate Maximum Matching in the Message-Passing Model,” Distrib Comput, 2020, doi: 10.1007/s00446-020-00371-6.
Z. Zhang, L. Teng, M. Zhou, J. Wang, and H. Wang, “Enhanced Branch-and-Bound Framework for a Class of Sequencing Problems,” IEEE Trans Syst Man Cybern Syst, 2021, doi: 10.1109/tsmc.2019.2916202.
V. Kovtun, “The Concept of Optimal Planning of a Linearly Oriented Segment of the 5G Network,” PLoS One, 2024, doi: 10.1371/journal.pone.0299000.
A. Ferber, J. Song, B. Dilkina, and Y. Yue, “Learning Pseudo-Backdoors for Mixed Integer Programs,” Proceedings of the International Symposium on Combinatorial Search, 2021, doi: 10.1609/socs.v12i1.18573.
K. Otaki, A. Okada, and H. Yoshida, “Experimental Study on the Information Disclosure Problem: Branch-and-Bound and QUBO Solver,” Front Appl Math Stat, 2023, doi: 10.3389/fams.2023.1150921.
H. Zhang, L. Chen, N. Zhao, Y. Chen, and F. R. Yu, “Interference Management of Analog Function Computation in Multicluster Networks,” Ieee Transactions on Communications, 2022, doi: 10.1109/tcomm.2022.3172996.
Y. Le, J. Li, and J. Chen, “Combinatorial Optimization Design of Search Tree Model Based on Hash Storage,” International Journal of Advanced Computer Science and Applications, 2023, doi: 10.14569/ijacsa.2023.0140574.
H. Havaeji, “Optimizing a Transportation System Using Metaheuristics Approaches (EGD/GA/ACO): A Forest Vehicle Routing Case Study,” World Journal of Engineering and Technology, 2024, doi: 10.4236/wjet.2024.121009.
Y. Shen, M. Liu, J. Yang, Y. Shi, and M. Middendorf, “A Hybrid Swarm Intelligence Algorithm for Vehicle Routing Problem With Time Windows,” Ieee Access, 2020, doi: 10.1109/access.2020.2984660.
L. F. de López, N. G. Blas, and C. M. Lucas, “Ant Colony Systems Optimization Applied to BNF Grammars Rule Derivation (ACORD Algorithm),” Soft comput, 2020, doi: 10.1007/s00500-020-04670-9.
R. Prado‐Rodríguez, “Improved Cooperative Ant Colony Optimization for the Solution of Binary Combinatorial Optimization Applications,” Expert Syst, 2024, doi: 10.1111/exsy.13554.
L. R. Rodrigues, “Defining Optimal Maintenance Scope for Multiple K-Out-of-N Load-Sharing Production Systems Connected in Series Based on RUL Predictions,” Int J Progn Health Manag, 2020, doi: 10.36001/ijphm.2016.v7i3.2408.
D. Ekmekci, “An Adaptive Ant Colony System Memorizing Better Solutions (aACS-MBS) for Traveling Salesman Problem,” Sakarya University Journal of Science, 2021, doi: 10.16984/saufenbilder.822646.
M. Mavrovouniotis, S. Yang, M. Van, C. Li, and M. M. Polycarpou, “Ant Colony Optimization Algorithms for Dynamic Optimization: A Case Study of the Dynamic Travelling Salesperson Problem [Research Frontier],” IEEE Comput Intell Mag, 2020, doi: 10.1109/mci.2019.2954644.
D. Vulakh and R. A. Finkel, “Parallel M-Dimensional Relative Ant Colony Optimization (mDRACO) for the Costas-Array Problem,” Soft comput, 2022, doi: 10.1007/s00500-022-06969-1.
A. H. YILMAZ and Z. Aydın, “Karınca Koloni Algoritmasında Kullanılan Parametrelerin Kafes Sistem Optimizasyonu Üzerinden Irdelenmesi,” Balıkesir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 2022, doi: 10.25092/baunfbed.955408.
T. M. Ngo, “Business Applications of Optimisation Theory: Ant Colony Optimization and Selected Applications in Manufacturing,” International Journal of Research in Commerce and Management Studies, 2023, doi: 10.38193/ijrcms.2023.5412.
A. Chatterjee, E. J. Kim, and H. Reza, “Adaptive Dynamic Probabilistic Elitist Ant Colony Optimization in Traveling Salesman Problem,” SN Comput Sci, 2020, doi: 10.1007/s42979-020-0083-z.
Y. Wang, “Research on Inventory Path Optimization of VMI Large Logistics Enterprises Based on Ant Colony Algorithm,” Journal of Intelligent & Fuzzy Systems, 2021, doi: 10.3233/jifs-219163.
B. Ghimire, “Hybrid Parallel Ant Colony Optimization for Application to Quantum Computing to Solve Large-Scale Combinatorial Optimization Problems,” Applied Sciences, 2023, doi: 10.3390/app132111817.
X. Yu, L. Yu, M. Zheng, L. U. Jun-hui, and L. Zhang, “Firefly Algorithm and Ant Colony Algorithm to Optimize the Traveling Salesman Problem,” J Phys Conf Ser, 2022, doi: 10.1088/1742-6596/2253/1/012010.
A. Ahmid, T.-M. Dao, and N. Van Le, “Enhanced Hyper-Cube Framework Ant Colony Optimization for Combinatorial Optimization Problems,” Algorithms, 2021, doi: 10.3390/a14100286.
J. Bremer and S. Lehnhoff, “Ant Colony Optimization for Feasible Scheduling of Step-Controlled Smart Grid Generation,” Swarm Intelligence, 2021, doi: 10.1007/s11721-021-00204-7.
M. M. Alobaedy, A. A. Khalaf, and Y. Fazea, “Distributed Multi-Ant Colony System Algorithm Using Raspberry Pi Cluster for Travelling Salesman Problem,” Iraqi Journal of Science, 2022, doi: 10.24996/ijs.2022.63.9.35.
M. Cheng, J. Li, P. Bogdan, and S. Nazarian, “H₂o-Cloud: A Resource and Quality of Service-Aware Task Scheduling Framework for Warehouse-Scale Data Centers,” Ieee Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, doi: 10.1109/tcad.2019.2930575.
M. E. Seno, B. N. Dhannoon, and O. K. J. Mohammad, “Enhancement of Cloud Computing Environment Using Machine Learning Algorithms MLCE,” Iraqi Journal of Computer Communication Control and System Engineering, 2023, doi: 10.33103/uot.ijccce.23.4.1.
G. El Haj Ahmed, F. Gil‐Castiñeira, and E. Costa-Montenegro, “KubCG: A Dynamic Kubernetes Scheduler for Heterogeneous Clusters,” Softw Pract Exp, 2020, doi: 10.1002/spe.2898.
G. Rjoub, J. Bentahar, O. A. Wahab, and A. S. Bataineh, “Deep and Reinforcement Learning for Automated Task Scheduling in Large‐scale Cloud Computing Systems,” Concurr Comput, 2020, doi: 10.1002/cpe.5919.
J. Moon, M. Yang, and J. Jeong, “A Novel Approach to the Job Shop Scheduling Problem Based on the Deep Q-Network in a Cooperative Multi-Access Edge Computing Ecosystem,” Sensors, 2021, doi: 10.3390/s21134553.
M. J. Karamthulla, “Optimizing Resource Allocation in Cloud Infrastructure Through AI Automation: A Comparative Study,” Journal of Knowledge Learning and Science Technology Issn 2959-6386 (Online), 2023, doi: 10.60087/jklst.vol2.n2.p326.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Sugiarto
This work is licensed under a Creative Commons Attribution 4.0 International License.
