A Heuristic Algorithm for the Static Scheduling on Multiprocessors

摘要

The multiprocessor scheduling problem discussed in this paper is to determine a non-preemptive schedule to minimize the maximum completion time (the schedule length or make-span) when a set of computational tasks having arbitrary precedence constraints and arbitrary processing time are assigned to processors of the same speed. The complexity of the proposed heuristic algorithm is O(pv{sup}2), where p is the number of the processing elements and v is the number of nodes in the task graph. In this paper also a comparison of proposed algorithm with two well-known scheduling algorithms is carried out. The proposed algorithm generates in many cases better solutions than the referenced algorithms in terms of the maximum completion times.