IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v41y1995i1p83-93.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • W. Grossmann & G. Guariso & M. Hitz & H. Werthner, 1995. "A Min Cost Flow Solution for Dynamic Assignment Problems in Networks with Storage Devices," Management Science, INFORMS, vol. 41(1), pages 83-93, January.
    • Handle: RePEc:inm:ormnsc:v:41:y:1995:i:1:p:83-93
    DOI: 10.1287/mnsc.41.1.83
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.41.1.83
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.41.1.83?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. c. gandolfi & g. guariso & d. togni, 1997. "Optimal Flow Allocation in the Zambezi River System," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 11(5), pages 377-393, October.
    2. Tari, Mehrdad Heidari & Soderstrom, Mats, 2002. "Optimisation modelling of industrial energy systems using MIND introducing the effect of material storage," European Journal of Operational Research, Elsevier, vol. 142(2), pages 419-433, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:41:y:1995:i:1:p:83-93. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.