Constructing Maximal Dynamic Flows from Static Flows

A network, in which two integers t ıj (the traversal time) and c ıj (the capacity) are associated with each arc P ı P j , is considered with respect to the following question. What is the maximal amount of goods that can be transported from one node to another in a given number T of time periods, and how does one ship in order to achieve this maximum? A computationally efficient algorithm for solving this dynamic linear-programming problem is presented. The algorithm has the following features (a) The only arithmetic operations required are addition and subtraction (b) In solving for a given time period T, optimal solutions for all lesser time periods are a by-product (c) The constructed optimal solution for a given T is presented as a relatively small number of activities (chain-flows) which are repeated over and over until the end of the T periods. Hence, in particular, hold-overs at intermediate nodes are not required (d) Arcs which serve as bottlenecks for the flow are singled out, as well as the time periods in which they act as such (e) In solving the problem for successive values of T, stabilization on a set of chain-flows (see (c) above) eventually occurs, and an a priori bound on when stabilization occurs can be established. The fact that there exist solutions to this problem which have the simple form described in (c) is remarkable, since other dynamic linear-programming problems that have been studied do not enjoy this property.