The Research On Load Balancing Grid Tasks Scheduling Algorithms

The rapid development networks makes it possible to integrate the geographically distributed and heterogeneous computing resource into tremendous Grid. So the tasks scheduling in Grid has become an important problem. The research of schedule algorithms, which directly related to the speed and quality of grid scheduling, plays a decisive role in the research of Grid computing.Min-Min algorithm, a classic heuristic algorithm, which always schedules the task with shortest completion time, catched a lot of attentions in the field of study for tasks scheduling algorithms in Grid,but it has a limitation that it can't balance the load well. In Grid computing, a good algorithm for task scheduling should not only decrease the makespan of all tasks but also balance the load among the resources in the Grid system.The thesis focuses on the following researches:(1) Since Min-Min algorithm is unable to balance the load well, an improved algorithm is proposed,which introduces the the idea of time sufferage in Max-Int algorithm into the Min-Min algorithm.The improved algorithm K-M-I sets an adjustable parameter k which is a percentage. The parameter k means the ratio of the number of selected tasks from all the tasks to the total task number. Taking advantage of the experiment to test the k on what condition that K-M-I obtains the less makespan.Then comparing the K-M-I with the Min-Min and the Max-Int, we have a conclusion that K-M-I has less makespan and better load balacing than Min-Min algorithm.The statistic from the experiment also showed that K-M-I has better load balancing than Max-Int algorithm.(2) Since Min-Min algorithm doesn't take Quality of Service (QoS) into consideration, the thesis proposed an improved algorithm considering the QoS requirements.The improved algorithm is called Qos guided K-M-I.The idea of improvement is similar to the way that Qos guided Min-Min improves the Min-Min. According to the experimental simulation, we have a conclusion that the improved algorithm K-M-I can reach less makespan and better load balancing and the performance is better than Min-Min algorithm.The statistic from the experiment also proved that K-M-I has better load balancing than QoS guided Min-Min algorithm.