A Grid Computing Task Scheduling Based On Genetic Algorithm

Advances in wide area network have led to the emergence of a new type of computing model, which is based on a high-performance distributed heterogeneous platform-computational grid. Grid computing is a new computing-framework to meet the growing computational demands. Computational grids provide mechanisms for sharing and accessing large and heterogeneous collections of remote resources. However, how to schedule the subtasks in these heterogeneous resources is a critical problem. Grid scheduling which aims at improving resource utilization and grid application performance is a key concern in grid. Currently, much research can be found about grid scheduling and some algorithms on it were proposed. However, since grid resources are autonomic, distributed and their status change over time, those scheduling algorithms did not fit for the cases well. Task scheduling in Grid computing has been proved to be a NP complete problem. However, in the algorithm of NP complete problem, Genetic Algorithm has been proved an effective algorithm.In this paper, the chromosome coding method and the operator of genetic algorithm are discussed in detail. The task scheduling model is analyzed, and several main kinds of algorithms for tasks scheduling on grid and introduced, which are: SJF, EDF, HPF, First come first serve, Genetic Algorithm, Neural Net Algorithm, Min-min an d Max-min. A scheduling-algorithm based on genetic algorithm (GA) is addressed. The relationship between subtasks can be obtained through the DAG, and then the subtasks are ranked according to their depth-value. Which can avoid the emergence of invalidate chromosomes. In encoding schemes and population initialization, this algorithm, considering the interrelationships among tasks and the algorithmic ability of computing resource, solves lots of problems on wrong chromosome. It employ muti-group on the evolution of population, strengthens the fatherly chromosome combined mode of evolvement, The algorithm presented can overcome premature convergence and find global optima efficiently, decreases the possibilities of premature convergence in local oriental result.