Solving Siphons with the Minimal Cardinality for Deadlock Control

1. Introduction

Due to the competition of shared resources in a flexible manufacturing system (FMS), deadlock problems occur frequently (Chao,2006; Piroddi et al., 2009), which are a highly undesirable situation, leading to unnecessary costs. One way of dealing with deadlock problems is to model an FMS with Petri nets (Murata, 1989; Li & Zhou, 2009). As a particular Petri net structural object, siphons play an important role in solving deadlock problems in Petri nets, resulting in many deadlock prevention policies using siphon control (Ezpeleta et al., 1995; Li & Zhou, 2004; Huang et al., 2006; Uzam et al., 2007). These siphon-based control methods mainly consists of two phases. The first is about siphon computation and the second adds a CP to each computed siphon in order to achieve the desired control.

It is well known that the number of Strict Minimal Siphons (SMSs) in a Petri net grows quickly with respect to its size. A deadlock prevention policy using a complete siphon enumeration such as E-policy and L-policy, is time-consuming, where E-policy and L-policy are referred to the DPP in (Ezpeleta et al., 1995) and (Li & Zhou, 2004), respectively. Moreover, E-policy introduces too many additional CPs when the number of such siphons is large, leading to a much more structurally complex Petri net supervisor than the plant net model, which is impractical for large-sized systems. For this, Li and Zhou (Li & Zhou, 2004) propose the concept of elementary siphons that are a special class of SMSs and indicate that only a part of computed SMSs need to be controlled. Hence, a DPP using a partial siphon enumeration such as C-policy, H-policy, and P-policy, focuses on solving those siphons that contribute to deadlocks and then add CPs for them, which relatively reduces computational time and obtains a live controlled system with a simple structure. Note that the policies in (Chao,2009) (Huang et al., 2006) and (Piroddi et al., 2009) are denoted as C-policy, H-policy, and P-policy, respectively. The C-policy has an advantage over the others since it can directly compute a minimal siphon, which eliminates an extra step to derive a minimal siphon from a maximal unmarked siphon computed by the MIP method in (Chu & Xie, 1997). However, an MIP method in C-policy (Chao,2009) that is obtained by revising the MIP method in (Chu & Xie, 1997) suffers from a number of problems. It is only suitable for Ordinary Petri Nets (OPNs). In addition, since a PN system that models a practical FMS such as SPR (a simple sequential process with resources), SPR (systems of simple sequential processes with resources) (Ezpeleta et al., 1995), L-SPR (Linear SPR), ESPR (Extended SPR) (Huang et al., 2006) and SR (system of sequential systems with shared resources) (Li & Zhou, 2009) is self-loop free and contains one or more strongly connected state machines, the number of places in the PN is at least two. As a result, a new added constraint denotes the total number of places in a Petri net) is not accurate to solve the revised MIP problem in (Chao,2009).