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

W. Grossmann, G. Guariso, M. Hitz and H. Werthner
Additional contact information
W. Grossmann: Institut für Statistik, OR und Computermethoden, Universität Wien, Austria
G. Guariso: Institut für angewandte Informatik und Informationssysteme, Universität Wien, Austria
M. Hitz: Dipartimento di Elettronica, Politecnico di Milano, Italy
H. Werthner: Dipartimento di Elettronica, Politecnico di Milano, Italy

Management Science, 1995, vol. 41, issue 1, 83-93

Abstract: 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 pseudopolynomial, 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.

Keywords: flows in networks; dynamic assignment; min cost flow problems (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.1.83 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:41:y:1995:i:1:p:83-93

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().