A Dynamic Clustering Heuristic for Jobs Scheduling on Grid Computing Systems

Efficient scheduling has emerged as a fundamental problem in grid computing systems. Since finding an optimal scheduling on the system to minimize the program completion time is a well-known NP-complete problem in general, researchers have resorted to devising efficient heuristics. In this paper, we present a dynamic scheduling heuristic which is appropriate for the grid computing systems, with the goal of building a practical and load balanced system. The goal is realized with four general metrics and two additional restricted metrics, which not only take the communication cost, priority, mutex between jobs into account, but also consider the characteristics of the resource, such as the storage capability and the dynamic characteristic in grid computing system, and the characteristics of the jobs, like the real time limit and the execution variety on different resources. We illustrate that the heuristic exhibits the capability to solve the dynamic resources and jobs, and good performance with load balancing for many cases in grid computing system.