Premium
A minimum concave‐cost dynamic network flow problem with an application to lot‐sizing
Author(s) -
Graves Stephen C.,
Orlin James B.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150107
Subject(s) - sizing , minimum cost flow problem , mathematical optimization , flow network , multi commodity flow problem , computer science , flow (mathematics) , time horizon , mathematics , art , geometry , visual arts
We consider a minimum‐cost dynamic network‐flow problem on a very special network. This network flow problem models an infinite‐horizon, lot‐sizing problem with deterministic demand and periodic data. We permit two different objectives: minimize long‐run average‐cost per period and minimize the discounted cost. In both cases we give polynomial algorithms when certain arc costs are fixed charge functions, and others are linear.