Optimal flow control in acyclic networks with uncontrollable routings and precedence constraints
Source: Discrete Event Dynamic Systems, Volume 21, Number 4, December 2011 , pp. 499-518(20)
Abstract: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.
Document Type: Research Article
Affiliations: 1: School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA, Email: firstname.lastname@example.org 2: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, USA, Email: email@example.com
Publication date: December 1, 2011