Research On Grid Task Scheduling Based On Distributed Parallel Genetic Algorithm

Grid task scheduling system is an important part of Grid computing system; it is also the key technique to achieve high-performance in grid computing. Because of the strong capability of global searching, genetic algorithms have more advantages than the traditional schedule algorithms when dealing with the task scheduling problems. However, there are some disadvantages in basic genetic algorithm (SGA), such as "premature convergence", low precision of the result and long optimization time. In this paper, we study the approach to realize parallel genetic algorithm, and propose a distributed parallel genetic algorithm which is applied to deal with the grid task scheduling problems. The contributions are as follows:1. Study the principle and process of grid task scheduling, and analyze the existing task scheduling algorithms. We decide to use a task scheduling scheme which is based on genetic algorithms, aiming at the dependent relationship among the sub-tasks in grid environment and realizing the optimal makespan of the task scheduling algorithm.2. Analyze the principle of genetic algorithms. Because of the "premature convergence" and low precision of the result, we introduce the elite mechanism in serial mode to ensure that the optimal result won't be destroyed by the following operations in the process of the evolution. We also analyze the four possible parallelisms of genetic algorithms. From the global parallelism aspect and based on the population grouping parallelism, we propose a distributed parallel genetic algorithm (DPGA). In the DPGA, we introduce an individual migration strategy, by which to improve average fitness and result accuracy.3. Aiming at the characteristics of grid task scheduling, we adopt C language and Message Passing Interface (MPI) to realize DPGA. Let DPGA, EGA and SGA apply to the grid task scheduling problem and simulate in the PC cluster. Analyzed the task scheduling makespan of different scales of tasks, the analysis results show that the DPGA has better search capability and faster convergence rate than EGA and SGA; it can achieve the optimal makespan in dealing with grid task scheduling problem.