J. Brest and V. Žumer (Slovenia)
Parallel processing, task graphs, list scheduling, processorallocation
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^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.
Important Links:
Go Back
