Research And Simulation Of Grid Task Scheduling Based On Genetic Algorithm

Grid is an environment that integrates calculation and resources. It can fully absorb all kinds of computing resources and turns them into a computing capability which is easily available, reliable, standardized and economical. In this way, we can share the resources thoroughly. Task scheduling is one of the most important part in grid research, How allocate tasks to different resources in order to make the grid system obtain the highest performance is the problem which the task scheduling needed to resolve. The features of distribution, heterogeneousness, dynamic and self-ruling of grid challenge the traditional scheduling algorithms. So it is very important and realistic to put forward a better scheduling algorithm based on existing algorithms which can make full use of all kinds of resources and improve the throughput of grid system.Genetic algorithm is a new kind of modern heuristics algorithm, which is often used to solve different kinds of NP-complete problems and complex job scheduling problems. Some simulation experiments have confirmed that genetic algorithm is better than classical scheduling algorithms. Because the simple genetic algorithm (SGA) has some defects, such as prematurely convergence and deceptive problem, many academicians committed themselves to the research of improving the genetic algorithm.This thesis analyzes the basic principle of the genetic algorithm and the simulated annealing algorithm (SA) thoroughly. Aiming at the shortage of simple genetic algorithm, this thesis brings forward a kind of hybrid genetic algorithm (HGA). Some improvement is made on the basis of SGA: It learns the Metropolis rule from SA to determine whether to accept a new individual that generated by the crossover or mutation operation. According to the Metropolis rule, the algorithm can accept not only a premium solution, but also a bad solution in a limited probability, so it makes the population having great variety; its crossover probability and the mutation probability are self-adaptive; its genetic operations are also improved properly. Based on characteristics of task scheduling in Grid, we design all the components of HGA at length. On top of that, we perform an experiment based on GridSim to implement the algorithm, and do comparison with SGA and SA in performance. The experiment results show that the hybrid scheduling algorithm that we put forward has a better ability of search and a higher convergence speed.