×

Balancing problems in acyclic networks. (English) Zbl 0811.90108

The authors regard a balancing problem in acyclic networks. Arc lengths are called balanced if any two paths with common endpoints have the same length. The buffer assignment problem arises in a network if the sum of the added amounts is minimal, in such a way that the arc lengths are balanced. The authors give procedures which solve several generalizations of the problem in polynomial time. The network flow theory is used.
The authors solve a weighted version of the problem for nonrooted networks and upper bounds of buffers. It is shown that the problem of balancing a network while minimizing the number of arcs with positive buffers is NP-hard.
Reviewer: G.Merkel (Leipzig)

MSC:

90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
90C60 Abstract computational complexity for mathematical programming problems
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows, (Nemhauser, G. L.; Rinnooy Kan, A. H.G.; Todd, M. S., Handbooks in Operations Research and Management Science, Vol. I (1989), Elsevier: Elsevier Amsterdam), 211-369
[2] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms and Applications (1992), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[3] Bartholdi, J. J.; Orlin, J. B.; Ratliff, H. D., Cyclic scheduling via integer programs with circular ones, Oper. Res., 28, 1073-1085 (1980) · Zbl 0451.90075
[4] Boros, E.; Hammer, P. L.; Shamir, R., A polynomial algorithm for balancing acyclic data flow graphs, IEEE Trans. Comput., 41, 1380-1385 (1992) · Zbl 1395.68141
[5] Chang, P. R.; Lee, C. S.G., A decomposition approach for balancing large-scale acyclic data flow graphs, IEEE Trans. Comput., 39, 34-46 (1990)
[6] Dantzig, G. B.; Blattner, W.; Rao, M. R., Finding and cycle in a graph with minimum cost to time ratio with application to a ship routing problem, (Rosensthiehl, P., Theory of Graphs (1967), Dunod: Dunod Paris), 77-84, Gordon and Breach, New York · Zbl 0189.24102
[7] Dennis, J. B., Data flow supercomputers, IEEE Comput., 48-56 (1980)
[8] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow algorithms, J. ACM, 19, 248-264 (1972) · Zbl 0318.90024
[9] Fisher, A. L.; Kung, S. Y., Special-purpose VLSI architectures: general description and a case study, (Kung; Whitehouse; Kailath, VLSI and Modern Signal Processing (1985), Prentice Hall: Prentice Hall Englewood Cliffs, NJ), 153-169
[10] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization, J. ACM, 34, 596-615 (1987) · Zbl 1412.68048
[11] Garey, M. R.; Johnson, D. S., The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math., 32, 826-834 (1977) · Zbl 0396.05009
[12] Goldberg, A. V.; Tardos, É.; Tarjan, R. E., Network flow algorithms, (Korte, B.; Lovasz, L.; Prömel, H. J.; Schrijver, A., Paths, Flows and VLSI-Layout (1990), Springer: Springer Berlin), 101-164
[13] Hartmann, M.; Orlin, J. B., Finding minimum cost to time ratio cycles with small integral transit times, (Tech. Rept. No. UNC/TR/91-19 (1991), University of North Carolina: University of North Carolina Chapel Hill) · Zbl 0786.90081
[14] Kelley, J. E., Critical-path planning and scheduling: mathematical basis, Oper. Res., 9, 296-320 (1961) · Zbl 0098.12103
[15] Kung, S. Y., Why systolic architectures?, IEEE Comput., 37-46 (1982)
[16] Lawler, E., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0413.90040
[17] Megiddo, N., Combinatorial optimization with rational objective functions, Math. Oper. Res., 3, 313-323 (1979)
[18] Moder, J. J.; Phillips, C. R.; Davis, E. W., Project Management with CPM, PERT and Precedence Diagrams (1983), Van Nostrand Reinhold: Van Nostrand Reinhold New York
[19] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052
[20] Orlin, J. B., Sloan W.P. No. 3060-89-MS (1989), Sloan School of Management, M.I.T
[21] Orlin, J. B.; Rothblum, U. G., Computing optimal scaling by parametric network algorithms, Math. Programming, 32, 1-10 (1985) · Zbl 0573.90095
[22] Tarjan, R. E., Data Structures and Network Algorithms (1983), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0584.68077
[23] Young, N. E.; Tarjan, R. E.; Orlin, J. B., Faster parametric shortest path and minimum balance algorithms, Networks, 21, 205-221 (1991) · Zbl 0719.90087
[24] Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structures, (Annals of Discrete Mathematics, 10 (1981), North-Holland: North-Holland Amsterdam) · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.