Grid Computing Heuristic Task Scheduling Algorithm Research And Simulation, In Gridsim

With the fast development of internet technology, Grid Computing is becoming a new style of distributed computing mode, which aims at realizing large-scale distributed resource sharing and collaborative problems solved. An effective task scheduling algorithm can make the best of grid resources in order to improve application running performance, which is the reason why task scheduling is the core technology in Grid Computing. However, the characteristics of dynamicity, heterogeneity and autonomy of grid resources make task scheduling under grid environment much more complex, so how to develop an effective task scheduling algorithm is a challenge that Grid Computing confronts with.Task scheduling problem has been proved to be NP hard, so most task scheduling algorithms are mainly based on heuristics method. This paper focuses on heuristics meta-task scheduling, on the basis of introducing task scheduling concept, principles, and goals. The contributions of this paper are listed as following:1. Make a brief introduction of research context and current study situation of Grid Computing and task scheduling, and detail the related theory of Grid Computing and task scheduling.2. Make an intensive study on the scheduling principles of Min-Min and Sufferage algorithm. The analysis concludes, Min-Min algorithm has a shorter task waiting time, but suffers an unsatisfying makespan. Whereas, Sufferage algorithm can acquire a satisfying makespan, but suffers a longer task waiting time. So when grid users have constraints both on makespan and task waiting time, these two algorithms cannot facilitate strong usability.3. In order to solve the insufficiency of only comparing the difference between the second minimum completion time and minimum completion time of each task of Sufferage algorithm while handling resource competition among tasks, this paper brings up MD-Sufferage algorithm. The execution procedure of MD-Sufferage algorithm is:Firstly sort the completion time of tasks in ascending order, and then calculate the differences between all completion time and minimum completion time. Secondly, while handling resource competition among tasks, not only compare the difference between the second minimum completion time and minimum completion time of each task, but also the differences between all completion time and minimum completion time orderly.4. In order to guarantee relatively short task waiting time while shortening makespan, this paper brings up WTMB (Waiting Time and Makespan Balance) algorithm. The execution procedure of WTMB algorithm is:Considering the impact of task execution time variance on scheduling performance, firstly calculate the execution time variance of all tasks. Secondly divide the scheduling set into high variance set and low variance set according to the average execution time variance. At last, schedule these two subsets in turns until all tasks have been scheduled. During each turn of scheduling these two subsets, firstly based on Min-Min scheduling principle, select some tasks whose minimum completion time is comparatively short to constitute a candidate task set, and then schedule this candidate task set using MD-Sufferage algorithm.5. Make an intensive study on GridSim simulation toolkit, and use GridSim to simulate Min-Min, Sufferage, MD-Sufferage and WTMB algorithm. The simulation results showed that:the makespan of MD-Sufferage algorithm slightly outperformed Sufferage algorithm; WTMB algorithm realized the unification of short makespan and short task waiting time, so it had a better synthesis performance than Min-Min, Sufferage, and MD-Sufferage algorithm, and could facilitate stronger flexibility.