Enhancing genetic algorithms for dependent job scheduling in grid computing environments

Genetic Algorithms (GAs) are stochastic search techniques based on principles of natural selection and recombination that attempt to find optimal solutions in polynomial time by manipulating a population of candidate solutions. GAs have been widely used for job scheduling optimisation in both homogeneous and heterogeneous computing environments. When compared with list scheduling heuristics, GAs can potentially provide better solutions but require much longer processing time and significant experimentation to determine GA parameters. This paper presents a GA for scheduling dependent jobs in grid computing environments. A number of selection and pre-selection criteria for the GA are evaluated with an aim to improve GA performance in job scheduling optimization. A Task Matching with Data scheme is proposed as a GA mutation operator. Furthermore, the effect of the choice of heuristics for seeding the GA is investigated.