Time Optimization Heuristics for Scheduling Budget-Constrained Grid Workflows

Workflow scheduling which guarantees anticipated QoS (quality of service) is a fundamental and complex problem in grids. In this paper, the budget-constrained scheduling of workflows represented by DAG (directed acyclic graph) with the objective of time optimization is considered. In general, the optimization problem is NP-hard. Two new iterative heuristics based on priority rules are proposed. According to the property of parallel activities in DAG, two concepts called TL (top level) and BL (bottom level) are defined. By incorporating them with priority rule MP (maximum profit) respectively, two priority rules, i.e. MPTL (maximum profit with top level) and MPBL (maximum profit with bottom level) are designed. They are implemented in iterative heuristics to generate iteratively feasible solutions from leveling-based initial solutions which need bigger total costs. In each step, MPTL and MPBL manage to take into account the maximum decrease in the total cost but the minimum increase of workflow duration. Computational experiments show that MPTL and MPBL can considerably improve the average performance of MP within a few iterations and a little computation time. Moreover, MPBL outperforms MPTL. As well, the impact of budget constraints and the number of Web services on the two heuristics are analyzed.