Critical Path-Based Iterative Heuristic for Workflow Scheduling in Utility and Cloud Computing

This paper considers the workflow scheduling problem in utility and cloud computing. It deals with the allocation of tasks to suitable resources so as to minimize total rental cost of all resources while maintaining the precedence constraints on one hand and meeting workflow deadlines on the other. A Mixed Integer programming (MILP) model is developed to solve small-size problem instances. In view of its NP-hard nature, a Critical Path-based Iterative (CPI) heuristic is developed to find approximate solutions to large-size problem instances where the multiple complete critical paths are iteratively constructed by Dynamic Programming according to the service assignments for scheduled activities and the longest (cheapest) services for the unscheduled ones. Each critical path optimization problem is relaxed to a Multi-stage Decision Process (MDP) problem and optimized by the proposed dynamic programming based Pareto method. The results of the scheduled critical path are utilized to construct the next new critical path. The iterative process stops as soon as the total duration of the newly found critical path is no more than the deadline of all tasks in the workflow. Extensive experimental results show that the proposed CPI heuristic outperforms the existing state-of-the-art algorithms on most problem instances. For example, compared with an existing PCP (partial critical path based) algorithm, the proposed CPI heuristic achieves a 20.7% decrease in the average normalized resource renting cost for instances with 1,000 activities.