ISSN 1000-1239 CN 11-1777/TP

• Paper • Previous Articles     Next Articles

Cost Optimization Heuristics for Grid Workflows Scheduling Based on Serial Reduction

Yuan Yingchun1,3, Li Xiaoping1,2, and Wang Qian1,2   

  1. 1(School of Computer Science and Engineering, Southeast University, Nanjing 210096) 2(Ministry of Education Key Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 210096) 3(Faculty of Information Science and Technology, Agriculture University of Hebei, Baoding 071001)
  • Online:2008-02-15

Abstract: 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.

Key words: service grid, directed acyclic graph, workflow, heuristics, serial reduction