This chapter proposes a number of deadlock prevention polices for a class of generalized Petri nets, namely G-systems, which is usually considered to be the most generalized Petri nets that can model Flexible Manufacturing Systems (FMSs) with machining, assembly, and disassembly operations. First, a deadlock prevention policy based on elementary siphons theory is presented, which indicates that structural complexity and behavioral permissiveness can be improved effectively. In order to reduce the computational complexity, a Mixed Integer Programming (MIP)-based deadlock detection approach is proposed, then two deadlock control polices combined with MIP method are introduced. Finally, comparison among deadlock prevention policies reported in this chapter is done in terms of structural complexity, behavioral permissiveness, and computational complexity of the resulting supervisor through a typical case study. Importantly, future research directions related to this area are presented at the end of this chapter.
Top1. Introduction
Deadlock problems can cause unnecessary costs because of long downtime and low use of some critical and expensive resources in a Flexible Manufacturing System (FMS). Over the last two decades, a great deal of research has been focused on solving deadlock problems in an FMS, receiving an enormous amount of attention (Ezpeleta et al. 1995; Huang, 2007; Iordache and Antsaklis, 2006; Li and Zhou, 2004; Li et al. 2008; Park and Reveliotis, 2001; Uzam and Zhou, 2006; Wu and Zhou, 2007). Specially, deadlock prevention is considered to be one of most effective methods in deadlock control, which is usually achieved by adding monitors to ensure that deadlocks can never occur. In this case, the computation is carried out off-line in a static way and once the control policy is established, the system can no longer reach deadlock states. Due to its advantage, deadlock prevention in generalized Petri nets has resulting in various fruits in deadlock control (Chao, 2009; Li and Hu, 2007; Li and Zhao, 2008; Zhao and Li, 2009; Zhao et al. 2010). Since most deadlock prevention polices are developed according to the relationship between liveness and siphons, the siphon-based control methods (Barkaoui and Pradat-Peyre, 1996; Chao, 2007; Chu and Xie, 1997; Reveliotis, 2007) play an important role in the development of liveness-enforcing Petri net supervisors for an FMS. Meanwhile, since the generalized Petri nets have good ability of modeling with multiple resource requirements, it can be used to model more general automated manufacturing systems. Therefore, the deadlock control in a generalized net is much more complicated than ordinary nets. From the points of structural complexity, computational complexity and behavioral permissiveness, it is necessary to facilitate engineers in choosing a suitable control method for industrial application.
This chapter intends to present and compare a variety of siphon-based deadlock prevention policies for G-systems, a class of generalized Petri nets, which can model many flexible manufacturing systems. The deadlock prevention policies underlying Petri net formalisms in this chapter are developed on the basis of either the concept of elementary siphons or MIP-based detection method. Falling into the first category, elementary siphons theory is an important method for controlling of discrete event systems. Its appearance is followed by numerous research aiming to reduce the structural complexity of the controlled system (Li and Zhao, 2008; Li and Zhou, 2004). As for MIP-based detection method, it can usually provide a computationally effective supervisor since the complete state enumeration is avoided. To inherit and reserve the advantages of two classes of approaches, this chapter applies a deadlock prevention policy based on the elementary siphons theory and MIP-based detection method to an application subclass of generalized Petri nets.
The rests of this chapter are organized as follows. Section 2 introduces the basic definitions of G-systems. An elementary siphon-based deadlock prevention method is developed in Section 3. Section 4 proposes two deadlock prevention methods by using MIP-based deadlock detection method. A case study is given in Section 5 to demonstrate the proposed method. Conclusions and future research directions are finally presented.