TY - GEN
T1 - Structure identification in layered precedence networks
AU - Kong, Seo Taek
AU - Katselis, Dimitrios
AU - Beck, Carolyn L.
AU - Srikant, R.
N1 - This work has been partially supported by funding from The Boeing Company, and the NSF grants EECS-1509302 and CMMI-1562276.
PY - 2017/10/6
Y1 - 2017/10/6
N2 - We consider the problem of identifying the structure of a network when precedence constraints are present. The associated graph is assumed to be directed, layered and with edges that exist only between successive layers. Such precedence networks arise in manufacturing processes resulting from a necessary or desirable sequencing of subassembly tasks to be completed in order to assemble the final product. Each node in the graph corresponds to a task and each edge represents a precedence constraint. We provide a simple and natural algorithm that can identify the network structure. We study the corresponding sample complexity as a function of the number of layers L, the maximum number of nodes, D, per layer and the maximum node in-degree M in the network. We show that, for networks that are start-time synchronized, i.e., networks in which all tasks per layer are coordinated to start simultaneously, identification with probability at least 1-for some 0 < < 1 is guaranteed for a number of samples satisfying n = Ω (Mlog ((L-2)DM/)).
AB - We consider the problem of identifying the structure of a network when precedence constraints are present. The associated graph is assumed to be directed, layered and with edges that exist only between successive layers. Such precedence networks arise in manufacturing processes resulting from a necessary or desirable sequencing of subassembly tasks to be completed in order to assemble the final product. Each node in the graph corresponds to a task and each edge represents a precedence constraint. We provide a simple and natural algorithm that can identify the network structure. We study the corresponding sample complexity as a function of the number of layers L, the maximum number of nodes, D, per layer and the maximum node in-degree M in the network. We show that, for networks that are start-time synchronized, i.e., networks in which all tasks per layer are coordinated to start simultaneously, identification with probability at least 1-for some 0 < < 1 is guaranteed for a number of samples satisfying n = Ω (Mlog ((L-2)DM/)).
UR - http://www.scopus.com/inward/record.url?scp=85047631763&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047631763&partnerID=8YFLogxK
U2 - 10.1109/CCTA.2017.8062618
DO - 10.1109/CCTA.2017.8062618
M3 - Conference contribution
AN - SCOPUS:85047631763
T3 - 1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017
SP - 1177
EP - 1182
BT - 1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017
Y2 - 27 August 2017 through 30 August 2017
ER -