A classical problem in scheduling theory is to compute a minimal length schedule for executing n unit length tasks on m identical parallel processors constrained by a precedence relation. This problem is NP-complete in general, but there exist a number of restricted variants of it that have polynomial solutions and are still of major interest.
First, we show that if the precedence constraints are restricted to be trees, then an optimal schedule can be computed in time O(lognlogm) using n/logn processors of an EREW PRAM. Hence, for those cases where m is not part of the input but a constant, our algorithm is work and time optimal. Second, we present a parallel algorithm that optimally schedules arbitrary precedence constraints on two processors. It runs in time O(log2n) and uses n3/logn processors. In addition, we show that optimal two processor schedules can be computed much more efficiently, if the precedence constraints are restricted to be series parallel graphs. In this case, an optimal schedule can be computed in logarithmic time and a linear number of operations suffice.
Finally, we investigate the parallel complexity of scheduling with unit interprocessor communication delays. In this extended setting the schedule additionally takes into account the time required to communicate data between processors. After finishing a task, one unit of time must pass before any of its successors can be started on a different processor, in order to allow for transportation of results from one task to the other. The problem of computing minimal length schedules in this setting is NP-complete, even if precedence constraints are restricted to be trees. The only nontrivial class of precedence constraints for which polynomial solutions are known, is the class of interval orders. We present a parallel algorithm that solves the problem for interval orders in time O(log2n) using n3/logn processors. This is the first NC algorithm for this problem.
Hans Stadtherr, 1998/09/23