Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems

Yufeng Chen, Zhiwu Li, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

110 Scopus citations


This paper presents two iterative deadlock prevention policies for flexible manufacturing systems (FMSs). Both can find a maximally permissive liveness-enforcing supervisor with a small number of control places. A vector covering approach is used to obtain a minimal covering set of legal markings and a minimal covered set of first-met bad markings (FBMs), which are much smaller than the sets of legal markings and FBMs, respectively. At each iteration, by solving an integer linear programming problem (ILPP), a place invariant (PI) associated with a control place is designed to forbid as many FBMs as possible, and no markings in the minimal covering set of legal markings are forbidden. The objective function of the ILPP maximizes the number of FBMs that are forbidden by the PI. Then, the forbidden FBMs by the PI are removed from the minimal covered set of FBMs. This process is carried out until all FBMs are forbidden. Two ILPP design techniques are developed for the control policies. Though the proposed methods cannot in general guarantee the minimality of the supervisory structure, they reduce the overall computational time greatly, which is shown by numerical studies. Finally, a number of FMS examples from the literature are presented to illustrate the proposed methods.

Original languageEnglish (US)
Article number6095650
Pages (from-to)615-629
Number of pages15
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
Issue number3
StatePublished - May 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications


  • Deadlock prevention
  • Petri net
  • flexible manufacturing system (FMS)
  • optimal liveness-enforcing supervisor


Dive into the research topics of 'Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems'. Together they form a unique fingerprint.

Cite this