Journal
INFORMATION SCIENCES
Volume 179, Issue 15, Pages 2562-2575Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2009.01.035
Keywords
Grid computing; Workflow; Directed acyclic graph; Cost/time tradeoff; Heuristic
Categories
Ask authors/readers for more resources
Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines. (C) 2009 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available