An Efficient Deadlock Prevention Policy for Noncyclic Scheduling of Multicluster Tools

Tatsushi Nishi, Yushin Watanabe, Masaru Sakai

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


Scheduling of multicluster tools has received much attention due to its complexity of interaction among cluster tools. A cluster tool comprises several modules such as processing modules, a transfer module with a single or dual-armed handling robot, and loadlock modules. A multicluster tool comprises two, three, or more cluster tools that are interconnected with each other. In this paper, we propose a deadlock prevention policy for noncyclic scheduling of dual-armed multicluster tools. The proposed deadlock prevention policy is effective for generating an efficient schedule for two or three-connected multicluster tools with a single or a dual-path flow. This is proven by analyzing the strict minimal siphon of the Petri net model. The performance of the proposed method is compared with that of a maximal permissible deadlock prevention policy. The results demonstrate that the proposed method is computationally efficient for larger state spaces and more suitable than conventional deadlock prevention policies for generating effective schedules for noncyclic scheduling of multicluster tools. Note to Practitioners - Scheduling of multicluster tools has recently attracted attention in the growing semiconductor manufacturing industry. Most conventional studies on multicluster tools focus on cyclic scheduling to minimize cycle time with swap strategy. The challenge addressed by this paper is to derive a deadlock-free schedule for multicluster tools with noncyclic operations. We propose a simple deadlock prevention policy that can be applied to large-scale timed Petri net (PN) model of general multicluster tools without enumeration of siphon computations or solution of mixed integer programming. A timed PN model is developed for noncyclic operations of dual-armed multicluster tools with a dual ath. The computational results show that the approximately 10% of the total throughput of the proposed method is better than those of the conventional methods. It enables more efficient operations for noncyclic scheduling under transient periods including cleaning operations.

Original languageEnglish
Article number8187708
Pages (from-to)1677-1691
Number of pages15
JournalIEEE Transactions on Automation Science and Engineering
Issue number4
Publication statusPublished - Oct 2018
Externally publishedYes


  • Deadlock prevention
  • Petri nets (PNs)
  • discrete event systems
  • multicluster tools
  • scheduling
  • siphon

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'An Efficient Deadlock Prevention Policy for Noncyclic Scheduling of Multicluster Tools'. Together they form a unique fingerprint.

Cite this