Iterative Deadlock Control for Petri Net Models of Automated Manufacturing Systems: Algorithms and Case Studies

Iterative Deadlock Control for Petri Net Models of Automated Manufacturing Systems: Algorithms and Case Studies

Anrong Wang (Xidian University, China) and MengChu Zhou (New Jersey Institute of Technology, USA & Tongji University, China)
Copyright: © 2013 |Pages: 26
DOI: 10.4018/978-1-4666-4034-4.ch012
OnDemand PDF Download:


Deadlocks should be eliminated in resource allocation systems such as flexible manufacturing systems. An iterative deadlock control policy is usually considered to be a natural solution with reasonable computational cost for a large-scale system where direct methods would be prohibitively expensive (and in some cases impossible) even with the best available computing power. This chapter reviews the existing iterative deadlock prevention policies for discrete event systems that are modeled with Petri nets. A number of technical problems in the existing iterative deadlock control approaches are formulated and discussed. Their solutions are illustrated through case studies. The authors conclude that the suitability, effectiveness, and efficiency of an iterative deadlock control approach are sensitive to specific examples and no general algorithm is found in the literature, which works well for all cases.
Chapter Preview

1. Introduction

Deadlock-free is often a desirable situation in resource allocation systems. Because deadlocks always deteriorate the utilization of resources and may lead to serious economy loss in highly automated production processes such as semiconductor manufacturing, and even catastrophic results in safety-critical systems such as management and monitoring systems of nuclear power stations.

Graph theory, automata, and Petri nets (Hruz and Zhou 2007; Raty 2010; Trappey, Hsiao, and Lin 2011) are three important and widely used mathematical tools to handle deadlock problems in resource allocation systems. Particularly, Petri nets are considered as a popular formalism due to their inherent characteristics. On the one hand, Petri nets are intuitive and capture structural information about a system to be modeled. On the other hand, many analysis techniques that have been developed for studying them promote the popularity of Petri net formalism. For instance, reachability analysis and structure-based linear-algebraic methods are two typical well known developed techniques. Actually, Petri nets have received much attention over the past decades to tackle deadlock problems, leading to a variety of deadlock control policies (Chen, and Li 2011; Fanti, and Zhou 2004; Hu, Zhou, and Li 2010a; Hu, Zhou, and Li 2010b; Li, Hu, and Wang 2007; Li, Liu, Hanisch, and Zhou 2012; Li, and Wei 2007; Li, Yan, and Zhou 2010; Li, and Zhao 2008; Li, and Zhou 2004; Li, and Zhou 2006; Li, and Zhou 2008a; Li, and Zhou 2008b; Li, Zhou, and Jeng 2008; Li, Zhou, and Wu 2012; Tricas 2003; Tricas, Garcia-Vallès, Colom, and Ezpeleta 2000; Tricas, Garcia-Vallès, Colom, and Ezpeleta, 2005; Tricas, and Martinez 1995; Uzam, and Zhou 2006; Uzam, and Zhou 2007; Wu 1999; Wu, Bai, and Chu 2007; Wu, Chu, Chu, and Zhou 2008a; Wu, Chu, Chu, and Zhou 2008b;Wu, Chu, Chu, and Zhou 2009; Wu, Chu, Chu, and Zhou 2010; Wu, and Zeng 2002; Wu, and Zhou 2005; Wu, and Zhou 2010; Wu, Zhou, and Li 2008; Xing, Zhou, Wang, Liu, and Tian 2011; Xing, Zhou, Yang, and Tian 2009).

A basic task with respect to deadlock control by using Petri nets as a formalism is to design a liveness-enforcing supervisor (LES), consisting of external control agents that are usually called monitors, and transitions in a plant that is an alias of a system to be controlled. The supervisor interacts with the plant such that the supervised plant is deadlock-free. Its design must consider three aspects: structural complexity, computational efficiency, and behavioral permissiveness. Structural complexity of a supervisor usually implies the number of the monitors in it, computational efficiency indicates the overheads of computing a supervisor, and behavioral permissiveness generally corresponds to the number of legal states permitted in the supervised system. A supervisor is said to be optimal if each legal state of the plant is permitted in the supervised system that is also called the controlled (net) system.

Complete Chapter List

Search this Book: