The Research On Task Scheduling Based On Genetic Algorithm For Computing Grid

The concept of grid computing is becoming a more and moreimportant one in the high performance computing world and enables thesharing, selection, and aggregation of geographically distributedheterogeneous resources for solving large-scale problems in science,engineering, and commerce. The resources in the grid are heterogeneousand geographically distributed. The management of task scheduling in sucha large-scale distributed environment is a complex problem. And theperformance of task scheduling algorithm will affect the efficiency andthroughput of the grid system directly.Genetic algorithm is a new-style optimizing algoirhtm based onnatural selection theory and natural heredity mechanism, which is simple,current robust,high efficiency and is fit for parellel processing. So, thispaper does research on task scheduling algorithm on the basis of geneticalgorithm. The contributions of this paper are as follows:1. An algorithm based on the virtual deadline in view of the loadbalance among the machines in the grid system is presented, which uses themean slack time to set the priority of each task. This algorithm has betterresults in terms of makespan and load balance compared with otheralgorithms. 2. An algorithm based on immune system theory is brought up. Thisalgorithm expands the variety of population by adjusting the structure ofthe algorithm, and it also improves the local search ability by injectingvaccine operator. It produces better results in terms of schedule length andit also has good convergent speed.3. An algorithm is proposed based on one of the grid trust models afterdoing research on trust definition and models. We design a new codingscheme, and select the corresponding crossover and mutate operators toincrease the diversification. So it can reach a better average trust utilitythan others.4. An algorithm which aims at optimizing the time and budget on thebasis of satisfying the deadline constraint is presented after pointing out theimportance of considering the factor of economy in grid system. Thisalgorithm considers the communication among tasks. It makes up thealgorithms proposed by Buyya which only consider the tasks with nodependencies and which can only consider the time or budgetindependently.