A Parallelism-Based Earliest Finish Time (PBEFT) Algorithm for Workflow Scheduling in Clouds

For those public-cloud-based application providers, workflow scheduling in clouds must not only meet traditional performance optimization goals, but also minimize financial costs. This paper focuses on budget-constrained workflow scheduling issue on heterogeneous cloud resources, and tries to minimize the end-to-end delay of the workflow while meeting the given budget. A heuristic algorithm is proposed, which introduces a resource leasing mechanism to maximize the usage of the budget. This paper also defines a scheduling factor parameter consisting of two factors (parallelism and urgency) to determine the scheduled tasks. A scheduling algorithm based on task duplication is designed, which reduces the finish time of workflow tasks by using the idle time slots in existing servers. Finally, compared with contrast algorithms, the experimental results show that the proposed algorithm is superior in both meeting budget constraints and minimizing end-to-end delay.