An Investigation of List Heuristic Scheduling Algorithms for Multiprocessor System
Sunita Kushwaha, Sanjay Kumar · SSRN Electronic Journal · 2018
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.