A hybrid scheduling technique for grid workflows in advance reservation environments

Scheduling workflows in Grids with the goal of minimizing the completion time is a challenging optimisation problem. Communication times between dependent tasks affect the schedule length only if the tasks are scheduled on different resources, and this makes it difficult to predict the critical path of the scheduled workflow. To address this difficulty, we introduce a new variation of critical path scheduling that ignores communication times between dependent tasks under certain conditions. Furthermore, we propose a hybrid scheduling method that computes five different schedules, based on the combination of two resource selection rules with four job selection rules, and then uses the best of the five. In simulation experiments for workflow scheduling in an advance reservation environment conducted with GridSim, it is shown that the proposed hybrid scheduling method achieves makespan improvements of up to 25.5% on benchmark workflows, compared to previous methods.