Since the problem of scheduling independent jobs in heterogeneous computational resources is known as NP-complete, an approximation or heuristic algorithm is highly desirable. Grid is an example of the heterogeneous parallel computer system. Many researchers propose heuristic scheduling algorithm for Grid. In this paper, we propose a new on-line heuristic scheduling algorithm. We show that our scheduling algorithm has better performance than previous scheduling algorithms by extensive simulation.
Introduction:
A Grid computing system is a system which has various machines to execute a set of tasks. We need high performance Grid computing systems in the field of natural science and engineering for large scale simulation. In this paper, we propose a scheduling algorithm which assigns tasks to machines in a heterogeneous Grid computing system. The scheduling algorithm determines the execution order of the tasks which will be assigned to machines. Since the problem of allocating independent jobs in heterogeneous computational resources is known as NP-complete, an approximation or heuristic algorithm is highly desirable.
In the scheduling algorithms, we consider that the tasks randomly arrive the system. We assume that the scheduling algorithms are nonpreemptive, i.e., tasks must run to completion once they start, and the tasks have no deadlines. All the tasks are independent, i.e., there is no synchronization or communication among the tasks. In the on-line mode, a task is assigned to a machine as soon as it arrives at the scheduling system.
Source: Nanjing University
Authors: Hak Du Kim | Jin Suk Kim
Scheduling Algorithms for Grid Computing: State of the Art and Open Problems
>> More Project Downloads on Grid Computing