On the complexity of optimal deadlock avoidance in flexible manufacturing systems

Spiridon A. Reveliotis, Mark A. Lawley, Placid M. Ferreira

Research output: Contribution to journalConference articlepeer-review


The problem of the manufacturing system deadlock has received considerable attention recently, since its effective solution is a prerequisite to the implementation of large-scale flexibly automated discrete-part manufacturing systems (FMS). Its difficulty arises from the fact that in the FMS context, the computation of the optimal deadlock avoidance policy is NP-hard. This paper proves, though, that for a large subclass of FMS, with significant practical relevance, the optimal DAP is polynomially tractable in real-time. The implications of this result to broader FMS classes are also considered.

Original languageEnglish (US)
Pages (from-to)1008-1012
Number of pages5
JournalProceedings of the American Control Conference
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 American Control Conference. Part 3 (of 6) - Albuquerque, NM, USA
Duration: Jun 4 1997Jun 6 1997

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'On the complexity of optimal deadlock avoidance in flexible manufacturing systems'. Together they form a unique fingerprint.

Cite this