A Novel Approach for Task Scheduling in Multiprocessor System

In multiprocessor system, scheduling of tasks to assigned on the number of processors. The major objective of task scheduling is to find minimum execution time of a program. It is well known that the complexity of a general scheduling problem is NP-Complete [9], there are number of heuristic have been developed. Each of which may either find optimal or near optimal scheduling under the different conditions. The task scheduling is represented by a directed acyclic graph (DAG). In this paper, we present a new scheduling algorithm which is called Task Scheduling based on Breath First Search(TSB). The TSB is queue based approach to schedule parallel tasks on the homogenous parallel multiprocessor system. Its performance is evaluated in comparison with Highest Level First with Estimate Time (HLFET) algorithm, Modified Critical Path (MCP) algorithm, Earliest Time First (ETF) algorithm and Dynamic Level Scheduling (DLS) algorithm in terms of Speedup, Efficiency, Load Balance and Normalized Scheduling Length (NSL).