Structure identification in layered precedence networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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/)).

Original languageEnglish (US)
Title of host publication1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1177-1182
Number of pages6
ISBN (Electronic)9781509021826
DOIs
StatePublished - Oct 6 2017
Event1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017 - Kohala Coast, United States
Duration: Aug 27 2017Aug 30 2017

Publication series

Name1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017
Volume2017-January

Other

Other1st Annual IEEE Conference on Control Technology and Applications, CCTA 2017
CountryUnited States
CityKohala Coast
Period8/27/178/30/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Hardware and Architecture
  • Software
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Structure identification in layered precedence networks'. Together they form a unique fingerprint.

Cite this