TPALA: Two Phase Adaptive Algorithm based on Learning Automata for job scheduling in cloud Environment
محورهای موضوعی : Cloud computing
Abolfazl Esfandi
1
,
Javad Akbari Torkestani
2
,
Abbas Karimi
3
,
Faraneh Zarafshan
4
1 - Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran
2 - Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran
3 - Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran
4 - Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran.
کلید واژه: Cloud Computing, Job scheduling, Learning Automata, Virtual Machine, CloudSim, Simulation,
چکیده مقاله :
Due to the completely random and dynamic nature of the cloud environment, as well as the high volume of jobs, one of the significant challenges in this environment is proper online job scheduling. Most of the algorithms are presented based on heuristic and meta-heuristic approaches, which result in their inability to adapt to the dynamic nature of resources and cloud conditions. In this paper, we present a distributed online algorithm with the use of two different learning automata for each scheduler to schedule the jobs optimally. In this algorithm, the placed workload on every virtual machine is proportional to its computational capacity and changes with time based on the cloud and submitted job conditions. In proposed algorithm, two separate phases and two different LA are used to schedule jobs and allocate each job to the appropriate VM, so that a two phase adaptive algorithm based on LA is presented called TPALA. To demonstrate the effectiveness of our method, several scenarios have been simulated by CloudSim, in which several main metrics such as makespan, success rate, average waiting time, and degree of imbalance will be checked plus their comparison with other existing algorithms. The results show that TPALA performs at least 4.5% better than the closest measured algorithm.
Due to the completely random and dynamic nature of the cloud environment, as well as the high volume of jobs, one of the significant challenges in this environment is proper online job scheduling. Most of the algorithms are presented based on heuristic and meta-heuristic approaches, which result in their inability to adapt to the dynamic nature of resources and cloud conditions. In this paper, we present a distributed online algorithm with the use of two different learning automata for each scheduler to schedule the jobs optimally. In this algorithm, the placed workload on every virtual machine is proportional to its computational capacity and changes with time based on the cloud and submitted job conditions. In proposed algorithm, two separate phases and two different LA are used to schedule jobs and allocate each job to the appropriate VM, so that a two phase adaptive algorithm based on LA is presented called TPALA. To demonstrate the effectiveness of our method, several scenarios have been simulated by CloudSim, in which several main metrics such as makespan, success rate, average waiting time, and degree of imbalance will be checked plus their comparison with other existing algorithms. The results show that TPALA performs at least 4.5% better than the closest measured algorithm.
[1] B. Varghese, and R. Buyya, “Next generation cloud computing: New trends and research directions,” Future Generation Computer Systems, vol. 79, pp. 849-861, 2018.
[2] N. Moganarangan, R. Babukarthik, S. Bhuvaneswari et al., “A novel algorithm for reducing energy-consumption in cloud computing environment: Web service computing approach,” Journal of King Saud University-Computer and Information Sciences, vol. 28, no. 1, pp. 55-67, 2016.
[3] A. Ghaffari, and A. Mahdavi, “Embedding Virtual Machines in Cloud Computing Based on Big Bang–Big Crunch Algorithm,” Journal of Information Systems and Telecommunication (JIST), vol. 28, no. 7, pp. 305-315, 2020.
[4] L. F. Bittencourt, A. Goldman, E. R. Madeira et al., “Scheduling in distributed systems: A cloud computing perspective,” Computer science review, vol. 30, pp. 31-54, 2018.
[5] N. Mansouri, and M. M. Javidi, “Cost-based job scheduling strategy in cloud computing environments,” Distributed and Parallel Databases, pp. 1-36, 2019.
[6] U. Bhoi, and P. N. Ramanuj, “Enhanced max-min task scheduling algorithm in cloud computing,” International Journal of Application or Innovation in Engineering and Management (IJAIEM), vol. 2, no. 4, pp. 259-264, 2013.
[7] Y. Mao, X. Chen, and X. Li, "Max–min task scheduling algorithm for load balance in cloud computing." pp. 457-465, 2014.
[8] S. A. Hamad, and F. A. Omara, “Genetic-based task scheduling algorithm in cloud computing environment,” International Journal of Advanced Computer Science and Applications, vol. 7, no. 4, pp. 550-556, 2016.
[9] A. Kaleeswaran, V. Ramasamy, and P. Vivekanandan, “Dynamic scheduling of data using genetic algorithm in cloud computing,” International Journal of Advances in Engineering & Technology, vol. 5, no. 2, pp. 327, 2013.
[10] H. Aziza, and S. Krichen, “Bi-objective decision support system for task-scheduling based on genetic algorithm in cloud computing,” Computing, vol. 100, no. 2, pp. 65-91, 2018.
[11] B. Keshanchi, A. Souri, and N. J. Navimipour, “An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing,” Journal of Systems and Software, vol. 124, pp. 1-21, 2017.
[12] H. Y. Shishido, J. C. Estrella, C. F. M. Toledo et al., “Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds,” Computers & Electrical Engineering, vol. 69, pp. 378-394, 2018.
[13] M. A. Tawfeek, A. El-Sisi, A. E. Keshk et al., "Cloud task scheduling based on ant colony optimization." pp. 64-69, 2013.
[14] C. Z. a. P. W. C. Liu, “A Task Scheduling Algorithm Based on Genetic Algorithm and Ant Colony Optimization in Cloud Computing,” in 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, Xi'an, China, 2014, pp. 68-72.
[15] X. Wei, “Task scheduling optimization strategy using improved ant colony optimization algorithm in cloud computing,” Journal of Ambient Intelligence and Humanized Computing, 2020/10/21, 2020.
[16] F. Hemasian-Etefagh, and F. Safi-Esfahani, “Dynamic scheduling applying new population grouping of whales meta-heuristic in cloud computing,” The Journal of Supercomputing, vol. 75, no. 10, pp. 6386-6450, 2019.
[17] N. Manikandan, N. Gobalakrishnan, and K. Pradeep, “Bee optimization based random double adaptive whale optimization model for task scheduling in cloud computing environment,” Computer Communications, vol. 187, pp. 35-44, 2022/04/01/, 2022.
[18] Z. Liu, W. Qu, W. Liu et al., “Resource preprocessing and optimal task scheduling in cloud computing environments,” Concurrency and Computation: Practice and Experience, vol. 27, no. 13, pp. 3461-3482, 2015.
[19] V. Priya, and C. N. K. Babu, “Moving average fuzzy resource scheduling for virtualized cloud data services,” Computer Standards & Interfaces, vol. 50, pp. 251-257, 2017.
[20] S. Zhan, and H. Huo, “Improved PSO-based task scheduling algorithm in cloud computing,” Journal of Information & Computational Science, 2012.
[21] A. Kamalinia, and A. Ghaffari, “Hybrid Task Scheduling Method for Cloud Computing by Genetic and PSO Algorithms,” Journal of Information Systems and Telecommunication (JIST), vol. 16, no. 4, pp. 1-10, 2016.
[22] M. Masdari, F. Salehi, M. Jalali et al., “A survey of PSO-based scheduling algorithms in cloud computing,” Journal of Network and Systems Management, vol. 25, no. 1, pp. 122-158, 2017.
[23] G. Babu, and K. Krishnasamy, “Task scheduling algorithm based on Hybrid Particle Swarm Optimization in cloud computing environment,” Journal of Theoretical and Applied Information Technology, vol. 55, pp. 33-38, 2013.
[24] N. Mansouri, B. M. H. Zade, and M. M. Javidi, “Hybrid task scheduling strategy for cloud computing by modified particle swarm optimization and fuzzy theory,” Computers & Industrial Engineering, vol. 130, pp. 597-633, 2019.
[25] X. Chen, and D. Long, “Task scheduling of cloud computing using integrated particle swarm algorithm and ant colony algorithm,” Cluster Computing, vol. 22, no. 2, pp. 2761-2769, 2019/03/01, 2019.
[26] H. Naseri, S. Azizi, and A. Abdollahpouri, “BSFS: A Bidirectional Search Algorithm for Flow Scheduling in Cloud Data Centers,” Journal of Information Systems and Telecommunication (JIST), vol. 27, no. 7, pp. 175-183, 2020.
[27] M. Shojafar, S. Javanmardi, S. Abolfazli et al., “FUGE: A joint meta-heuristic approach to cloud job scheduling algorithm using fuzzy theory and a genetic method,” Cluster Computing, vol. 18, no. 2, pp. 829-844, 2015.
[28] Y. Shi, L. Luo, and H. Guang, "Research on Scheduling of Cloud Manufacturing Resources Based on Bat Algorithm and Cellular Automata." pp. 174-177, 2019.
[29] M. I. Khaleel, “Efficient job scheduling paradigm based on hybrid sparrow search algorithm and differential evolution optimization for heterogeneous cloud computing platforms,” Internet of Things, vol. 22, pp. 100697, 2023/07/01/, 2023.
[30] H. G. S. Phani Praveen, Negar Shahabi, Fatemeh Izanloo, “A Hybrid Gravitational Emulation Local Search-Based Algorithm for Task Scheduling in Cloud Computing,” Mathematical Problems in Engineering, 2023.
[31] S. Sahoo, B. Sahoo, and A. K. Turuk, "An Energy-Efficient Scheduling Framework for Cloud Using Learning Automata." pp. 1-5, 2018.
[32] A. Yazidi, I. Hassan, H. L. Hammer et al., “Achieving Fair Load Balancing by Invoking a Learning Automata-Based Two-Time-Scale Separation Paradigm,” IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 8, pp. 3444-3457, 2021.
[33] L. Zhu, K. Huang, Y. Hu et al., “A Self-Adapting Task Scheduling Algorithm for Container Cloud Using Learning Automata,” IEEE Access, vol. 9, pp. 81236-81252, 2021.
[34] S. A. Murad, A. J. M. Muzahid, Z. R. M. Azmi et al., “A review on job scheduling technique in cloud computing and priority rule based intelligent framework,” Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 6, Part A, pp. 2309-2331, 2022/06/01/, 2022.
[35] M. Masdari, and M. Zangakani, “Efficient task and workflow scheduling in inter-cloud environments: challenges and opportunities,” The Journal of Supercomputing, vol. 76, no. 1, pp. 499-535, 2020.
[36] A. Arunarani, D. Manjula, and V. Sugumaran, “Task scheduling techniques in cloud computing: A literature survey,” Future Generation Computer Systems, vol. 91, pp. 407-415, 2019.
[37] M. A. Rodriguez, and R. Buyya, “A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments,” Concurrency and Computation: Practice and Experience, vol. 29, no. 8, pp. e4041, 2017.
[38] F. Wu, Q. Wu, and Y. Tan, “Workflow scheduling in cloud: a survey,” The Journal of Supercomputing, vol. 71, no. 9, pp. 3373-3418, 2015.
[39] J. Kazemi Kordestani, M. Razapoor Mirsaleh, A. Rezvanian et al., "An Introduction to Learning Automata and Optimization," Advances in Learning Automata and Intelligent Optimization, J. Kazemi Kordestani, M. R. Mirsaleh, A. Rezvanian et al., eds., pp. 1-50, Cham: Springer International Publishing, 2021.
[40] K. S. Narendra, and M. A. Thathachar, “Learning automata-a survey,” IEEE Transactions on systems, man, and cybernetics, no. 4, pp. 323-334, 1974.
[41] K. S. Narendra, and M. A. Thathachar, Learning automata: an introduction: Courier corporation, 2012.
[42] A. Rezvanian, A. M. Saghiri, S. M. Vahidipour et al., Recent advances in learning automata: Springer, 2018.
[43] M. A. L. Thathachar, and B. R. Harita, “Learning automata with changing number of actions,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 17, no. 6, pp. 1095-1100, 1987.
[44] R. N. Calheiros, R. Ranjan, C. A. De Rose et al., “Cloudsim: A novel framework for modeling and simulation of cloud computing infrastructures and services,” arXiv preprint arXiv:0903.2525, 2009.
[45] R. N. Calheiros, R. Ranjan, A. Beloglazov et al., “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” Software: Practice and experience, vol. 41, no. 1, pp. 23-50, 2011.
[46] R. D. Lakshmi, and N. Srinivasu, “A dynamic approach to task scheduling in cloud computing using genetic algorithm,” Journal of Theoretical & Applied Information Technology, vol. 85, no. 2, 2016.
[47] J. Blazewicz, K. H. Ecker, E. Pesch et al., Scheduling Computer and Manufacturing Processes: Springer Science & Business Media, 2013.
