Job scheduling heuristics for grid

Abstract

Grid computing can be expressed as a set of services for sharing data, computation capacity and other resources like special equipment. Improvements in networking enabled grid technology to progress quite fast. Resource selection for jobs submitted in a grid, also called matchmaking, is one of the most important tasks needed for operating a grid. Matchmaking is a process that tries to assign jobs to available resources. One important goal of matchmaking is to maximize grid throughput. This is a difficult goal to realize because of the existence of heterogeneous resources in a grid. A widely used approach is Condor’s matchmaking algorithm, which is used by SEE-GRID, EGEE and TR-Grid infrastructures. The goal of this study is to improve this algorithm to obtain better algorithms for the matchmaking process. We propose two new polynomial algorithms for matchmaking. The idea shared by both of our proposed heuristic algorithms is that our heuristics take the collection of jobs and try to match as many jobs to available resources. One of our heuristics, called Scarce Resource First Matchmaking (SRFM), assigns by first trying to match scarce resources. The other heuristic called Linear programming Based Matchmaking (LBM) solves relaxed version of the NP-hard integer program and assigns resources by using relaxed solution values. Our simulation results show that our collective matchmaking schemes work quite well by improving the number of completed jobs.