Network design and dynamic routing under queueing demand |
| |
| Authors: | K O Kortanek G G Polak |
| |
| Institution: | (1) Department of Mathematics, Carnegie-Mellon University, Pittsburgh, PA;(2) Department of Mathematics, Wheeling College, Wheeling, WV |
| |
| Abstract: | Given a nonhierarchical network and time-varying flow requirements, the problem of determining optimal capacities is termed design; that of determining optimal flows as dynamic routing. We formulate a linear program to solve both simultaneously in the case of deterministic flow requirements. A probability distribution termed the Erlang Difference Distribution is derived from a queueing model to describe random flow requirements, and this case leads to a separable convex program that has a linear programming equivalent. Both linear programs are amenable to Dantzig-Wolfe decomposition, which reveals subproblems that yield to special techniques of solution.
Zusammenfassung Gegeben sei ein nicht hierarchisches Netzwerk mit zeitabhängigen Flüssen. Das Problem, optimale Kapazitäten festzusetzen, wird als Netzwerk-Entwurf bezeichnet. Die Bestimmung optimaler Flüsse bezeichnet man als dynamische Flußführung. Es wird ein lineares Programm formuliert, das beide Probleme gleichzeitig löst, sofern deterministische Flüsse vorliegen. Sodann wird eine Wahrscheinlichkeitsverteilung namens  Erlang'sche Differenzen-Verteilung aus einem Warteschlangenmodell abgeleitet, um zufällige Flüsse zu beschreiben. Dies führt auf ein separables konvexes Programm mit einem linearen Programm als Äquivalent. Bei beiden betrachteten linearen Programmen kann die Dantzig-Wolfe Dekomposition angewendet werden, wobei die auftretenden Teilprobleme durch spezielle Techniken gelöst werden können.
Research partially supported by National Science Foundation Grant ECS-8300214. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
