BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-81-880
       ENTRY:: June 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Well structured parallel programs are not easier to schedule
        TYPE:: Technical Report
      AUTHOR:: Mayr, Ernst W.
        DATE:: September 1981
       PAGES:: 17
    ABSTRACT:: The scheduling problem for unit time task systems with
               arbitrary precedence constrainls is known to be NP-complete.
               We show that the same is true even if the precedence
               constraints are restricted to certain subclasses which make
               the corresponding parallel programs more structured. Among
               these classes are those derived from hierarchic cobegin-coend
               programming constructs, level graph forests, and the parallel
               or serial composition of an out-tree and an in-tree. In each
               case, the completeness proof depends heavily on the number of
               processors being part of the problem instances.
       NOTES:: [Adminitrivia V1/Prg/19950605]
         END:: STAN//CS-TR-81-880