Grid Scheduling Simulation Environment

Dalibor Klusáček, Luděk Matyska, and Hana Rudová
Faculty of Informatics, Masaryk University,
Botanická 68a, 602 00 Brno, Czech Republic

This work concentrates on the design of a system intended
for study of advanced scheduling techniques for planning various types
of jobs in a Grid environment. The solution is able to deal with common
problems of the job scheduling in Grids like heterogeneity of jobs and
resources, and dynamic runtime changes such as arrivals of new jobs.
Our work is based on the GridSim simulation toolkit which we extended
to provide a simulation environment that supports simulation of varying
Grid scheduling problems. To demonstrate the features of the GridSim
environment, we implemented an experimental centralised Grid sched-
uler which uses standard queue-based algorithms as well as advanced 
scheduling techniques for schedule generation.
By now local search based algorithms and some dispatching rules were
tested in comparison with typical queue-based solutions.
The scheduler is capable to handle both static and dynamic situation.
In the static case, all jobs are known in advance while the dynamic
situation means that jobs appear in the system during simulation. In
this case generated schedule is changing through time as some jobs are
already fnished while the new ones are arriving. Comparison of FCFS, EDF, 
Backfilling, Tabu search and dispatching rules is presented for both cases 
and we demonstrate that the Tabu search algorithm provides the best
solution while keeping the algorithm runtime acceptable.