Grid Resource Scheduling Based On Genetic And Taboo Algorithm

The popularity of the Internet and the availability of powerful computers and high-speed networks as low-cost commodity components make that it is possibly for us to use geographically distributed resource to solve large-scale problems in science, engineering and commerce. The research on these fields has led to the emergence of Grid Computing. An effective and efficient scheduling algorithm is very important to make these distributed resources achieve their promising potentials. Although these traditional scheduling algorithms can work well in old circumstance, they can not work well in the grid circumstances. So, the new and effective scheduling algorithms are needed. This paper is just about scheduling algorithm in grid circumstances.In this paper, the basic knowledge of grid is introduced. The model of scheduling problem and some heuristic algorithms are discussed. Recently, heuristic algorithms are very popular used to solve scheduling problem. Here, two of these heuristic algorithms are introduced more detail i.e. genetic algorithm and taboo algorithm. Genetic algorithm is one of the most important algorithms for solving scheduling problem. Firstly, this paper does some research on existing scheduling algorithms based genetic algorithm. And then some improvements have been presented. There are three improvements. The first one is about initial population. During the phase of create initial population, this paper takes into account the number of operations in each job and the execute-time of each task. Every task is assigned a weight which is based on the two factors and the weight affects the location of the task in queue. The second improvement is about mutation operator. The mutation probability of individual and gene are dynamic. The individual with good fitness and the gene assigned on the resource of big load have good mutation probability. The third improvement is to improve the new individuals with taboo algorithm. Taboo algorithm is also a common heuristic algorithm. Here, it is used to improve the genetic result to get better result.There is an experiment for the three improvements in this paper. During the experiment, the first improvement and the second improvement are tested respectively with the compared genetic algorithm. And then, these two improvements are tested together. At last the three improvements are tested together. The results show that the improved genetic algorithm outperforms the compared algorithm.