Task Scheduling In Heterogeneous Grid Based On Hybrid Genetic Algorithm

Task scheduling is a focus in the research area of grid computing. And task scheduling based on the actual characteristics of grid resources has important significance for the practical application of high-performance grid. Task scheduling which has been proved to be an NP-hard problem becomes more complicated when consider the actual characteristics of grid resources. Currently, scholars at home and abroad have proposed many heuristic algorithms and obtained good effect. However, many scheduling algorithms often ignore the data connection and precedent restriction among tasks. While some scheduling algorithms based on DAG task scheduling have considered the precedent restriction, they often ignore the heterogeneity among the grid nodes and the communication relationship among tasks, thus can not reflect the real characteristic of grid environment and tasks.This paper makes a research of DAG task graph scheduling with communication in the heterogeneous grid environment, by virtue of the superiority of genetic algorithms in solving combinatorial optimization problems. We give detailed analysis of the scheduling strategies and characteristics of traditional genetic algorithm BGA and list scheduling technology based heuristic scheduling algorithm DLS, and propose an improved method-hybrid genetic algorithm. The main innovations are:1. A preprocess-based population initialization is proposed. Aiming at poor initial population and lack of long evolutionary time of traditional genetic algorithm, our initialization method based on pretreatment of the population fully consider the important degree of tasks and characteristics of heterogeneous grid, make independent tasks to parallelize as much as possible, and then get better initial population. In the situation of the same evolution generation, our method can get a better solution and reduce the evolution time.2. Hybrid crossover operator is proposed. To address the prematurity convergence problem and low efficiency of traditional genetic algorithm when two parent individuals are the same in crossover operator, our hybrid crossover operator takes the character of two parent individuals into account and single parent operation will be done when the two individuals are the same or similar, which can generate new individuals and improve the efficiency of crossover operator.3. Dynamic mutation operator is proposed. Mutation operator of traditional genetic algorithms prone to blindness in later stage of evolution and is difficult to a rapid global convergence. To address above shortcomings, our dynamic mutation operator limit the scope of mutation according to evolutionary stage, do adjacent gene mutation in the later stage of evolution, reduce arbitrariness, and gain a rapid convergence to the global optimal solution.4. A pDLS heuristic operator which can compromise DLS algorithm is proposed. Considering DLS algorithm can achieve better solutions in heterogeneous grid scheduling, this paper compromise some improvement of the DLS operation-pDLS operator after the traditional genetic operators, correct the selected individual with a certain probability, and further optimize the individuals.This paper conducts corresponding experiment simulations and results analysis on the improved hybrid genetic algorithm. The experimental results show that grid task scheduling based on hybrid genetic algorithm can effectively shorten the scheduling time of grid tasks.