Report Number: CS-TR-84-1025
Institution: Stanford University, Department of Computer Science
Title: Fast scheduling algorithms on parallel computers
Author: Helmbold, David
Author: Mayr, Ernst
Date: November 1984
Abstract: With the introduction of parallel processing, scheduling problems have generated great interest. Although there are good sequential algorithms for many scheduling problems, there are few fast parallel scheduling algorithms. In this paper we present several good scheduling algorithms that run on EREW PRAMS. For the unit time execution case, we have algorithms that will schedule n jobs with intree or outtree precedence constraints in O(log n) time. The intree algorithm requires $n^3$ processors, and the outtree algorithm requires $n^4$ processors. Another type of scheduling problem is list scheduling, where a list of n jobs with integer execution times is to be scheduled in list order. We show that the general list scheduling problem on two identical processors is polynomial-time complete, and therefore is not likely to have a fast parallel algorithm. However, when the length of the (binary representation of the) execution times is bounded by O($log^c$ n) there is an NC algorithm using $n^4$ processors.
http://i.stanford.edu/pub/cstr/reports/cs/tr/84/1025/CS-TR-84-1025.pdf