Use of genetic algorithms for scheduling jobs in large scale grid applications

Abstract

In this paper we present the implementation of Genetic Algorithms (GA) for job scheduling on computational grids that optimizes the makespan and the total flowtime. Job scheduling on computational grids is a key problem in large scale grid‐based applications for solving complex problems. The aim is to obtain an efficient scheduler able to allocate a large number of jobs originated from large scale applications to grid resources. Several variations for GA operators are examined in order to identify which works best for the problem. To this end we have developed a grid simulator package to generate large and very large size instances of the problem and have used them to study the performance of GA implementation. Through extensive experimenting and fine tuning of parameters we have identified the configuration of operators and parameters that outperforms the existing implementations in the literature for static instances of the problem. The experimental results show the robustness of the implementation, improved performance of static instances compared to reported results in the literature and, finally, a fast reduction of the makespan making thus the scheduler of practical interest for grid environments.

Genetinių algoritmų naudojimas kompiuterių tinkluose ir kalendorinis darbų planavimas

Santrauka. Aprašoma, kaip genetinis algoritmas taikomas darbų trukmėms optimizuoti kalendoriniam darbų planavimui, naudojant kompiuterių, sujungtų į tinklą, išteklius. Kalendorinis darbų planavimas, naudojant kompiuterių tinklą, yra aktuali problema, sprendžiant kompleksines, didelio masto problemas. Autorių tikslas ñ sukurti tokį algoritmą, kuris efektyviausiai paskirstytų teikiamų skaičiuoti darbų srautą į kompiuterių tinklą. Ištirti keli algoritmai, išrinktas geriausias. Sukurtas kompiuterių tinklo darbą imituojantis programinis paketas, jis patikrintas, sprendžiant konkrečius uždavinius. Eksperimentuojant rastas geriausias operatorių ir parametrų derinys, o eksperimento rezultatai atskleidė, jog darbų planavimo laikas sutrumpėjo.

Reikšminiai žodžiai: genetinis algoritmas, kalendorinis darbų planavimas, kompiuterių tinklas, pavyzdžiai, darbų trukmė, laikas.

First Published Online: 21 Oct 2010

Keyword : Genetic algorithms, job scheduling, computational grid, large size instances, makespan, flowtime