Comparative Study of Static Task Scheduling Algorithms for Heterogeneous Systems

On the distributed or parallel heterogeneous computing systems, an application is usually decomposed into several interdependent sets of co-operating subtasks and assigned to a set of available processors for execution. Task scheduling is in general NP-compete problem. Static task scheduling algorithms are categorized as Heuristic based and Guided random search based scheduling algorithms. Heuristic algorithms guaranteed to find near optimal solution in less than polynomial time. Heuristic based list scheduling algorithms are Heterogeneous Earliest Finish Time (HEFT) and Critical-Path-On- -Processor (CPOP). Whereas, Guided random search based scheduling algorithms have shown robust performance on verity of schedulingproblems. Typical examples are Multiple Priority Queueing Genetic Algorithm (MPQGA), Tabu Search(TS), Ant Colony System (ACS). This paper gives comparative study of all these static task scheduling algorithms and compares them on the basis of average makespan, schedule length ratio (SLR) and speedup and running time of algorithm.