Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays

We present here an n^τ+1 algorithm for optimally scheduling a dag of n nodes on a multiprocessor when the message-to-instruction ratio parameter is τ. Our algorithm constructs an optimum schedule which uses at most n processors. We furthermore show lower bound results on the amount of recomputation needed, thus answering an open question posed by Papadimitriou and Yannakakis. In addition, precise lower bounds are demonstrated for the scheduling time of full binary trees. Our techniques may contribute to an important new understanding of parallel scheduling when the message delay is significant, which is usually the case.