Evaluating Heuristics for Grid Workflow Scheduling

Job scheduling plays a critical role in utilising resources in grid computing environments. However, the heterogeneity of grid resources adds some challenges to the work of job scheduling especially when jobs have dependencies. It is widely recognised that scheduling m jobs to n resources with an objective to achieve a minimum makespan has shown to be NP-complete requiring the development of heuristics. Although a number of heuristics are available for job scheduling optimisation, selecting the best heuristic to use in a given grid environment remains a difficult problem due to the fact that the performance of each original heuristic is usually evaluated under different assumptions. This paper evaluates 12 representative heuristics for dependent job scheduling under one set of common assumptions. The results are presented and analysed which provides an even basis in comparison of the performance of those heuristics.