A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> It is shown how deadlocks and traps of a class of place/transition-nets can be calculated as S-invariants of marked graphs. <s> BIB001 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> In this paper we propose a new solution to the problem of finding generating families of siphons (structural dead-locks in classical terminology), traps and st-components in Petri Nets. These families are obtained as solutions of some systems of linear inequalities. Their transformation into a system of linear equations allows to interpret the technique as follows: traps (siphons, st-components) of a net N are deduced from the support of psemiflows of a transformed net NΘ(NΣ,NΣΘ). <s> BIB002 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> This paper presents a deadlock prevention method for a class of flexible manufacturing systems where deadlocks are caused by unmarked siphons in their Petri net models. This method is an iterative approach consisting of two main stages. At each iteration, a fast deadlock detection technique developed by mixed integer programming is used to find an unmarked maximal siphon. An algorithm is formalized that can efficiently obtain an unmarked minimal siphon from the maximal siphon. The first stage, called siphons control, of the proposed method is to add, for each unmarked minimal siphons, a control place to the original net with its output arcs to the sink transitions of the minimal siphon. The objective is to prevent a minimal siphon from being unmarked. The second stage, called augmented siphons control, is to add a control place to the modified net with its output arcs to the source transitions of the resultant net if the resource places are removed. The second stage is required since adding control places... <s> BIB003 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> A variety of important Petri net-based methods to prevent deadlocks arising in flexible manufacturing systems (FMS) are to add some control places and related arcs to strict minimal siphons (SMS) such that no siphon can be emptied. Since the number of minimal siphons grows in general exponentially with respect to a Petri net size, their disadvantages lie in that they often add too many additional places to the net, thereby making the resulting net model much more complex than the original one. This paper explores ways to minimize the new additions of places while achieving the same control purpose. It proposes for the first time the concept of elementary siphons that are a special class of siphons. The set of elementary siphons in a Petri net is generally a proper subset of the set of all SMS. Its smaller cardinality becomes evident in large Petri net models. This paper proves that by adding a control place for each elementary siphon to make sure that it is marked, deadlock can be successfully prevented. Compared with the existing methods, the new method requires a much smaller number of control places and, therefore, is suitable for large-scale Petri nets. An FMS example is used to illustrate the proposed concepts and policy, and show the significant advantage over the previous methods. <s> BIB004 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> The paper addresses the problem of enumerating minimal siphons in an ordinary Petri net. The algorithms developed in this work recursively use a problem partitioning procedure to reduce the original search problem to multiple simpler search subproblems. Each subproblem has specific additional place constraints with respect to the original problem. Some results on algorithm correctness, convergence, and computational complexity are provided, as well as an experimental evaluation of performance. The algorithms can be applied to enumerate minimal, place-minimal siphons, or even siphons that are minimal with respect to given subsets of places. <s> BIB005 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> Siphons are related to the liveness properties of Petri net models. This relation is strong in the case of resource allocation systems (RASs). Siphons can be used in these systems in order to both characterize and prevent/avoid deadlock situations. However, the computation of these structural components can be very time consuming or, even, impossible. Moreover, if, in general, the complete enumeration of the set of minimal siphons must be avoided (there can exist an exponential number of such components), some deadlock prevention methods rely on its (complete or partial) computation and enumeration. The special syntactical constraints of some classes of RASs can help in developing specific algorithms to compute siphons in a more efficient way. In this work, a known method for siphon computation is adapted to get advantage of the special (syntactical) structure of a class of RASs; a parallel implementation is proposed and some experimental results are presented <s> BIB006 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> In this paper, a method is proposed to compute all the strict minimal siphons (SMS) in an S3PR based on resource circuits. The concepts of A-resource subsets, B-resource subsets, and elementary B-resource subsets are proposed, which play an important role in finding SMS. Moreover, it is proved in this paper that not all the resource circuits can generate SMS and SMS are generated by elementary B-resource subsets. An FMS example is used to illustrate the application of the proposed method. <s> BIB007 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> Based on key resource subsets, a necessary and sufficient condition is proposed under which a resultant siphon can be always marked if its strict minimal siphons (SMS) are optimally controlled. The proposed condition is established by analyzing the structural characteristics and markings of the resource subnets in a class of Petri nets called L-S3PR. When it is used in deadlock prevention policies, the number of monitors can be significantly reduced, thereby decreasing control implementation complexity and cost. <s> BIB008 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The fast calculation approaches of strict minimal siphons <s> Strict minimal siphons (SMSs) play a key role in the development of deadlock prevention policies by using Petri nets for flexible manufacturing systems (FMSs). In this paper, given two SMSs and their resultant siphon, the concept of key resource subsets is proposed which is shown to be the critical factor in deciding the controllability conditions of the latter. A necessary and sufficient condition is then proposed under which the resultant siphon can be always marked if its two SMSs are M-controlled, i.e., invariant controlled via the method proposed by Moody and Antsaklis. As for a resultant siphon that is composed by more than two composable SMSs, a sufficient condition is proposed under which it can be always marked if its SMSs are M-controlled. They are established by analyzing the structural characteristics and markings of the resource subnets in a class of Petri nets called L-S3PR. When they are applied to some classes of S3PR nets, i.e., those whose controlled ones are maximally permissive and live once their original SMSs are M-controlled, the number of monitors may be reduced. An FMS example is used to illustrate the application of the results. <s> BIB009
As a structural object, siphons play an important role in the analysis of structural and behavioral properties of Petri nets. An algorithm with polynomial complexity to decide whether a set of places is a minimal siphon can be found in  . Classical and typical siphon computation methods are presented in BIB002 BIB001  . A siphon computation method that is claimed to be rather efficient is developed in BIB005 , which can find 2×10 7 siphons within one hour. For a class of Petri nets, a siphon solution approach is given in  that is also efficient through experimental studies. A parallel solution to siphons is established by Tricas and Ezpeleta BIB006 . In order to apply deadlock prevention control policy into large size systems, Wang utilizes loop resource subsets to compute all the strict minimal siphons in S 3 PR. From some counterexamples, some flaws in strict minimal siphons computation-based elementary siphon theory proposed by Li and Zhou can be found. One of these flaws is that some siphons derived from resource circuit are not strict minimal ones BIB007 . Another is that redundant strict minimal siphon can be achieved with this method. The method to compute strict minimal siphons in a class of Petri net based on loop resource subsets proposed by Wang has solved aforementioned flaws and has higher computational efficiency. Moreover, sufficient and necessary conditions for loop resource subsets to generate strict minimal siphons are established, and an algorithm is proposed to find all the strict minimal siphons in an S 3 PR  . This approach is one of the most efficient methods to compute strict minimal siphons. However, this approach can only be available for S 3 PR, and it will be no use for more general nets. Motivated by the fact that deadlock control is usually concerned with unmarked strict minimal siphons in a Petri net, some scholars investigate strict minimal siphon extraction methods from a maximal unmarked siphon and achieve a lot of new contributions. This kind of method is widely used since it fits every kind of ordinary Petri net, while it suffers from low computational efficiency. For example in BIB003 BIB004 , the computational efficiency of the method which can investigate strict minimal siphon extraction methods from a maximal unmarked siphon is still NP-hard. For several kinds of Petri nets, such as S PR, etc., Wang investigates related theory and some algorithms to compute strict minimal siphons based on MIP and loop resource subsets. Meanwhile, the controllability problem of strict minimal siphons generated from loop resource subsets is researched. The set of elementary siphons in a Petri net is unique, so we should be cautious when choosing elementary siphons. In order to deal with this problem, Wang BIB009 BIB008 classifies strict minimal siphons generated from loop resource subsets into two kinds: simple and combined ones. A siphon is called a simple one when it cannot be comprised by other strict minimal siphons. It is easy to see that the set of simple siphons is evidently unique. A siphon is called combined one when it can be comprised by other strict minimal siphons. Moreover, sufficient and necessary conditions that the controllability of combined siphons can be ensured by the optimal control of simple ones is proposed. In addition, the controllability of combined siphon comprised by two simple siphons for LS  PR is proposed, while the problem for more general nets, such as S 3 PR, S 3 PMR, S 4 PR, etc., is still at issue.