Optimal flow control in acyclic networks with uncontrollable routings and precedence constraints

Authors: Reveliotis, Spyros1; Bountourelis, Theologos2

Source: Discrete Event Dynamic Systems, Volume 21, Number 4, December 2011 , pp. 499-518(20)

Publisher: Springer

Buy & download fulltext article:


Price: $47.00 plus tax (Refund Policy)


This paper introduces a novel optimal flow control problem that seeks to convey a specified amount of fluid to each of the nodes of an acyclic digraph with a single source node, while minimizing the total amount of fluid inducted into the network. Two factors complicating the aforementioned task are (i) the presence of nodes with uncontrollable routing of the traversing flow and (ii) a set of precedence constraints regarding the satisfaction of the nodal fluid requirements. It is shown that the considered problem can be naturally formulated as a continuous-time optimal control problem that can be reduced to a hybrid optimal control problem with controlled switching. This property subsequently enables the solution of the considered problem through a Mixed Integer Programming formulation. Additional results in the paper establish the NP-hardness of the considered problem, highlight its affinity to some well known scheduling problems, and offer guidelines that can alleviate the increased problem complexity.

Keywords: Complexity Analysis; Hybrid optimal control with controlled switching; Mixed integer programming; Optimal flow control

Document Type: Research Article

DOI: http://dx.doi.org/10.1007/s10626-011-0112-0

Affiliations: 1: School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA, Email: spyros@isye.gatech.edu 2: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, USA, Email: bountourelis@gmail.com

Publication date: December 1, 2011

Related content


Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page