An efficient real-time deadlock-free control algorithm for automated manufacturing systems

C. O. Kim, S. S. Kim

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)


In recent years, deadlock issue has received considerable attention in the real-time control realm of automated manufacturing system (AMS). In this paper, we propose a simple and easily adaptable deadlock avoidance algorithm using a graph theoretic approach. Unlike Petri-net based methods which are complex and static from the viewpoint that once they are constructed and implemented, it is not easy to modify them as the system configuration is changed, and operate them coupled with other shop-floor control modules such as a dispatching controller, our algorithm can be used cooperatively with a dispatching controller and expanded with little modification. The core of the algorithm consists of two modules: resource allocation policy and a cycle detection method. In particular, the resource allocation policy is of importance in our algorithm because even though the cycle detection method is employed, deadlock may occur under wrong resource allocation policies. Throughout this paper, we propose a quasi two-step resourceallocation policy with which our deadlock avoidance algorithm can detect and avoid deadlock just one step before deadlock.

Original languageEnglish
Pages (from-to)1545-1560
Number of pages16
JournalInternational Journal of Production Research
Issue number6
Publication statusPublished - 1997 Jun

All Science Journal Classification (ASJC) codes

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'An efficient real-time deadlock-free control algorithm for automated manufacturing systems'. Together they form a unique fingerprint.

Cite this