A Min Cost Flow Solution for Dynamic Assignment Problems in Networks with Storage Devices

The paper presents a minimum-cost flow approach for dynamic assignment procedures for networks with storage devices over time. Decision variables are diversion of flow at specific nodes and the storage of material in buffers which have to meet upper and lower capacity constraints. Evaluation of a decision is based on utility functions which are assumed to be piecewise linear and concave. The solution is based on a transformation into a network flow problem as suggested by Kuczera (1989). The temporal dimension of the problem is handled by constructing a supergraph with a layer for each time period. These layers are connected by temporal arcs. Thus the problem can be solved entirely by well-known algorithms for the minimum-cost flow problem which yield the optimal solution and determine automatically whether a feasible solution exists or not. The complexity of the proposed algorithm is pseu- dopolynomial, i.e., linear in the size of the network (measured by nodes, arcs, and buffers), linear in the amount of inflow, and quadratic in the number of time periods under consideration.