Cost Optimization Heuristics for Grid Workflows Scheduling Based on Serial Reduction

Workflow scheduling which guarantees the anticipated QoS (quality of service) is a fundamental and complexity problem in computational grids. In this paper, the scheduling of workflows represented by directed acyclic graph (DAG) with the objective of cost minimization is considered. In general, the optimization problem is NP-hard. Two new heuristics, FSRD (forward serial reduction with deadline) and BSRD (backward serial reduction with deadline) are proposed. According to the property of serial activities, a new concept called series reduction (SR) is defined. The time window for each serial reduction group is recalculated based on leveling algorithms. A dynamic programming method is presented for implementing the cost minimization of each serial reduction group. By integrating the local optimization strategy with two leveling algorithms (DBL and DTL), BSRD and FSRD are investigated. The two heuristics take into account comprehensive serial and parallel properties of DAG, and improve the cost optimization strategies adopted by leveling algorithms. Experimental results show that BSRD and FSRD can considerably improve the average performance of corresponding leveling heuristics. For pipeline workflows, BSRD (FSRD) can achieve the optimal solutions but require a little more computational time. For hybrid workflows, BSRD can save 8.77% average cost of DBL and FSRD can save 6.00% average cost of DTL. Moreover, BSRD outperforms FSRD. As well, the impact of serial reduction ratio on two heuristics is analyzed.