A Deadline-Constrained Scheduling Algorithm for Scientific Workflows in Clouds

Scheduling scientific workflows in clouds under deadline constraint is a challenging problem since public clouds usually provide various types of instances that are rented on-demand and charged based on time period. To solve this problem, the paper proposes DCWS, a deadline-constrained workflow scheduling algorithm for cost-effective execution of scientific workflows in clouds. DCWS is a list-based scheduling algorithm that uses several strategies to reduce the monetary cost under deadline constraint: i) sub-deadlines are assigned for individual tasks by considering the probabilities that tasks are placed together; ii) instance type upgrading and downgrading strategies are designed to accelerate workflow execution and reduce the total cost respectively; iii) task backfilling and sub-deadline violation penalizing are used to improve resource utilization and ensure that the sub-deadlines of the individual tasks are satisfied. Experimental results demonstrate that in comparison with two state-of-the-art algorithms, DCWS is effective on reducing monetary cost under deadline constraint.