Abstract
Load balancing is a very important and complex problem in grid computing. This paper studies Min-min chromosome genetic algorithm (MCGA) to gauge their suitability for solving grid load balancing problems. The effectiveness of the MCGA algorithm is shown for a number of test problems. Performance comparisons with Min-min, and genetic algorithm are also discussed.
Keywords
Introduction
Grid computing originated from a new computing infrastructure for scientific research and cooperation. However, grid computing has different constraints and requirements to those of traditional high performance computing systems. To fully exploit such grid systems, resource management and scheduling are key grid services. In this paper, we propose the use of a genetic algorithm(GA) to find efficient solutions to the grid load balancing problem. A Min-min chromosome genetic algorithm(MCGA) is combined with GA, as well as Min-min, which improves the overall performance of the algorithms.
Min-Min Chromosome Genetic Algorithm
Min-min is a simple algorithm which runs fast and delivers a satisfactory performance. However, the Min-min algorithm is unable to balance the load well since it usually schedules small tasks first. Although GA has a powerful quality of global search, it is liable to raise the problem of premature convergence in the practical application. Thus, we propose to abstract the merit of both Min-min and GA, and a new load balancing algorithm based on grid computing, namely MCGA is proposed. The new algorithm not only retains the advantage of the Min-min algorithm but also achieves the good load balancing.
Experimental Results
We compare MCGA with Min-min algorithm and GA in order to demonstrate MCGA's advantages. The result shows that, with the same tasks and resources, the average resource utilization rate v and load balancing level β of MCGA are the most while the mean square deviation d is the least. In this manner, the result indicates that the general performance of MCGA is prior to Min-min and GA algorithm. In conclusion, MCGA algorithm leads to significant performance gain for a variety of tasks in different scenarios. Through exploiting the merit of the Min-min and GA, MCGA could exert the potential of the efficiency of Min-min and GA to the maximum, and obtaining a better performance than the others.
Conclusion
Results of the experiment show that the MCGA algorithm can be effectively used for grid load balancing. MCGA has shown the better performance than Min-min, GA algorithm.