Fortschritte in der angewandten Wissenschaftsforschung Offener Zugang

Abstrakt

Comparative analysis of heuristics for multiprocessor task scheduling problem with homogeneous processors

Sunita Dhingra, Satinder Bal Gupta and Ranjit Biswas

Scheduling of a task on a multiprocessor system represented by a directed acyclic graph for minimizing the different performance measures is a prominent problem in parallel processing. As judgment of an optimal schedule for multiprocessor task scheduling problem is a NP hard problem and different researchers have resorted for devising efficient heuristics. List scheduling heuristics belong to one of the categories used for multiprocessor task scheduling problem. Present work considers the comparative analysis of five commonly used list scheduling heuristics based on makespan and total completion time of the schedule for homogeneous multiprocessors. A defined Performance Index (PI) is used for the comparative analysis of different heuristics and it has been proved that the Insertion Scheduling Heuristic (ISH) Algorithm and Earliest Time First (ETF) Algorithm provides the best results for trade-off between the makespan and total completion time of the schedule.