Minimum-delay schedules in layered networks (Q1812948)

We consider the following problem: Given a layered network including a set of messages, each of which must be transmitted from a source to a sink node, what is the sequence of moves from one node to another which minimizes the total completion time? We first show that the general problem is NP-complete for both fixed and variable path routing (thus the scheduling problem for more realistic networks with cycles must be considered computationally intractable). We then consider several restrictions which admit polynomial time algorithms.