Development and Performance Analysis of Grid Scheduling Algorithms

Grid scheduling is a vital component of a Grid infrastructure. Reliability, efficiency (in terms of time consumption), effectiveness in resource utilization, and robustness are the desired characteristics of Grid scheduling systems. Many algorithms have been developed for Grid scheduling. En this paper, we propose two new scheduling algorithms (the Multilevel Hybrid Scheduling Algorithm and the Multilevel Dual Queue Scheduling Algorithm) for optimum utilization of CPUs in a master/slave environment. The main idea of the proposed algorithms is to allocate jobs to cluster processors in a circular fashion and execute jobs optimally, i.e. with minimum average waiting, turnaround and response times. To facilitate the research, a software tool has been developed which produces a comprehensive simulation of a number of CPU scheduling algorithms for a clustered system. The tool's output is in the form of scheduling performance metrics.