A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The present of deadlock prevention <s> 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. > <s> BIB001 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> The present of deadlock prevention <s> 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. > <s> BIB002
Zhou and DiCeare BIB001 pioneered the study about Petri net-based deadlock prevention in FMS, in which modeling problem of FMS with sharing resources is proposed. They ensure the liveness of system by adding buffered modules and control places, or limiting the number of parts. The major weakness of this deadlock prevention is its conservativeness. As is known, a direct and remarkable consequence is that the productivity of a system can be deteriorated. In 1995, Ezpeleta BIB002 developed a design method of monitor-based liveness-enforcing Petri net supervisors. It is often considered to be a classical contribution that utilizes structural-analysis techniques of Petri nets to prevent deadlocks in FMS. First, a class of Petri nets, which is called S 3 PR, is proposed, and the relationship between strict minimal siphons and liveness of an S 3 PR is established. For each strict minimal siphon that can be empty at a reachable marking, a monitor is added such that it is controlled. After all siphons are controlled, liveness-enforcing Petri net supervisors are achieved. The significance of this approach lies in the fact that it successfully separates a plant net model and its supervisor. This work becomes such a spur that attracts much attention, and also has built a solid foundation for development and application of siphon theory. The years following 1995 have seen many siphon-based deadlock prevention policies in Petri nets proposed on the basis of this work. As gradually recognized, general deadlock prevention policies suffer from the following three kinds of defects: behavioral permissiveness, computational complexity, and structural complexity. The behavioral permissiveness problem is referred to as the fact that the permissive behavior of a plant net model is overly restricted by the deadlock prevention policy, namely that the supervisor excludes some admissible states. That's because the output arc of added monitor points to source transition of Petri net model, which limits the number of workpieces entering system to be released into and processed to a great extent. A source transition is the output transition of an idle place, which models the entry of raw parts into the system. Computational complexity results from the complete siphon enumeration that is necessary for computing a supervisor. In theory, the number of siphons grows exponentially with respect to the size of a net model. Structural complexity refers to that the number of monitors in a liveness-enforcing supervisor is exponential with the net model size theoretically since every strict minimal siphon that can be unmarked at a reachable marking needs a monitor to prevent from being emptied. The structural complexity of a supervisor means extra cost in system verification, validation, and implementation. Since 1995, a great deal of work has focused on solving the aforementioned problems.