Deadlock-Free Scheduling of Flexible Assembly Systems Based on Petri Nets and Local Search

Jianchao Luo, Zhiqiang Liu, Mengchu Zhou, Keyi Xing

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


Deadlock-free scheduling and control is critical for optimizing the performance of flexible assembly systems (FASs). Based on the Petri net models of FASs, this paper integrates a deadlock prevention policy with local search and develops a novel deadlock-free scheduling algorithm. A solution of the scheduling problem is coded as a chromosome representation that is a permutation with repetition of parts. By using the deadlock prevention policy, a repairing algorithm (RA) is developed to repair unfeasible chromosomes. A perturbation strategy based on estimation of distribution algorithm is developed to escape from local optima. Moreover, to improve population diversity, an acceptance criterion (AC) based on Pareto dominance is proposed. The chromosome representation, RA, perturbation strategy, and AC together support the cooperative aspect of local search for scheduling problems strongly.

Original languageEnglish (US)
Article number8457481
Pages (from-to)3658-3669
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Issue number10
StatePublished - Oct 2020

All Science Journal Classification (ASJC) codes

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


  • Deadlock prevention policy
  • Petri net (PN)
  • flexible assembly system (FAS)
  • local search
  • scheduling


Dive into the research topics of 'Deadlock-Free Scheduling of Flexible Assembly Systems Based on Petri Nets and Local Search'. Together they form a unique fingerprint.

Cite this