A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems
---
paper_title: Petri Net Synthesis for Discrete Event Control of Manufacturing Systems

paper_content:

List of Figures. List of Tables. 1. Introduction. 2. Petri Nets and Manufacturing Systems. 3. Parallel Mutual Exclusions. 4. Sequential Mutual Exclusion. 5. Hybrid Synthesis of Petri Nets. 6. Illustration of Hybrid Synthesis. 7. Discrete Event Control of FMS. 8. Augmentation of Petri Nets. 9. Petri Nets: Past, Present and Future. Appendix A. Bibliography. Index.
---
paper_title: A Survey and Comparison of Petri Net-Based Deadlock Prevention Policies for Flexible Manufacturing Systems

paper_content:

Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases.
---
paper_title: Deadlock Resolution in Automated Manufacturing Systems: A Novel Petri Net Approach

paper_content:

Deadlock problems in flexible manufacturing systems (FMS) have received more and more attention in the last two decades. Petri nets are one of the more promising mathematical tools for tackling deadlocks in various resource allocation systems. In a system modeled with Petri nets, siphons are tied to the occurrence of deadlock states as a structural object. The book systematically introduces the novel theory of siphons, traps, and elementary siphons of Petri nets as well as the deadlock control strategies for FMS developed from it. Deadlock prevention methods are examined comparatively. The many FMS examples presented to demonstrate the concepts and results of this book range from the simple to the complex. Importantly, to inspire and motive the reader s interest in further research, a number of interesting and open problems in this area are proposed at the end of each chapter. Deadlock Resolution in Automated Manufacturing Systems is directed to control, computer, electrical, mechanical, and industrial engineers, researchers and scientists. It will be useful for designers in the automation and control disciplines in industry and academia who need to develop the control methods, tools and software to improve the performance of automated flexible manufacturing systems.
---
paper_title: Parallel and sequential mutual exclusions for petri net modeling of manufacturing systems with shared resources

paper_content:

A theoretical basis for Petri net synthesis methods is provided that can be used to model systems with shared resources, and to make the resulting nets bounded, live, and reversible. Two resource-sharing concepts, parallel mutual exclusion (PME) and sequential mutual exclusion (SME), are formulated in the context of the Petri net theory. A PME models a resource shared by distinct independent processes, and an SME is a sequential composition of PMEs, modeling a resource shared by sequentially related processes. The conditions under which a net containing such structures remains bounded, live, and reversible are derived. >
---
paper_title: A Petri net based deadlock prevention policy for flexible manufacturing systems

paper_content:

In this paper we illustrate a compositional method for modeling the concurrent execution of working processes in flexible manufacturing systems (FMS) through a special class of Petri nets that we call S/sup 3/PR. In essence, this class is built from state machines sharing a set of places modeling the availability of system resources. The analysis of S/sup 3/PR leads us to characterize deadlock situations in terms of a zero marking for some structural objects called siphons. In order to prevent the system from deadlocks, we propose a policy for resource allocation based on the addition of new places to the net imposing restrictions that prevent the presence of unmarked siphons (direct cause of deadlocks). Finally we present the application of this technique to a realistic FMS case. >
---
paper_title: A Maximally Permissive Deadlock Prevention Policy for FMS Based on Petri Net Siphon Control and the Theory of Regions

paper_content:

This paper addresses the deadlock problems in flexible manufacturing systems (FMS) by using a Petri net siphon control method and the theory of regions. The proposed policy consists of two stages. The first one, called siphons control, is to add, for every siphon that we identify, a monitor to the original net model such that it is optimally invariant controlled. In the second stage, the theory of regions is utilized to derive the net supervisors such that deadlocks can be prevented. The first-stage work significantly lowers the computational cost compared with the approach where the theory of regions is used alone. An FMS example is presented to illustrate the technique. By varying the markings of given net structures, this paper shows its computational advantages.
---
paper_title: On the siphon-based characterization of liveness in sequential resource allocation systems

paper_content:

One of the most interesting developments from, both, a theoretical and a practical perspective, in the emerging theory of resource allocation systems (RAS), is the characterization of the non-liveness of many RAS classes through the Petri net (PN)-based structural object of empty, or more generally, deadly marked siphon. The work presented in this paper seeks to develop a general theory that provides a unifying framework for all the relevant existing results, and reveals the key structures and mechanisms that connect the RAS non-liveness to the concept of deadly marked - and in certain cases, empty - siphon. By taking this generalizing approach, the developed results allow also the extension of the siphon-based characterization of non-liveness to broader RAS classes, and provide a clear and intuitive explanation for the cases where the RAS non-liveness cannot be attributed to such a siphon-based construct.
---
paper_title: An optimal-elementary-siphons-based iterative deadlock prevention policy for flexible manufacturing systems

paper_content:

Petri nets have been proved to be a tool with prominent capabilities to describe discrete event systems, such as flexible manufacturing systems (FMS), thanks to their excellent properties over other models. Characterization in terms of special structural elements in a Petri net called siphons has been a major approach for the investigation of deadlock-freeness in context of FMS. Utilizing the optimal elementary siphons and the modified mixed integer programming (MIP) algorithm proposed in this paper, one can detect and solve deadlock problems arising in FMS in an iterative mode with tractable computational complexity. Moreover, the MIP approach can be exploited to implement the flexibility enhancement in the resultant net system so that the obtained system is less restricted. In contrast to the conventional typical policies, this approach evolves without explicitly enumerating all the strict minimal siphons. Its legitimacy and feasibility are proved and validated through an experimental study.
---
paper_title: Deadlock control of flexible manufacturing systems via invariant–controlled elementary siphons of petri nets

paper_content:

Effective resolution for deadlock problems plays an important role in the operation of automated flexible manufacturing systems (FMS). Based on P-invariants and elementary siphons of Petri nets, a deadlock prevention policy is developed for a special class of Petri nets that can well model many FMS. Siphons in a plant net model are divided into elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that the siphon is invariant-controlled. Our method guarantees that no emptiable control-induced siphon is generated due to the addition of the monitors. When all elementary siphons are controlled, the controllability of a dependent siphon is ensured by properly setting the control depth variables of its related elementary siphons. An FMS example is utilized to illustrate the proposed methods.
---
paper_title: On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets

paper_content:

A fair amount of research has shown the importance of siphons in the analysis and control of deadlocks in a variety of resource allocation systems by using a Petri net formalism. In this paper, siphons in a generalized Petri net are classified into elementary and dependent ones, as done for ordinary nets in our previous work. Conditions are derived under which a dependent siphon is controlled by properly supervising its elementary siphons, which indicates that the controllability of dependent siphons in an ordinary Petri net is a special case of that in a generalized one. The application of the controllability of dependent siphons is shown by considering the deadlock prevention problem for a class of resource allocation systems, namely, G-system that allows multiple resource acquisitions and flexible routings in a flexible manufacturing system with machining, assembly, and disassembly operations. We develop a monitor-based deadlock prevention policy that first adds monitors for elementary siphons only to a G-system plant model such that the resultant net system satisfies the maximal controlled-siphon property (maximal cs-property). Then, by linear programming, initial tokens in the additional monitors are decided such that liveness is enforced to the supervised system. Also, a simplified live marking relationship for a G-system between the initial tokens of the source places and those of the resource places is derived. Finally, the proposed deadlock prevention methods are illustrated by using an example.
---
paper_title: Resource-Transition Circuits and Siphons for Deadlock Control of Automated Manufacturing Systems

paper_content:

The resource-transition circuit ( RTC) and siphon are two different structural objects of Petri nets and used to develop deadlock control policies for automated manufacturing systems. They are related to the liveness property of Petri net models and thus used to characterize and avoid deadlocks. Based on them, there are two kinds of methods for developing deadlock controllers. Such methods rely on the computation of all maximal perfect RTCs and strict minimal siphons (SMSs), respectively. This paper concentrates on a class of Petri nets called a system of simple sequential processes with resources, establishes the relation between two kinds of control methods, and identifies maximal perfect RTCs and SMSs. A graph-based technique is used to find all elementary RTC structures. They are then used to derive all RTCs. Next, an iterative method is developed to recursively construct all maximal perfect RTCs from elementary ones. Finally, a one-to-one correspondence between SMSs and maximal perfect RTCs and, hence, an equivalence between two deadlock control methods are established.
---
paper_title: Clarifications on the Definitions of Elementary Siphons in Petri Nets

paper_content:

The concept of elementary siphons of Petri nets is first proposed in our previous work. However, their definitions can cause confusion when there exist weakly independent siphons in a net. In this correspondence, we redefine elementary siphons and show the significance of this improvement
---
paper_title: Liveness enforcing supervision for sequential resource allocation systems: State of the art and open issues

paper_content:

Liveness-enforcing supervision of sequential resource allocation systems is currently a well-defined problem, underlying the operation of many contemporary technological systems, spanning a wide spectrum of applications. This technical note provides a brief overview of the currently available results, delineating, both, our major analytical understandings/characterizations concerning the problem concepts/structure and its complexity, and also, our ability to synthesize effective and computationally tractable solutions to it. The last part of the document identifies open/unaddressed research issues, the resolution of which will extent the power of the current theory and will allow the integration of the developed results in the broader control frameworks managing the behavior of these environments.
---
paper_title: Combined Siphon and Marking Generation for Deadlock Prevention in Petri Nets

paper_content:

In Petri-net (PN) modeling of flexible manufacturing systems, deadlock prevention is often addressed by means of siphon-control methods. Constraints that avoid the emptying of siphons can be easily implemented using additional places suitably connected to the PN transitions. Efficient siphon-based techniques achieve highly permissive solutions using as few control places as possible. One such technique employs a set-covering approach to optimally match emptiable siphons to critical markings. In this paper, a modified version of the method is proposed that achieves the same results in terms of permissivity and size of the control subnet but avoids full siphon enumeration. This greatly reduces the overall computational time and memory requirements and allows the applicability of the method to large-size models.
---
paper_title: Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems

paper_content:

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.
---
paper_title: On Siphon Computation for Deadlock Control in a Class of Petri Nets

paper_content:

As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.
---
paper_title: New controllability condition for siphons in a class of generalised Petri nets

paper_content:

Over the last two decades, a number of deadlock control policies based on Petri nets were proposed for flexible manufacturing systems (FMSs). As a structural object of a Petri net, siphons are widely used in deadlock control. For system of sequential systems with shared resources (S4R), the current deadlock control policies based on max or max′-controlled siphons tend to overly restrict the behaviour of a controlled system. The controllability conditions of a siphon are relaxed by a new concept called max″-controlled ones. We conclude that an S4R is live if all its siphons are max″-controlled. Compared with the existing ones, the proposed one is more general. Examples are given to illustrate it.
---
paper_title: Structural conditions of systems of simple sequential processes with resources nets without weakly dependent siphons

paper_content:

For the purpose of deadlock control, siphons in a Petri net (PN) can be divided into elementary and dependent ones; the latter can further be distinguished by strongly and weakly dependent siphons (WDS). The computation of the elementary siphons in a PN is essential but expensive since a complete siphon enumeration is needed. The results reported in the literature show that the control of WDS is quite conservative. Li et al. present two open problems. First, for what kinds of PN, we can definitely find a set of elementary siphons such that no WDS can be derived? Secondly, could we develop an algorithm to find a set of elementary siphons that can minimise the number of WDS in a net? The aim here is to answer the first problem for an systems of simple sequential processes with resources (S3PR) by investigating its structural conditions under which there are no WDS in it. The authors address such an issue by using an incremental approach for the synthesis of subnets (to compute an strict minimal siphon) of a strongly connected resource component. At each step, the authors add a PP-handle Hi with at least one interior resource place. The structural condition for the absence of WDS is derived and show that the maximal class of S3PR is a 2c+-system.
---
paper_title: A Survey and Comparison of Petri Net-Based Deadlock Prevention Policies for Flexible Manufacturing Systems

paper_content:

Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases.
---
paper_title: A Deadlock Prevention Policy for a Class of Petri Nets S^3PMR

paper_content:

This paper focuses on the problem of deadlocks in automated flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. A deadlock prevention policy is proposed for a subclass of Petri nets, S^3PMR that can well model a large class of FMS. We distinguish siphons in such a net model by elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that it is invariant-controlled. The monitor addition way guarantees that no emptiable control-induced siphon is generated due to the presence of monitors in the resultant net. This novel deadlock prevention policy can usually lead to a more permissive supervisor by adding a small number of monitors and arcs than the existing methods for the design of liveness-enforcing Petri net supervisors. Experimental study indicates that the proposed policy appears to be more permissive than closely related approaches in the literature.
---
paper_title: Selective Siphon Control for Deadlock Prevention in Petri Nets

paper_content:

Deadlock prevention is a crucial step in the modeling of flexible manufacturing systems. In the Petri net framework, deadlock prevention policies based on siphon control are often employed, since it is easy to specify generalized mutual exclusion constraints that avoid the emptying of siphons. However, such policies may require an excessive computational load and result in impractical oversized control subnets. This is often a consequence of the redundancy in the control conditions derived from siphons. In this paper, a novel method is proposed that provides small size controllers, based on a set covering approach that conveniently relates siphons and markings. Some examples are provided to demonstrate the feasibility of the approach and to compare it with other methods proposed in the literature.
---
paper_title: Design of Liveness-Enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets

paper_content:

This correspondence develops a methodology to synthesize supervisors for a special class of Petri nets that can well model many flexible manufacturing systems. In our previous work, siphons in a Petri net are divided into elementary and dependent ones on the condition that all emptiable minimal siphons are computed. In this research, a mixed integer programming (MlP)-based deadlock detection technique is used to find some, in general not all, minimal siphons in a plant model without complete siphon enumeration. For each siphon found, depending on its noncontrollability, a monitor is added such that it is invariant-controlled. Our siphon control method guarantees that no emptiable control-induced siphon is generated due to the addition of the monitors. The siphon control process proceeds iteratively until there is no unmarked siphon in the supervisor of a plant model. Compared with the existing approaches, the novel deadlock prevention policy can usually lead to a structurally simple liveness-enforcing supervisor by adding only a small number of monitors and arcs. More importantly, complete siphon enumeration is avoided. A practical flexible manufacturing system (FMS) example is utilized to illustrate the proposed methods.
---
paper_title: A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net

paper_content:

This correspondence corrects an algorithm by Huang et al. [International Journal of Production Research, 2001, 39, 283–305] that is used in the development of a deadlock prevention policy for a class of flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. The algorithm was initially designed to derive a minimal siphon from a maximal unmarked siphon that can be obtained due to the MIP (Mixed Integer Programming)-based deadlock detection method. Also, some minor mistakes detected in the same paper are corrected.
---
paper_title: Direct minimal empty siphon computation using MIP

paper_content:

We propose a revised mixed-integer programming (MIP) method to directly compute unmarked siphons with a minimal number of places. This eliminates the need to deduce a minimal siphon from an unmarked maximal siphon obtained from the traditional MIP method proposed by Chu et al. The revised MIP test reports smaller siphons earlier than larger siphons and adds monitors to basic siphons before compound siphons. This results in adding fewer monitors and reaching more states.
---
paper_title: Deadlock prevention policy based on Petri nets and siphons

paper_content:

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...
---
paper_title: Deadlock analysis of Petri nets using siphons and mathematical programming

paper_content:

This paper exploits the potential of siphons for the analysis of Petri nets, It generalizes the well-known Commoner condition and is based on the notion of potential deadlocks which are siphons that eventually become empty. A linear programming based sufficient condition under which a siphon is not a potential deadlock is obtained. Based on the new sufficient condition, a mathematical programming approach and a mixed-integer programming approach are proposed for checking general Petri nets and structurally bounded Petri nets respectively without explicitly generating siphons. Stronger results are obtained for asymmetric choice nets and augmented marked graphs. In particular, we show that an asymmetric choice net is live iff it is potential-deadlock-free and an augmented marked graph is live and reversible iff it is potential-deadlock-free.
---
paper_title: Enumeration algorithms for minimal siphons in Petri nets based on place constraints

paper_content:

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.
---
paper_title: Technical note—reducing mip iterations for deadlock prevention of flexible manufacturing systems

paper_content:

We propose adding monitors to each basic siphon and find conditions for a compound siphon to be already controlled. This (1) relieves the problem of siphon enumeration, which grows exponentially, and (2) reduces the number of subsequent time-consuming mixed integer programming (MIP) iterations.
---
paper_title: Control of Elementary and Dependent Siphons in Petri Nets and Their Application

paper_content:

The importance of siphons is well recognized in the analysis and control of deadlocks in a Petri net. To minimize the number of siphons that have to be explicitly controlled, siphons in a net are divided in a net into elementary and dependent ones. The concepts of token-rich, token-poor, and equivalent siphons are newly presented. More general conditions under which a dependent siphon can be always marked are established. The existence of dependent siphons in a Petri net is investigated. An algorithm is developed to find the set of elementary siphons in a net system for deadlock control purposes. The application of the proposed elementary siphon concept to the existing deadlock control policies is discussed. A few different-sized manufacturing examples are used to demonstrate the advantages of elementary siphon-based policies. The significant value of the proposed theory via a particular deadlock control policy is shown. Finally, some interesting and open problems are discussed.
---
paper_title: Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems

paper_content:

Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.
---
paper_title: Two-Stage Method for Synthesizing Liveness-Enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets

paper_content:

This paper develops a two-stage approach to synthesizing liveness-enforcing supervisors for flexible manufacturing systems (FMS) that can be modeled by a class of Petri nets. First, we find siphons that need to be controlled using a mixed integer programming (MIP) method. This way avoids complete siphon enumeration that is more time-consuming for a sizable plant model than the MIP method. Monitors are added for only those siphons that require them. Second, we rearrange the output arcs of the monitors on condition that liveness is still preserved. The liveness is verified by an MIP-based deadlock detection method instead of much time-consuming reachability analysis. Experimental studies show that the proposed approach is more efficient than the existing ones and can result in more permissive and structurally simpler liveness-enforcing supervisors than all the known existing methods. This paper makes the application of siphon-based deadlock control methods to industrial-size FMS possible
---
paper_title: Real-Time Management of Resource Allocation Systems: A Discrete Event Systems Approach

paper_content:

Resource Allocation Systems: Concepts and Problems.- Logical Control of Disjunctive / Conjunctive Resource Allocation Systems.- Sequential RAS Admitting Optimal Nonblocking Supervision of Polynomial Complexity.- Polynomial-Kernel Nonblocking Supervisory Control Policies for Single-Unit RAS.- Logical Control of RAS with Complex Process Flows.- Performance-Oriented Modelling and Control of Logically Controlled RAS.- Epilogue.
---
paper_title: Modeling and Supervisory Control of Railway Networks Using Petri Nets

paper_content:

In this paper, we deal with the problem of modeling railway networks with Petri nets so as to apply the theory of supervisory control for discrete event systems to automatically design the system controller. We provide a modular representation of railway networks in terms of stations and tracks including sensors and semaphores. We first ensure safeness and local liveness imposing both generalized mutual exclusion constraints and constraints also involving the firing vector. The detailed model used in this first step can be abstracted, considering a higher level description of a railway network that belongs to the class of ES PR (extended simple sequential process with resources) nets and show that global liveness may be enforced by adding appropriate monitor places designed using siphon analysis. In our approach, this can be done without an exhaustive computation of all siphons and we can characterize the cases in which the procedure can be recursively applied, giving a simple test for closed-loop net to remain an ES PR net.
---
paper_title: Siphon-Based Deadlock Prevention Policy for Flexible Manufacturing Systems

paper_content:

A siphon-based algorithm for deadlock prevention of a type of Petri nets called S3PMR, which is a subclass of S3PGR2, is presented in this correspondence. The proposed method is an iterative approach by adding two kinds of control places called ordinary control (OC) places and weighted control (WC) places to the original model to prevent siphons from being unmarked. An OC place with ordinary arcs, which optimally prevent a siphon from becoming unmarked, is employed whenever it is possible, and otherwise, the WC places that adopt a conservative policy of controlling the release of parts into the system are used. Furthermore, this algorithm is not only for the subclass Petri nets but also for S3PR, ES 3PR, S2LSPR, and S3PGR2 nets. The authors prove the liveness and reversibility of the controlled net, and hence establish the correctness of the deadlock prevention policy. Finally, numerical experiments indicate that the proposed policy appears to be more permissive than closely related approaches in the literature
---
paper_title: Comments on "Siphon-Based Deadlock Prevention Policy for Flexible Manufacturing Systems

paper_content:

A siphon-based algorithm for deadlock prevention of Petri nets called Algorithm H2 is proposed in the above paper. However, the illustrative examples for Algorithm H2 are incorrect because of the redundant weighted control (WC) places which control some marked siphons. This correspondence modifies the illustrative examples by removing the redundant control places and getting a maximally permissive control for the original net. As no WC place is presented in the modified examples, the examples cannot well illustrate Algorithm H2.
---
paper_title: An Effective Algorithm to Find Elementary Siphons in a Class of Petri Nets

paper_content:

As a structural object of Petri nets, siphons play a key role in the development of deadlock prevention policies for resource allocation systems. Elementary siphons are a novel concept in net theory. Based on graph theory, this paper proposes an effective algorithm with polynomial complexity to find a set of elementary siphons for a linear system of simple sequential processes with resources (LS3 PR), a subclass of Petri nets, which can model many flexible manufacturing systems. The algorithm is established through the use of a resource directed graph and complementary sets of strict minimal siphons (SMS) of the net. The upper bound of the number of SMS in such a net is identified. A running example is used to demonstrate the proposed method.
---
paper_title: A method of computing strict minimal siphons in an S3PR based on resource circuits

paper_content:

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.
---
paper_title: Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems

paper_content:

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.
---
paper_title: Linear algebraic calculation of deadlocks and traps

paper_content:

It is shown how deadlocks and traps of a class of place/transition-nets can be calculated as S-invariants of marked graphs.
---
paper_title: Necessary and sufficient conditions for resultant siphons to be controlled

paper_content:

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.
---
paper_title: Deadlock prevention policy based on Petri nets and siphons

paper_content:

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...
---
paper_title: Enumeration algorithms for minimal siphons in Petri nets based on place constraints

paper_content:

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.
---
paper_title: A New Technique for Finding a Generating Family of Siphons, Traps and st-Components. Application to Colored Petri Nets

paper_content:

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ΣΘ).
---
paper_title: Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution

paper_content:

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
---
paper_title: Controllability Conditions of Resultant Siphons in a Class of Petri Nets

paper_content:

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.
---

Title: A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems

Section 1: Introduction
Description 1: This section introduces the importance of the manufacturing industry and the necessity of deadlock prevention in flexible manufacturing systems (FMS) using Petri nets as a control method.

Section 2: Deadlock Prevention
Description 2: This section reviews typical deadlock prevention strategies developed using Petri nets and discusses their historical significance and impact on the field.

Section 3: The Present of Deadlock Prevention
Description 3: This section discusses the historical development of Petri net-based deadlock prevention methods and their evolution, including notable contributions and their limitations.

Section 4: Deadlock Prevention and Siphon
Description 4: This section explores the role of siphons in deadlock prevention within Petri nets and examines methods for computing and utilizing strict minimal siphons to design deadlock prevention policies.

Section 5: The Fast Calculation Approaches of Strict Minimal Siphons
Description 5: This section presents various computational approaches for efficiently calculating strict minimal siphons and addresses their application within different classes of Petri nets.

Section 6: Conclusion
Description 6: This section summarizes the deadlock control problem in high automated systems, discussing current challenges and the need for improvements in deadlock prevention methods to achieve higher efficiency and adaptability.