On the complexity of scheduling with large communication delays

On the complexity of scheduling with large communication delays

0.00 Avg rating—0 Votes
Article ID: iaor1999642
Country: Netherlands
Volume: 94
Issue: 2
Start Page Number: 252
End Page Number: 260
Publication Date: Oct 1996
Journal: European Journal of Operational Research
Authors: , ,
Abstract:

Given a directed acyclic graph (DAG) with unit execution time tasks and constant communication delays c=2, we are interested in deciding if there is a schedule for the DAG of length at most L. We prove that the problem is polynomial when L is equal to (c+1), or (c+2) for the special case of c⩾2, and that it is NP-complete for (c+3) for any value of c, even in the case of bipartite DAG of depth one.

Reviews

Required fields are marked *. Your email address will not be published.