Multi-objective Memetic Algorithm For Application Research On Grid Job Scheduling

Grid computing became technical innovations in network interconnection era after Internet and Web. According to the demand, grid computing tried to share and integrate all kinds of resources which in the global Internet range including computing resources, data resources, storage resources and communication resources and so on. And effectively polymerization and widely shared is the salient features of these resources which is grid different from other kinds of shared technology.The essence of grid is coordinate resources sharing and collaborative problem solving in the dynamic and cross-organizational virtual organization, the notion that negotiate the sharing and management of resources of resource providers and consumers, and then the resources pool synergy to solve problems. Due to the grid have the dynamic, diversity and self-similarity and autonomy multiple properties, grid environment scheduling problem has become a hot and key spot of research grid system performance.Grid scheduling is an important kind of mechanism in grid system, and also is one of the core grid technologies. The performance of the grid scheduling will directly affect the grid system's efficiency. The main task of grid scheduling is through the optimization of resources and tasks to establish the mapping relation between the tasks set and the resources set, and named grid resources scheduling, resource selection or distribution also. Grid scheduling is a typical NP complete problem, nowadays also have many methods can solve the problem, such as evolutionary algorithm and so on. These algorithms can shorten tasks completion time and improve the efficiency of grid resources scheduling through many experiments. But due to the development of the grid system, there are many influence factors of grid scheduling system efficiency which can not satisfy the required scheduling performance.This paper firstly introduces the grid scheduling related concepts, job scheduling problem of computing grid, multi-objective optimization problem and introduces the basic theory and framework of the evolutionary algorithm. In the paper, we proposed two optimized objectives, makespan and flowtime, of the scheduling problem for grid system. And then we construct the multi-objective optimization model of grid system. This paper also introduces the basic theory and executive process of the Memetic algorithm. And we propose the Memetic algorithm based on grid environment to optimize mentioned two objectives. In this algorithm, redesign and propose the fitness function, crossover and mutation operators and local search strategy according to the characteristics of grid dispatch system. In local search strategy, we designed the two local search algorithms, Hill climbing algorithm and Tabu search algorithm. And in the light of specific grid environment, we have the corresponding experiment. The experimental results shown that compared to Memetic (Hill climbing) and genetic algorithm, Memetic (Tabu search) algorithm applied to the grid scheduling system have better convergence and more efficiency.