BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-84-1025
       ENTRY:: May 27, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Fast scheduling algorithms on parallel computers
        TYPE:: Technical Report
      AUTHOR:: Helmbold, David
      AUTHOR:: Mayr, Ernst
        DATE:: November 1984
       PAGES:: 36
    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.
       NOTES:: [Adminitrivia V1/Prg/19950527]
         END:: STAN//CS-TR-84-1025