Premium
A feedback strategy for periodic network flows
Author(s) -
Blanchini Franco,
Queyranne Maurice,
Rinaldi Franca,
Ukovich Walter
Publication year - 1996
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/(sici)1097-0037(199601)27:1<25::aid-net3>3.0.co;2-g
Subject(s) - submodular set function , polyhedron , dimension (graph theory) , mathematical optimization , constraint (computer aided design) , a priori and a posteriori , representation (politics) , mathematics , computation , flow network , time horizon , set (abstract data type) , upper and lower bounds , flow (mathematics) , computer science , algorithm , mathematical analysis , philosophy , geometry , epistemology , politics , political science , pure mathematics , law , programming language
We consider a dynamic network flow model for the control problem of a production‐distribution system with periodic demand in the presence of storage and transportation capacity constraints. Unlike most papers dealing with control problems of dynamic networks, we derive a control strategy in feedback form. It is optimal in the sense that it involves, for any initial time, the set of all the initial states for which there exists a control strategy allowing the network variables (flows, storage levels) to remain in their constraint domain for all future times. The evaluation of such a strategy requires the previous computation of these maximal sets. We show that, due to the particular structure of the system, they are submodular polyhedra; in particular, they are finitely represented and the representation complexity is a priori known. Moreover, the evaluation of this sequence, even for the infinite horizon problem, can be performed in a finite number of steps that has a known upper bound depending on the dimension of the problem only. As a consequence of these results, the optimal strategy requires, at each step, to solve a submodular flow problem. The finite horizon problem is solved by the proposed method as a particular case. © 1996 John Wiley & Sons, Inc.