JOB SCHEDULING IN COMPUTATIONAL GRID USING GENETIC ALGORITHMS

Mohsin Saleem, Savitri Bevinakoppa

2005

Abstract

The computational Grid is a collection of heterogeneous computing resources connected via networks to provide computation for the high-performance execution of applications. To achieve this high-performance, an important factor is the scheduling of the applications/jobs on the compute resources. Scheduling of jobs is challenging because of the heterogeneity and dynamic behaviour of the Grid resources. Moreover the jobs to be scheduled also have varied computational requirements. In general the scheduling problem is NP-complete. For such problems, Genetic Algorithms (GAs) are reckoned as useful tools to find high-quality solutions. In this paper, a customised form of GAs is used to find suboptimal schedules for the execution of independent jobs, with no inter-communications, in the computational Grid environment with the objective of minimising the makespan (total execution time of the jobs onto the resources). Further, while using the GA-based approach the solution is encoded in the form of chromosome, which not only represents the allocation of the jobs onto the resources but also specifies the order in which the jobs have to be executed. Simple genetic operators i.e., crossover and mutation are used. The selection is done on the using Tournament Selection and Elitism strategies. It was observed that the specification of order of the jobs to be executed on the Grid resources played a significant role in minimising the makespan. The results obtained from the experiments performed were also compared with other heuristics and the GA-based approach by other researchers for job-scheduling in the computational Grid environment. It was observed that the GA-based approach used in this paper was able to achieve much better performance in terms of makespan.

Paper Citation

in Harvard Style

Saleem M. and Bevinakoppa S. (2005). JOB SCHEDULING IN COMPUTATIONAL GRID USING GENETIC ALGORITHMS . In Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 4: ICEIS, ISBN 972-8865-19-8, pages 163-169. DOI: 10.5220/0002537501630169

in Bibtex Style

@conference{iceis05,
author={Mohsin Saleem and Savitri Bevinakoppa},
title={JOB SCHEDULING IN COMPUTATIONAL GRID USING GENETIC ALGORITHMS},
booktitle={Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 4: ICEIS,},
year={2005},
pages={163-169},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002537501630169},
isbn={972-8865-19-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 4: ICEIS,
TI - JOB SCHEDULING IN COMPUTATIONAL GRID USING GENETIC ALGORITHMS
SN - 972-8865-19-8
AU - Saleem M.
AU - Bevinakoppa S.
PY - 2005
SP - 163
EP - 169
DO - 10.5220/0002537501630169