Deadlock-free scheduling of automated manufacturing systems using petri nets and hybrid heuristic search

Jianchao Luo, Keyi Xing, Mengchu Zhou, Xiaoling Li, Xinnian Wang

Research output: Contribution to journalArticlepeer-review

70 Scopus citations


This paper focuses on the deadlock-free scheduling problem of automated manufacturing systems with shared resources and route flexibility, and develops novel scheduling methods by combining deadlock control policies and hybrid heuristic search. Place-timed Petri nets are used to model the systems and find a feasible sequence of firing transitions in the built model such that the firing time of its last transition is as small as possible. Based on the reachability graph of the net and a minimum processing time matrix, new heuristic and selection functions are designed to guide search processes. The proposed hybrid heuristic search is based on state space exploration and hence suffers from the state space explosion problem. In order to reduce the explored space, the search is restrained within a limited local search window. By embedding the deadlock-avoidance policies into the search processes, a novel deadlock-free hybrid heuristic search algorithm is developed. Experimental results indicate the effectiveness and superiority of the proposed algorithm over the state-of-the-art method.

Original languageEnglish (US)
Article number6909061
Pages (from-to)530-541
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Issue number3
StatePublished - Mar 1 2015

All Science Journal Classification (ASJC) codes

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


  • Automated manufacturing systems
  • Petri net
  • deadlock-avoidance policy
  • heuristic search
  • scheduling


Dive into the research topics of 'Deadlock-free scheduling of automated manufacturing systems using petri nets and hybrid heuristic search'. Together they form a unique fingerprint.

Cite this