ON MULTIPROCESSOR SYSTEM SCHEDULING

We show that there is a good algorithm for scheduling the average comp letion time of a set of unknown DAGs (i.e., data dependency relation g raphs of programs) on a multiprocessor in the PRAM model (Karp and Ram achandran, 1990) (or other similar shared memory models.) Then, we sho w that a large class of parallel jobs can be scheduled with near-optim al average completion time in the BSP model (Valiant, 1990a) though th is is not possible for the class of all unknown DAGs (Deng and Koutsou pias, 1993) (the same holds for other similar distributed memory model s.)