Constructing Maximal Dynamic Flows from Static Flows

Abstract

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.