On Optimized Deadlock Control For Petri Nets Based On Structural And Reachability Graph Analysis

A flexible manufacturing system(FMS)is an automated manufacturing system consisting of numerical computer-control machine tools and a material transmission system.In an FMS,limited resources are used to process different types of raw parts concurrently.If resources are assigned improperly,there may be deadlocks.A local or global system halt caused by deadlocks greatly decreases the efficiency of the system and even brings about heavy eco-nomic losses or fatal consequences.Petri net can be used in many systems from modeling to analyzing,and controlling implementation for FMSs.Generally,deadlock prevention policies can be realized by adding monitors to a net system to prohibit deadlock states.There are three criteria in evaluating the performance of a liveness-enforcing supervisor for an uncontrolled system:structural complexity,computation complexity,and behavioral permissiveness.Based on the Petri net models(PNMs),deadlock analysis techniques are divided into two categories:structural analysis and reachability graph(RG)analysis.A siphon is a structural characteristic of Petri nets.It is closely related to deadlocks in a sys-tem.A deadlock prevention algorithm with a complete enumeration of siphons possesses exponential complexity in theory.As for reachability graph analysis,it requires generat-ing all reachable states.This does not apply to complex systems due to the state explosion problem.This thesis aims to tackle the limitations mentioned above and focuses on develop-ing a computational efficiency liveness-enforcing supervisor synthesis method based on the think-globally-act-locally method in an iterative way,which can lead to a structurally simple controlled system with optimal or near optimal permissive behavior.The main results are as follows:1.A method of computing first-met bad markings(FBMs)in an ordinary net model is proposed.Deadlock markings are determined using strict minimal siphons(SMSs),and then a part of reachability graph can be computed.FBMs can be obtained by this method without a complete siphon enumeration.This method has great efficiency on computation of FBMs in an ordinary PNM with a large scale.2.A method of designing a control place for an SMS is proposed for ES~3PR.In this method,the arc weights of the monitors are all equal to one,which ensures that the ordinary charac-teristics of the controlled Petri net are preserved.Namely the obtained net system is always an ordinary net.Furthermore,the monitors whose arc weights are all equal to one are easily to be implemented and have simpler structures than ones whose arc weights are greater than one.3.In order to circumvent a complete siphon enumeration,a minimal emptiable siphon ex-traction method based on mixed integer linear programming(MILP)problem is investigated for ES~3PR.An MILP problem is utilized to verify the liveness of a net system.A minimal emptiable siphon can be directly extracted from the net.The liveness-enforcing supervisors can be obtained by adding control places for minimal emptiable siphons.Based on the above results,this thesis develops two iterative deadlock prevention policies.The first one is used to deal with deadlocks for an ordinary Petri net.The global idle place(GIP)is temporarily introduced to prevent deadlocks in an iterative way.At each iteration,the number of tokens in the GIP is determined by the initial marking of an SMS,and a related local model is obtained.Deadlock markings are computed by SMSs.If there are deadlocks,FBMs are computed without a complete state enumeration and will be forbidden by adding monitors.The process is repeated until no deadlock marking can be computed by SMSs in the PNM.Finally,a liveness-enforcing supervisor for the original PNM can be obtained with a set of monitors.In order to avoid a state enumeration,the other method is proposed for an S~3PR.The GIP is temporarily added to the uncontrolled net system during monitor computation steps.Starting with one token and then by gradually increasing the number of tokens in the GIP at each iteration step,a related local system is obtained.An MILP problem is used to check the liveness of the local systems,and non-max-marked siphons can be extracted directly if they are not live.Monitors are designed for the non-max-marked siphons according to the proposed siphon control method.Finally,when there is no feasible solution for the MILP,all local systems are live.Then,a liveness-enforcing supervisor is obtained when the GIP is removed.Compared with the existing deadlock control methods,the proposed method leads to a liveness-enforcing supervisor with optimal or near optimal behavioral permissiveness,simple net structure,and high computational efficiency.The utilization of the resources and the productivity of a system are improved effectively.