Task Scheduling Algorithms on Grid Computing Systems

Abstract

Scheduling tasks on heterogeneous resources distributed over a grid computing system is an NP-complete problem. The main aim for several researchers is to develop variant scheduling algorithms for achieving optimality. However, using of the full power of resources is still a challenge. In this thesis, two heuristic algorithms called Sort-Mid and Range-Suffrage are proposed. Sort-Mid and Range-Suffrage aim to maximizing the resources utilization and minimizing the makespan. The base step of Sort-Mid is to get the mean value of two consecutive middle values in the sorting list of completion time of each task. Then, the maximum value of these mean values is determined. Finally, the task has the maximum value is assigned to the machine having the minimum completion time. Experimental tests indicate that Sort-Mid utilizes the grid by more than 99% at 12 instances. In addition, Sort-Mid has good makespan in the 12 instances.