TY - GEN

T1 - Structure identification in layered precedence networks

AU - Kong, Seo Taek

AU - Katselis, Dimitrios

AU - Beck, Carolyn L.

AU - Srikant, R.

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 -