Reliability-driven scheduling of time/cost-constrained grid workflows

• The method maximizes the workflow reliability while respecting budget and deadline.
• Two heuristics find feasible schedule and one enhances reliability within Ant Colony.
• Real world workflows under various pair of constraints have been investigated.
• Feasibility ratio and workflow execution reliability have been improved.
• The feasibility ratio increment has reduced Grid profit loss.

Workflow scheduling in Grids and Clouds is a NP-Hard problem. Constrained workflow scheduling, arisen in recent years, provides the description of the user requirements through defining constraints on factors like makespan and cost. This paper proposes a scheduling algorithm to maximize the workflow execution reliability while respecting the user-defined deadline and budget. We have used ant colony system to minimize an aggregation of reliability and constraints violation. Three novel heuristics have been proposed which are adaptively selected by ants. Two of them are employed to find feasible schedules and the other is used to enhance the reliability. Two methods have been investigated for time and cost considerations in the resource selection. One of them assigns equal importance to the time and cost factors, and the other weighs them according to the tightness of satisfaction of the corresponding constraints. Simulation results demonstrate the effectiveness of the proposed algorithm in finding feasible schedules with high reliability. As it is shown, as an additional achievement, the Grid profit loss has been decreased.