Gradient-Based Scheduler for Scientific Workflows in Cloud Computing
Danjing Wang, Huifang Li, Youwei Zhang, and Baihai Zhang
School of Automation, Beijing Institute of Technology
Beijing 100081, China
It is becoming increasingly attractive to execute workflows in the cloud, as the cloud environment enables scientific applications to utilize elastic computing resources on demand. However, despite being a key to efficiently managing application execution in the cloud, traditional workflow scheduling algorithms face significant challenges in the cloud environment. The gradient-based optimizer (GBO) is a newly proposed evolutionary algorithm with a search engine based on the Newton’s method. It employs a set of vectors to search in the solution space. This study designs a gradient-based scheduler by using GBO for workflow scheduling to minimize the usage costs of workflows under given deadline constraints. Extensive experiments are conducted on well-known scientific workflows of different sizes and types using WorkflowSim. The experimental results show that the proposed scheduling algorithm outperforms five other state-of-the-art algorithms in terms of both the constraint satisfiability and cost optimization, thereby verifying its advantages in addressing workflow scheduling problems.
-  W. Tan and M. Zhou, “Business and Scientific Workflows: A Web Service-Oriented Approach,” IEEE Press, 2013.
-  X. Liu, “Optimization of Load Balancing Scheduling Model for Cloud Computing Resources in Abnormal Network Environment,” J. Adv. Comput. Intell. Intell. Inform., Vol.23, No.2, pp. 356-361, 2019.
-  X. Li and Z. Cai, “Elastic Resource Provisioning for Cloud Workflow Applications,” IEEE Trans. on Automation Science and Engineering, Vol.14, No.2, pp. 1195-1210, 2017.
-  H. Li, D. Wang, G. Xu, Y. Yuan, and Y. Xia, “Improved swarm search algorithm for scheduling budget-constrained workflows in the cloud,” Soft Computing, Vol.26, pp. 3809-3824, 2022.
-  H. Li, G. Xu, D. Wang, M. Zhou, Y. Yuan, and A. Alabdulwahab, “Chaotic-Nondominated-Sorting Owl Search Algorithm for Energy-Aware Multi-Workflow Scheduling in Hybrid Clouds,” IEEE Trans. on Sustainable Computing, Vol.7, No.3, pp. 595-608, 2022.
-  Y. Wang and X. Zuo, “An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules,” IEEE/CAA J. of Automatica Sinica, Vol.8, No.5, pp. 1079-1094, 2021.
-  H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. on Parallel and Distributed Systems, Vol.13, No.3, pp. 260-274, 2002.
-  S. Abrishami, M. Naghibzadeh, and D. H. Epema, “Cost-driven scheduling of grid workflows using partial critical paths,” IEEE Trans. on Parallel and Distributed Systems, Vol.23, No.8, pp. 1400-1414, 2012.
-  Y. Yuan, H. Li, W. Wei, and Z. Lin, “Heuristic Scheduling Algorithm for Cloud Workflows with Complex Structure and Deadline Constraints,” 2019 Chinese Control Conf. (CCC), pp. 2279-2284, 2019.
-  S. Das and P. N. Suganthan, “Differential Evolution: A Survey of the State-of-the-Art,” IEEE Trans. on Evolutionary Computation, Vol.15, No.1, pp. 4-31, 2011.
-  H. Aziza and S. Krichen, “A hybrid genetic algorithm for scientific workflow scheduling in cloud environment,” Neural Computing and Applications, Vol.32, pp. 15263-15278, 2020.
-  M. A. Rodriguez and R. Buyya, “Deadline Based Resource Provisioningand Scheduling Algorithm for Scientific Workflows on Clouds,” IEEE Trans. on Cloud Computing, Vol.2, No.2, pp. 222-235, 2014.
-  H. Li, D. Wang, M. Zhou, Y. Fan, and Y. Xia, “Multi-Swarm Co-Evolution Based Hybrid Intelligent Optimization for Bi-Objective Multi-Workflow Scheduling in the Cloud,” IEEE Trans. on Parallel and Distributed Systems, Vol.33, No.9, pp. 2183-2197, 2022.
-  Z.-G. Chen, Z.-H. Zhan, Y. Lin, Y.-J. Gong, T.-L. Gu, F. Zhao, H.-Q. Yuan, X. Chen, Q. Li, and J. Zhang, “Multiobjective Cloud Workflow Scheduling: A Multiple Populations Ant Colony System Approach,” IEEE Trans. on Cybernetics, Vol.49, No.8, pp. 2912-2926, 2019.
-  S. Benedict, Rejitha R. S, and V. Vasudevan, “An Evolutionary Hybrid Scheduling Algorithm for Computational Grids,” J. Adv. Comput. Intell. Intell. Inform., Vol.12, No.5, pp. 479-484, 2008.
-  W. Guo, B. Lin, G. Chen, Y. Chen, and F. Liang, “Cost-Driven Scheduling for Deadline-Based Workflow Across Multiple Clouds,” IEEE Trans. on Network and Service Management, Vol.15, No.4, pp. 1571-1585, 2018.
-  H. Li, D. Wang, J. R. C. Abreu, Q. Zhao, and O. B. Pineda, “PSO+LOA: hybrid constrained optimization for scheduling scientific workflows in the cloud,” J. of Supercomputing, Vol.77, pp. 13139-13165, 2021.
-  H. Li, B. Wang, Y. Yuan, M. Zhou, Y. Fan, and Y. Xia, “Scoring and Dynamic Hierarchy-Based NSGA-II for Multiobjective Workflow Scheduling in the Cloud,” IEEE Trans. on Automation Science and Engineering, Vol.19, No.2, pp. 982-993, 2022.
-  S. O. H. Madgwick, A. J. L. Harrison, and R. Vaidyanathan, “Estimation of IMU and MARG orientation using a gradient descent algorithm,” 2011 IEEE Int. Conf. on Rehabilitation Robotics, 2011. https://doi.org/10.1109/ICORR.2011.5975346
-  R. J. Kuo and F. E. Zulvia, “The gradient evolution algorithm: A new metaheuristic,” Information Sciences, Vol.316, pp. 246-265, 2015.
-  I. Ahmadianfar, O. Bozorg-Haddad, and X. Chu, “Gradient-based optimizer: A new metaheuristic optimization algorithm,” Information Sciences, Vol.540, pp. 131-159, 2020.
-  D. Wang, H. Li, Y. Zhang, and B. Zhang, “Gradient-Based Optimizer for Scheduling Deadline-Constrained Workflows in the Cloud,” The 7th Int. Workshop on Advanced Computational Intelligence and Intelligent Informatics (IWACIII2021), 2021.
-  W. Chen and E. Deelman, “WorkflowSim: A toolkit for simulating scientific workflows in distributed environments,” 2012 IEEE 8th Int. Conf. on e-Science, 2012. https://doi.org/10.1109/eScience.2012.6404430
-  G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, “Characterizing and profiling scientific workflows,” Future Generation Computer Systems, Vol.29, No.3, pp. 682-692, 2013.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.