The problem of obtaining an optimal scheduling of dependent tasks in homogeneous multiprocessor system is well known as an NP-hard problem. Heuristic is the best way to solve this problem. In a homogeneous multiprocessor system, task execution time is independent of the machine to which it is assigned. Recent research in scheduling has shown that list scheduling algorithms usually obtain more efficient and less complex schedules than other known algorithms. In this paper, some basic list scheduling algorithms, namely, LPT, SPT, ECT and EST are compared on the basis of performance parameter Makespan in two different environments. In the first environment, all the processes arrive at ‘zero’ time instantly, while in the second environment, all the processes arrive randomly. Simulation results show that the makespan of LPT is better than other algorithms in both environments.

A major issue in the operation of parallel computing systems is that of scheduling, which is an important problem in areas like manufacturing, process control, economics, and operation research, to name a few. To schedule is to simply allocate a set of tasks or jobs to resources such that the optimum performance is obtained (Ramamoorthy, 1972). If these tasks are not interdependent, the problem is known as task allocation. However, if tasks are dependent, then output of one task may become input to another task. In such cases, precedence relation among tasks is defined and Direct Acyclic Graph (DAG) is drawn. In a parallel processor system, one would expect linear improvement with increase in the number of processors used. However, this is generally not the case due to factors such as communication overhead, control overhead and precedence constraints between tasks (Adams, 1974; and Chow and Kohler, 1979).

LPT, SPT, ECT, EST, Makespan