Cost Optimization Method for Workflows with Deadline Constraints in Grids

Cost optimization for workflow applications with deadline constraints is fundamental and intractable in grids. In this paper, early tree is introduced to find an early feasible schedule for a workflow application. According to the early tree, a cost optimization algorithm is proposed. Taking into account the workflow total float, the workflow deadline is segmented to activity deadlines while keeping precedence constraints. Costs of all activities are locally optimized, so does the workflow cost. Experimental results show that the proposal that this approach can dramatically decrease workflow cost with different deadlines. Moreover, it outperforms other two leveling algorithms in performance on average.