Heuristic scheduling algorithm for cloud workflows with complex structure and deadline constraints

Nowadays, many large-scale scientific workflows are deployed in the cloud which provides a platform to run workflow at lower cost without any infrastructure. However, there are many challenges about how to effectively schedule and deploy workflow applications to guarantee QoS of different users. In this paper, a heuristic scheduling algorithm, named DR-LS (Dependency Relationship-List Scheduling) is proposed to minimize the cost of workflow application while satisfy the user-defined deadline constraint. In the proposed algorithm, we introduce the concept of task dependency during the task priority calculation phase, and use the heuristic method, i.e. Probabilistic Upward Rank to distribute the whole deadline fairly to each task, then select the resources with the least cost increment for the current task to satisfy its corresponding sub-deadline. Our approach is verified by WorkflowSim for four well-known scientific workflows with different sizes, and the experiment results show it outperforms IC-PCP and ProLis, especially for the workflows with complex topological structures, such as Montage.