Analysis of List scheduling for Dependent Task

Volume 7 Issue 1 December - February 2018

Research Paper

Analysis of List scheduling for Dependent Task

Sunita Kushwaha*, Sanjay Kumar **

* Ph.D. Scholar, School of Studies of Computer Science and Information Technology, Pt. Ravishankar Shukla University, Raipur, Chhattisgarh, India.

** Professor and Head, Department of Computer Science, Pt. Ravishankar Shukla University, Raipur, Chhattisgarh, India.

Kushwaha , S., & Kumar , S. (2018). Analysis of List Scheduling for Dependent Task. i-manager’s Journal on Information Technology, 7(1), 24-27. https://doi.org/10.26634/jit.7.1.14093

Abstract

This is an era of High Performance Computing (HPC), in which more computing elements work together in parallel to enhance the computing power. Scheduling plays an important role to enhance the computing power in the multiprocessor environment. Scheduling of the tasks onto the machines of a multiprocessor environment has generally become a NP-complete (nondeterministic polynomial time) problem. Heuristic is a better way to solve the NP-complete problems. List heuristic scheduling is one of the best and widely used heuristic to use in a homogeneous multiprocessor environment. However, to achieve parallelism in multiprocessor environment is not so easy; it is influenced by various factors such as dependencies, system environment etc. In this paper, some list scheduling algorithms for dependent task sets are studied and their performance are evaluated on the basis of makespan. The EST (Earliest Processing Time) scheduling algorithm performs better and takes less makespan as compared to other scheduling algorithms namely LPT (Longest Processing Time), SPT (Shortest Processing Time) and ECT (Earliest Completion Time). The graphs show that EST performs better when the number of processes increases, than other algorithms.