Near-optimal heuristics for schedulings on task-dependent machines

The paper considers task assignments in a parallel processing environment. Processors in this environment are considered to be task-dependent in that a task´s processing time depends not only on the nature of the task but also on the processor to which it is assigned. The problem is a generalization of several related problems of scheduling independent tasks. The authors show that the problem is NP-complete. They design good heuristics which satisfy two criteria: efficiency and performance. The algorithms presented are all polynomial-time and very efficient. To measure the relative performance of the algorithms. They use a low estimate of the optimal finishing time as a comparison. The simulation shows that the algorithms perform consistently well and some of them are near-optimal in terms of average relative performance