Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems

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

Research output: Contribution to journalArticlepeer-review


The development of efficient deadlock avoidance policies (DAP's) for sequential resource allocation systems (RAS's) is a problem of increasing interest in the scientific community, largely because of its relevance to the design of large-scale flexibly automated manufacturing systems. Much of the work on this problem existing in the literature is focused on the so-called single-unit RAS model, which is the simplest model in the considered class of RAS's. Furthermore, due to a well-established result stating that, even for single-unit RAS's, the computation of the maximally permissive DAP is intractable (NP-hard), many researchers (including our group) have focused on obtaining good suboptimal policies which are computationally tractable (scalable) and provably correct. In the first part of the paper, it is shown, however, that for a large subset (in fact, a majority) of single-unit RAS's, the optimal DAP can be obtained in real-time with a computational cost which is a polynomial function of the system size (i.e., the number of resource types and the distinct route stages of the processes running through the system). The implications of this result for the entire class of single-unit RAS's are also explored. With a result on the design of optimal DAP's for single-unit RAS's, the second part of the paper concentrates on the development of scalable and provably correct DAP's for the more general case of conjunctive RAS's.

Original languageEnglish (US)
Pages (from-to)1344-1357
Number of pages14
JournalIEEE Transactions on Automatic Control
Issue number10
StatePublished - 1997


  • Complexity
  • Deadlock
  • Deadlock avoidance
  • Flexibly automated production systems
  • Resource allocation systems

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems'. Together they form a unique fingerprint.

Cite this