Research On Task Scheduling In Grid Systems Ased On Genetic Algorithm

Task scheduling is a key for large scale computing in grid environment and is also the foundation of grid applications. And in order to make full use of the large computing capacity of grid, research on task cheduling based on the actual characteristics of grid resources is of great important significance. Since task scheduling has been proved to be NP-hard problem, it becomes more complicated when the actual characteristics of grid environment are considered. Currently, many scholars at home and abroad have proposed many heuristic algorithms and most of them can obtain good results. However, many scheduling algorithms usually ignore the data relations and precedence relation between tasks. And many algorithms which consider the precedence relations ususlly neglect the heterogeneity of nodes and communication relations. Thus, they cannot reflect the acutual grid environment and the real characteristics. This paper makes a research on task scheduling problem on the foundation of analyzing this problem in grid eneironment by using the superity when the genetic algorithm is used to solve combination and optimization problems. We first analyze the scheduling strategy and the characteristics of the traditional genetic (called BGA) algorithm and then propose a modified genetic algorithm MGA. The main innovations are given as below:1. A new fitness function is proposed. BGA usually uses the completion time as the fitness fnction; it has the weakness of low searching speed and cannot converge quickly. In this paper, we propose a new fitness function which can search quickly to find the best solution and converge quickly based on analyzation of task scheduling problem in grid enevironment.2. A new crossover operator is proposed. We use different crossover policy to the task sequence and processor sequence to improve the crossover efficiency.3. A new mutation operator is proposed. We use different mutation policy to the task sequence and processor sequence to improve mutation efficiency。 We employment the traditional genetic algorithm and the modified genetic algorithm and compare them using test data. The test result shows that the modified genetic algorithm can shorten the schedule time efficiently and can be used in real grid environment.