Grid Task Scheduling Based On Genetic Algorithm

Grid computing is becoming a more and more important in the high performance computing due to the fact that it enables the sharing, selection, and aggregation of geographically distributed heterogeneous resources for solving large-scale problems in the field of science, engineering, and commerce. Task scheduling is an important part of grid computing. Grid task scheduling resolves how to reasonably assign grid resources to tasks, and how to schedule every task to the assigned grid resources. A good scheduling policy can improve the rational allocation and efficient use of grid resources and reduces the overall grid task computing time and cost, making the best performance of the grid. So task scheduling under grid environments is one of the key research fields of grid systems.The main research works of this paper are listed as follows:①The features and common scheduling algorithms of grid task scheduling are analyzed through summarizing the research background and significance of grid computing.②An improved grid task scheduling algorithm based on genetic algorithm is proposed. In the process of population initialization, a new method which combines the Min-Min algorithm and the Max-Min algorithm is addressed, and it uses hamming distance to control the difference among the individuals. Therefore, the new method can not only improve the quality of initial population, but also ensure the diversity of population. In the evolution of the population, a new criterion predicting the premature convergence is presented and the corresponding improved mutation is designed to avoid premature convergence.③The DAG (Directed Acycle Graph) model is adopted to describe the relation among parallel tasks in the genetic algorithm. This kind of model has better capacity to illuminate the actual state of parallel job than the other model. The factor of different processing capacity of CPU is also considered in our algorithm.④Building an actual grid environment is not only expensive but also time-consuming, moreover considering the diversity and dynamic of grid resources, it is quite difficult to confirm the performance and validity of grid task scheduling algorithm through actual grid system. Generally, we use grid simulators to handle with the simulation work. The author does a prototype exeriment of the algorithms on the GridSim simulation platform, and analyzes the exerimental results in detail from the point of view about the makespan.The experimental results are analyzed in detail, and the simulation shows that the improved population initialization method can not only improve the starting point of the algorithm optimization, but also accelerate the speed of algorithm optimization. The improved premature convergence judgement criterion and the corresponding improved mutation can predicte the premature convergence and improve the ability of global optimization. In the grid task scheduling, the proposed algorithm is better than the adaptive genetic algorithm, it can effectively reduce the overall execution time of the total tasks, and have good performance in large-scale grid task scheduling environment, so it can be used in the real grid environment.