Effective Workflow Scheduling in Cloud using Constriction Factor based Inertia Weight Particle Swarm Optimization
Article Sidebar
Main Article Content
Abstract
Cloud computing allows rapid provision of resources based on the need. This enables users to execute the independent tasks and dependent tasks called workflows on the cloud system. Workflow scheduling is a crucial problem that is NP Hard and is still a challenging problem. Particle Swarm Optimization (PSO) is one of the commonly used metaheuristic algorithms for solving task scheduling problems, but it has issues with premature convergence and lack of diversity. In recent years, chaotic maps have been employed in PSO to enhance its performance. This study proposes a Constriction factor-based inertia weight in PSO for workflow scheduling (CFPSO). The proposed algorithm utilizes a constriction factor for updating the inertia weight, which enhances the exploration ability of the algorithm thereby avoid local optima. The algorithm considers a fitness function with an aim to minimize makespan, service cost, and maximize load balance. The proposed algorithm is evaluated using a set of benchmark workflows, and the obtained results are compared with the standard PSO algorithm, Grey Wolf Optimizer (GWO) algorithm and Chaotic PSO algorithm. The extensive experimentation performed show that the proposed algorithm outperforms the other algorithms in terms of makespan, service cost, and load balance. The proposed CFPSO shows reduction of 20% of makespan, 2% of the service cost and 18% load balance rate compared to the conventional algorithms on Montage workflow with 1000 tasks. The use of constriction factor enhances the performance of the algorithm and makes it suitable for solving complex problems with multiple objectives. The proposed algorithm can be used in real-world applications to optimize workflow scheduling in cloud computing environments.
Article Details
References
J. Kennedy and R. Eberhart, “Particle swarm optimization”, Encyclopedia of Machine Learning, pp. 760–766, 2010.
M. Karpagam, K. Geetha, and C. Rajan, “A modified shuffled frog leaping algorithm for scientific workflow scheduling using clustering techniques”, Soft Computing, Vol. 24, No. 1, pp. 637-646, 2020.
A. Mohammadzadeh, M. Masdari, F.S. Gharehchopogh, and A. Jafarian, “A hybrid multi-objective metaheuristic optimization algorithm for scientific workflow scheduling”, Cluster Computing, Vol. 24, No. 2, pp. 1479-1503, 2021.
A. Kaur, P. Singh, R.S. Batth, and C. P. Lim, “Deep?Q learning?based heterogeneous earliest finish time scheduling algorithm for scientific workflows in cloud”, Software: Practice and Experience, Vol. 52, No. 3, pp. 689-709, 2022.
N. Anwar and H. Deng, “A hybrid metaheuristic for multi-objective scientific workflow scheduling in a cloud environment”, Applied sciences, Vol. 8, No. 4, p. 538, 2018.
I. Gupta, M.S. Kumar, and P.K. Jana, “Efficient workflow scheduling algorithm for cloud computing system: a dynamic priority-based approach”, Arabian Journal for Science and Engineering, Vol. 43, No. 12, pp. 7945-7960, 2018.
Xue jun Li, Jia Xu,and Yun Yang, P. Guo and Z. Xue, "An Adaptive PSO Based Real-Time Workflow Scheduling Algorithm in Cloud Systems", 17th IEEE International Conference on Communication Technology, 2017, pp. 1932-1936.
Xuejun Li, Jia Xu,and Yun Yang, "A Chaotic Particle Swarm Optimization-Based Heuristic for Market-Oriented Task-Level Scheduling in Cloud Workflow Systems", Computational Intelligence and Neuroscience, 2015.
Emma Smith, Deep Learning for Gesture Recognition and Human-Computer Interaction , Machine Learning Applications Conference Proceedings, Vol 3 2023.
Ahmad Nickabadi, Mohammad Mehdi Ebadzadeh, Reza Safabakhsh, “A novel particle swarm optimization algorithm with adaptive inertia weight”, Applied Soft Computing, Volume 11, Issue 4, 2011, Pages 3658-3670.
Rui Wang, Kuangrong Hao, Lei Chen, Tong Wang, Chunli Jiang, “A novel hybrid particle swarm optimization using adaptive strategy”, Information Sciences, Volume 579, 2021, Pages 231-250.
Y. Home Prasanna Raju and Nagaraju Devarakonda, “Greedy-Based PSO with Clustering Technique for Cloud Task Scheduling”, Proceedings of International Conference on Computational Intelligence and Data Engineering, pp 133–141, Dec 2020.
Wu, Z., Liu, X., Ni, Z. Dong Y., Yun Yang, “A market-oriented hierarchical scheduling strategy in cloud workflow systems”, Journal of Super computing, 63, 256–293, 2013.
Nuttapong Netjinda, Booncharoen Sirinaovakul, and Tiranee Achalakul, “Cost optimal scheduling in IaaS for dependent workload with particle swarm optimization”, J. Supercomput. 68, 1579–1603, 2014.
Jasim, R. M. . (2023). Hybride Particle Swarm Optimization to Solve Fuzzy Multi-Objective Master Production Scheduling Problems with Application. International Journal of Intelligent Systems and Applications in Engineering, 11(1s), 201–208. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/2493
H. Li, H. Liu and J. Li, "Workflow scheduling algorithm based on control structure reduction in cloud environment," 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), San Diego, CA, USA, pp. 2587-2592, 2014.
M. J. Nadjafi-Arani, S. Doostali and M. Younis, "Workflow Scheduling with Guaranteed Responsiveness and Minimal Cost," in IEEE Transactions on Services Computing, 2022.
Sriperambuduri Vinay Kumar, M Nagaratna, Lakshmi Harika Marrivada, “Task scheduling in cloud computing using PSO algorithm”, Smart Intelligent Computing and Applications, Volume 1: Proceedings of Fifth International Conference on Smart Computing and Informatics (SCI 2021), Springer Nature, 2021.
C.-H. Liu, W.-H. Huang, and P.-C. Chang, “A two-stage AIS approach for grid scheduling problems”, International Journal of Production Research, vol. 50, no. 10, pp. 2665–2680, 2012.
Sriperambuduri Vinay Kumar, M. Nagaratna, “Comparison of Algorithms for Workflow Applications in Cloud Computing”, International Journal of Engineering and Advanced Technology (IJEAT), Volume-11 Issue-1, October 2021.
W.-N. Chen and J. Zhang, “A set-based discrete PSO for cloud workflow scheduling with user-defined Qos constraints,” in Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC ’12), pp. 773–778, 2012.
X. Li, S. Zhou, J. Wang, X. Liu, Yiwen Zhang, Cheng Z., and Yun Yang, “Time-sharing virtual machine based efficient task-level scheduling in scientific cloud workflows”, Future Information Technology, pp. 121–126, Springer, 2014.
P. Hirsch, A. Palfi, and M. Gronalt, “Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry”, International Journal of Production Research, vol. 50, no. 20, pp. 6005–6021, 2012.
Andrew Hernandez, Stephen Wright, Yosef Ben-David, Rodrigo Costa, David Botha. Intelligent Decision Making: Applications of Machine Learning in Decision Science. Kuwait Journal of Machine Learning, 2(3). Retrieved from http://kuwaitjournals.com/index.php/kjml/article/view/197
Sardaraz M, Tahir M., “A parallel multi-objective genetic algorithm for scheduling scientific workflows in cloud computing”, International Journal of Distributed Sensor Networks, 2020.
Henrique Yoshikazu Shishido, Júlio Cezar Estrella, Claudio Fabiano Motta Toledo, Marcio Silva Arantes, “Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds”, Computers & Electrical Engineering, Volume 69, Pages 378-394, 2018.
Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis, “Grey Wolf Optimizer”, Advances in Engineering Software, Volume 69, Pages 46-61, 2014.
Clerc M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization”, Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3, pp. 1951- 1957, 1999.