Deadlock Prevention Policies For Petri Nets By Using Iterative Siphon-Based Control

Petri nets, as an important and efcient mathematical tool to model, analyze, evalu-ate, and design discrete event dynamic systems (DEDSs), are widely adopted in practice.Flexible manufacturing systems (FMSs), as a typical kind of DEDSs, are the importantplants and applications in which Petri nets are used constantly. Due to competition forthe limited number of sharing resources in an FMS, such as robots, machines, fxtures,bufers, and conveyor, deadlocks occur frequently in an FMS, causing that the wholesystem or a part of it cannot evolve any more. Deadlocks directly decrease the efciencyof an FMS and may lead to catastrophic results and severe economic losses. Using Petrinet techniques to cope with deadlocks in FMSs, many policies are developed. The majorstrategies are deadlock detection and recovery, deadlock avoidance, and deadlock pre-vention. The last one tackles deadlocks during the stage of system designing nor runningand requires no decisions on-line such that it can be concerned in many applications.Since deadlocks in a plant Petri net model are strongly related to siphons thatare a special object in a Petri net, i.e., once a siphon is emptied or loses all tokensunder a marking, it remains empty permanently under any subsequent markings thatare reachable from the current marking, which can prevent the related transitions fromfring and lead to the occurrences of deadlocks. Hence using techniques of siphon con-trol can eliminate deadlocks and achieve the purpose of deadlock prevention. Emptiedsiphons in ordinary Petri nets (OPNs) are controlled if they are always marked byadding control places (CPs), which can be guaranteed by the property of P-invariants.For siphons causing deadlocks in generalized Petri nets (GPNs), adding control placescan make them max-controlled by using the concept of max-controlled siphons. As aresult, adding control places to the siphons causing deadlocks in an original Petri netmodel can make those controlled such that a live controlled system is obtained. Howto fnd siphons causing deadlocks and add control places is both an important step toobtain a liveness-enforcing supervisor and the key of designing a deadlock preventionpolicy. Computational complexity, structural complexity, and behavior permissivenessare the most important criterion in evaluating the performance of a liveness-enforcingsupervisor. The objective of this dissertation is to propose an efective deadlock preven-tion policy that can deal with deadlocks in FMSs modeling with Petri nets. By using apartial siphon enumeration method, this policy can solve the siphons causing deadlocksand then add corresponding control places to those according to the complementaryset of solved siphons such that a liveness-enforcing supervisor is obtained. Moreover, a proposed approach is used to reduce the structure of a live controlled system, whichcan decrease difculty of control implementation and economic cost. The main resultspresented in this research are as follows:1. Aiming at a problem of solving siphons for an S3PR (system of simple sequentialprocess with resource) that belongs to a subclass of OPNs, by a mixed integer program-ming (MIP) method in [9], an iterative algorithm of solving an elementary siphon set isproposed. At each iteration, a feasible solution of MIP corresponds a maximal emptiablesiphon. By the way of siphon extraction and minimizing the number of resource placesin the extracted siphon, an elementary siphon is obtained. Accordingly, the markingconstraint of the complementary set of the corresponding elementary siphon is added.The iteration proceeds until no maximal emptiable siphons exist in an original net,leading to a set of elementary siphons. The proposed algorithm avoids solving all strictminimal siphons, obtains a set of elementary siphons, and improves the computationalefciency.2. For deadlocks in OPNs and an S4R (systems of sequential systems with sharedresources) that belongs to a subclass of GPNs, the concepts of place classifcation andnecessary siphons (NSs) and the corresponding deadlock prevention policy are explored.A maximal deadly marked siphon can be obtained by the MIP method in [24] duringthe iteration. By the method of place classifcation, the corresponding NS is achieved.According to the complementary set of NS, an ordinary or general CP is properly added.The iteration proceeds until the optimal solution of MIP declares, implying that nomaximal deadly marked siphons exist in the controlled net and a liveness-enforcingsupervisor is obtained. The presented policy only solves NSs and then adds CPs forthem, which can simplify the structure of the live controlled net to some degree andrealize deadlock elimination.3. By modifying the objective function and adding new constraints to an MIPmethod in [24], a revised MIP (RMIP) method is obtained and accordingly smart siphonswith the minimal cardinality as well as the minimal number of resource places can besolved by the RMIP method. Compared with the traditional partial siphon enumerationmethods, i.e., a maximal emptiable (deadly marked) siphon is frstly computed fromwhich a minimal siphon is then derived, this RMIP method can directly compute aminimal siphon. Moreover, a deadlock prevention policy using smart siphons-basedcontrol is proposed, leading to a live controlled net with a relatively simple structureand more permissive behavior.4. Many deadlock prevention policies existing in the literature are to add CPs tocope with deadlocks under the condition that makes the controlled system live, which usually leads to a liveness-enforcing Petri net supervisor with redundant CPs. Hence, aniterative algorithm of fnding and removing those redundant CPs from the live controllednet (N~+,M~+) is developed. Each CP with its related arcs is selected and removed from(N~+,M~+) in the iteration. The corresponding CP is redundant and can be removedfrom (N~+,M~+) if the optimal solution of MIP equals to the number of the remindingplaces. Otherwise, the corresponding CP is necessary and then kept in (N~+,M~+) suchthat liveness is preserved in the iteration. The proposed algorithm can simplify thestructure of the live controlled net with redundant CPs and decrease difculty of controlimplementation and economic cost. This algorithm is suitable for the live OPNs andS4R and G-system that belong to two subclasses of GPNs.