2692-4048ISSN (Online)
2770-0070ISSN (Print)
Volume 15 , Issue 1 , PP: 157-179, 2024 | Cite this article as | XML | Html | PDF | Full Length Article
Heba M. Fadhil 1 *
Doi: https://doi.org/10.54216/FPA.150113
Optimizing system performance in dynamic and heterogeneous environments and the efficient management of computational tasks are crucial. This paper therefore looks at task scheduling and resource allocation algorithms in some depth. The work evaluates five algorithms: Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Firefly Algorithm (FA) and Simulated Annealing (SA) across various workloads achieved by varying the task-to-node ratio. The paper identifies Finish Time and Deadline as two key performance metrics for gauging the efficacy of an algorithm, and a comprehensive investigation of the behaviors of these algorithms across different workloads was carried out. Results from the experiments reveal unique patterns in algorithmic behaviors by workload. In the 15-task and 5-node scenario, the GA and PSO algorithms outclass all others, completing 100 percent of tasks before deadlines, Task 5 was a bane to the ACO algorithm. The study proposes a more extensive system that promotes an adaptive algorithmic approach based on workload characteristics. Numerically, the GA and PSO algorithms triumphed completing 100 percent of tasks before their deadlines in the face of 10 tasks and 5 nodes, while the ACO algorithm stumbled on certain tasks. As it is stated in the study, The above-mentioned system offers an integrated approach to ill-structured problem of task scheduling and resource allocation. It offers an intelligent and aggressive scheduling scheme that runs asynchronously when a higher number of tasks is submitted for the completion in addition to those dynamically aborts whenever system load and utilization cascade excessively. The proposed design seems like full-fledged solution over project scheduling or resource allocation issues. It highlights a detailed method of the choice of algorithms based on semantic features, aiming at flexibility. Effects of producing quantifiable statistical results from the experiments on performance empirically demonstrate each algorithm performed under various settings.
Task Scheduling , Resource Allocation , Metaheuristic , Genetic Algorithms , Particle Swarm Optimization , Ant Colony Optimization , Simulated Annealing.
[1] S. Goyal et al., “An optimized framework for energy-resource allocation in a cloud environment based on the whale optimization algorithm,” Sensors, vol. 21, no. 5, 2021, doi: 10.3390/s21051583.
[2] H. M. Fadhil, M. N. Abdullah, and M. I. Younis, “TWGH: A Tripartite Whale-Gray Wolf-Harmony Algorithm to Minimize Combinatorial Test Suite Problem,” 2022, doi: 10.3390/electronics11182885.
[3] J. Kang and H. Yu, “GPGPU task scheduling technique for reducing the performance deviation of multiple GPGPU tasks in RPC-based GPU virtualization environments,” Symmetry (Basel), vol. 13, no. 3, Mar. 2021, doi: 10.3390/sym13030508.
[4] S. RajPradhan, S. Sharma, D. Konar, and K. Sharma, “A Comparative Study on Dynamic Scheduling of Real-Time Tasks in Multiprocessor System using Genetic Algorithms,” Int J Comput Appl, vol. 120, no. 20, pp. 1–6, Jun. 2015, doi: 10.5120/21340-4346.
[5] “Comparative study on Metaheuristics approaches for solving travels salesman problem... Anas.pdf.”
[6] N. D. Hoang, “Image Processing-Based Pitting Corrosion Detection Using Metaheuristic Optimized Multilevel Image Thresholding and Machine-Learning Approaches,” Math Probl Eng, vol. 2020, 2020, doi: 10.1155/2020/6765274.
[7] E. Silva and P. Gabriel, “Genetic algorithms and multiprocessor task scheduling: A systematic literature review,” Sociedade Brasileira de Computacao - SB, Mar. 2020, pp. 250–261. doi: 10.5753/eniac.2019.9288.
[8] Y. Yun, E. J. Hwang, and Y. H. Kim, “Adaptive genetic algorithm for energy-efficient task scheduling on asymmetric multiprocessor system-on-chip,” Microprocess Microsyst, vol. 66, pp. 19–30, Apr. 2019, doi: 10.1016/j.micpro.2019.01.011.
[9] A. Y. Hamed, M. K. Elnahary, F. S. Alsubaei, and H. H. El-Sayed, “Optimization Task Scheduling Using Cooperation Search Algorithm for Heterogeneous Cloud Computing Systems,” Computers, Materials and Continua, vol. 74, no. 1, pp. 2133–2148, 2023, doi: 10.32604/cmc.2023.032215.
[10] P. Krishnadoss, G. Natesan, J. Ali, M. Nanjappan, P. Krishnamoorthy, and V. K. Poornachary, “CCSA: Hybrid Cuckoo Crow Search Algorithm for Task Scheduling in Cloud Computing,” International Journal of Intelligent Engineering and Systems, vol. 14, no. 4, pp. 241–250, 2021, doi: 10.22266/ijies2021.0831.22.
[11] S. M. Abdulhamid, M. S. Abd Latiff, S. H. H. Madni, and M. Abdullahi, “Fault tolerance aware scheduling technique for cloud computing environment using dynamic clustering algorithm,” Neural Comput Appl, vol. 29, no. 1, 2018, doi: 10.1007/s00521-016-2448-8.
[12] D. Gabi, A. S. Ismail, A. Zainal, and Z. Zakaria, “Solving task scheduling problem in cloud computing environment using orthogonal taguchi-cat algorithm,” International Journal of Electrical and Computer Engineering, vol. 7, no. 3, 2017, doi: 10.11591/ijece.v7i3.pp1489-1497.
[13] M. A. Alworafi, A. Dhari, A. A. Al-Hashmi, Suresha, and A. B. Darem, “Cost-Aware Task Scheduling in Cloud Computing Environment,” International Journal of Computer Network and Information Security, vol. 9, no. 5, 2017, doi: 10.5815/ijcnis.2017.05.07.
[14] R. R. Patel, T. T. Desai, and S. J. Patel, “Scheduling of jobs based on Hungarian method in cloud computing,” in Proceedings of the International Conference on Inventive Communication and Computational Technologies, ICICCT 2017, 2017. doi: 10.1109/ICICCT.2017.7975166.
[15] R. R. Kumar, S. Mishra, and C. Kumar, “A Novel Framework for Cloud Service Evaluation and Selection Using Hybrid MCDM Methods,” Arab J Sci Eng, vol. 43, no. 12, 2018, doi: 10.1007/s13369-017-2975-3.
[16] N. Gobalakrishnan and C. Arun, “A new multi-objective optimal programming model for task scheduling using genetic gray Wolf optimization in cloud computing,” Computer Journal, vol. 61, no. 10, 2018, doi: 10.1093/comjnl/bxy009.
[17] S. Srichandan, T. Ashok Kumar, and S. Bibhudatta, “Task scheduling for cloud computing using multi-objective hybrid bacteria foraging algorithm,” Future Computing and Informatics Journal, vol. 3, no. 2, 2018, doi: 10.1016/j.fcij.2018.03.004.
[18] A. M. Senthil Kumar and M. Venkatesan, “Task scheduling in a cloud computing environment using HGPSO algorithm,” Cluster Comput, vol. 22, 2019, doi: 10.1007/s10586-018-2515-2.
[19] G. Natesan and A. Chokkalingam, “Task scheduling in heterogeneous cloud environment using mean grey wolf optimization algorithm,” ICT Express, vol. 5, no. 2, 2019, doi: 10.1016/j.icte.2018.07.002.
[20] K. V, “A STOCHASTIC DEVELOPMENT OF CLOUD COMPUTING BASED TASK SCHEDULING ALGORITHM,” Journal of Soft Computing Paradigm, vol. 2019, no. 1, 2019, doi: 10.36548/jscp.2019.1.005.
[21] I. Strumberger, M. Tuba, N. Bacanin, and E. Tuba, “Cloudlet scheduling by hybridized monarch butterfly optimization algorithm,” Journal of Sensor and Actuator Networks, vol. 8, no. 3, 2019, doi: 10.3390/jsan8030044.
[22] S. M. G. Kashikolaei, A. A. R. Hosseinabadi, B. Saemi, M. B. Shareh, A. K. Sangaiah, and G. Bin Bian, “An enhancement of task scheduling in cloud computing based on imperialist competitive algorithm and firefly algorithm,” Journal of Supercomputing, vol. 76, no. 8, 2020, doi: 10.1007/s11227-019-02816-7.
[23] P. M. Rekha and M. Dakshayini, “Efficient task allocation approach using genetic algorithm for cloud environment,” Cluster Comput, vol. 22, no. 4, 2019, doi: 10.1007/s10586-019-02909-1.
[24] O. S. Ahmed, F. Fadhil, L. H. J. Alzubaidi, and R. Al-Obaidi, “Fusion Processing Techniques and Bio-inspired Algorithm for E-Communication and Knowledge Transfer,” Fusion: Practice and Applications, vol. 10, no. 1, 2023, doi: 10.54216/FPA.100109.
[25] M. A. S. Mohd Shahrom, N. Zainal, M. F. Mohamad, and S. A. Mostafa, “A Review of Glowworm Swarm Optimization Meta-Heuristic Swarm Intelligence and its Fusion in Various Applications,” Fusion: Practice and Applications, vol. 13, no. 1, 2023, doi: 10.54216/FPA.130107.
[26] J. Santamaría, M. L. Rivero-Cejudo, M. A. Martos-Fernández, and F. Roca, “An overview on the latest nature-inspired and metaheuristics-based image registration algorithms,” Applied Sciences (Switzerland), vol. 10, no. 6, 2020, doi: 10.3390/app10061928.
[27] T. O. Ting, X. S. Yang, S. Cheng, and K. Huang, “Hybrid metaheuristic algorithms: Past, present, and future,” in Studies in Computational Intelligence, vol. 585, Springer Verlag, 2015, pp. 71–83. doi: 10.1007/978-3-319-13826-8_4.
[28] A. Chaparala, “OPTIMIZATION USING EVOLUTIONARY METAHEURISTIC TECHNIQUES: A BRIEF REVIEW,” Brazilian Journal of Operations & Production Management, vol. 15, no. 1, pp. 44–53, 2018, doi: 10.14488/BJOPM.2018.v15.n1.a17.
[29] S. Radhika and A. Chaparala, “Optimization using evolutionary metaheuristic techniques: a brief review,” Brazilian Journal of Operations & Production Management, vol. 15, no. 1, pp. 44–53, May 2018, doi: 10.14488/bjopm.2018.v15.n1.a17.
[30] K. E. Adetunji, I. W. Hofsajer, A. M. Abu-Mahfouz, and L. Cheng, “A Review of Metaheuristic Techniques for Optimal Integration of Electrical Units in Distribution Networks,” IEEE Access, vol. 9, 2021, doi: 10.1109/ACCESS.2020.3048438.
[31] S. Dey, S. De, and S. Bhattacharyya, “Introduction to Hybrid Metaheuristics,” 2018. doi: 10.1142/9789813270237_0001.
[32] G. Ali, “Dynamic Task Scheduling in Multiprocessor Real Time Systems Using Genetic Algorithms,” Journal of Al-Rafidain University College For Sciences ( Print ISSN: 1681-6870 ,Online ISSN: 2790-2293 ), no. 2, pp. 46–65, Oct. 2021, doi: 10.55562/jrucs.v23i2.478.
[33] M. M. Hussain and N. Fujimoto, “GPU-based parallel multi-objective particle swarm optimization for large swarms and high dimensional problems,” Parallel Comput, vol. 92, Apr. 2020, doi: 10.1016/j.parco.2019.102589.
[34] J. Qu, X. Liu, M. Sun, and F. Qi, “GPU-Based Parallel Particle Swarm Optimization Methods for Graph Drawing,” Discrete Dyn Nat Soc, vol. 2017, 2017, doi: 10.1155/2017/2013673.
[35] M. Mavrovouniotis, S. Yang, M. Van, C. Li, and M. Polycarpou, “Ant colony optimization algorithms for dynamic optimization: A case study of the dynamic travelling salesperson problem [Research Frontier],” IEEE Comput Intell Mag, vol. 15, no. 1, pp. 52–63, Feb. 2020, doi: 10.1109/MCI.2019.2954644.
[36] B. A. M. Menezes, H. Kuchen, H. A. Amorim Neto, and F. B. De Lima Neto, “Parallelization Strategies for GPU-Based Ant Colony Optimization Solving the Traveling Salesman Problem,” in 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings, 2019. doi: 10.1109/CEC.2019.8790073.
[37] M. M. Mafarja and S. Mirjalili, “Hybrid whale optimization algorithm with simulated annealing for feature selection,” Neurocomputing, vol. 260, 2017, doi: 10.1016/j.neucom.2017.04.053.
[38] I. A. AbdulJabbar and S. M. Abdullah, “Hybrid Metaheuristic Technique Based Tabu Search and Simulated Annealing,” Engineering and Technology Journal, vol. 35, no. 2B, 2017, doi: 10.30684/etj.2017.138652.
[39] E. Suganya and S. Vijayarani, “Firefly Optimization Algorithm Based Web Scraping for Web Citation Extraction,” Wirel Pers Commun, vol. 118, no. 2, 2021, doi: 10.1007/s11277-021-08093-z.
