A Fully Hybrid Algorithm for Deadline Constrained Workflow Scheduling in Clouds
Liwen Yang, Yuanqing Xia, Lingjuan Ye, Runze Gao, Yufeng Zhan
Abstract
With the migration of more and more workflows to clouds, the workflow scheduling in clouds (WSC) becomes a critical problem. Although many algorithms have been presented for WSC, there is still room and need for improvement. This paper formulates WSC as a constrained optimization problem that optimizes workflow execution cost within a workflow deadline constraint and proposes a fully hybrid workflow scheduling algorithm, called HPCP-PSO to solve it. Unlike previous works, HPCP-PSO is based on the repeated and alternated execution of two different methods, namely, the heuristic IaaS Cloud Partial Critical Paths (IC-PCP) and meta-heuristic Particle Swarm Optimization (PSO). Moreover, HPCP-PSO incorporates with two novel designs: 1) a new solution encoding strategy not only to sufficiently embody the elasticity of cloud resources, but also to reflect the scheduling relationship between assigned and unassigned tasks; 2) a solution repair strategy on each infeasible lease process to utilize a user-defined deadline more effectively and enhance the solution efficiency of the algorithm. Extensive experiments are conducted on four real-world scientific workflows and the results show that compared with IC-PCP, PSO, and HGSA, the proposed algorithm outperforms them on average by 35.83%, 70.53%, and 87.71% in terms of workflow execution cost.