Summary
In this paper, 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 polynomia time algorithms.
Similar content being viewed by others
References
Blazewicz, J.: Selected topics in scheduling theory. Ann. Discr. Math.31, 1–60 (1987)
Coffman, E.G. Jr. (ed.): Computer & job/Shop scheduling theory. New York: Wiley 1976
Coffman, E.G. Jr., Garey, M.R., Johnson, D.S., Lapaugh, A.S.: Scheduling File Transfers. SIAM J. Comput.14 (3), 744–780 (1985)
Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman 1979
Gerla, M., Kleinrock, L.: Flow control: A comparative survey. IEEE Trans. Commun.28(4), 553–574 (1980)
Petreschi, R., Simeone, B.: A switching algorithm for the solution of quadratic Boolean equations. Info. Process. Lett.11 (4), 193–198 (1980)
Tannenbaum, A.S.: Computer networks. New Jersey: Prentice-Hall 1981
Author information
Authors and Affiliations
Additional information
Most of this work was done while this author was at the Department of Mathematics, University of Rome “La Sapienza”
Rights and permissions
About this article
Cite this article
Bovet, D.P., Crescenzi, P. Minimum-delay schedules in layered networks. Acta Informatica 28, 453–461 (1991). https://doi.org/10.1007/BF01178583
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01178583