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

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