Non-pure Petri Net For Optimal Deadlock Prevention Policy Using Theory Of Regions

Flexible manufacturing systems are automated manufacturing systems that can be employed for the batch processing of parts.Because of their high adaptability,they can flexibly switch processing objects.The systems have attracted much attention from many researchers and enterprises.However,the occurrence of deadlock greatly limits the resource utilization of flexible manufacturing systems and may cause great economic losses.Deadlock problems of flexible manufacturing systems are an interesting and significant problem.Deadlock prevention policies are offline strategies that can effectively solve the deadlock problems.When a supervisor designed for a system according to these policies is added to the original system,deadlocks cannot occur.Petri nets are one of the tools to solve the deadlock problems of flexible manufacturing systems.When Petri nets are used to model systems,all permissive behaviors of a system can be obtained by calculating and analyzing the reachability graph of a Petri net model.While the addition of a supervisor designed according to the deadlock prevention policy for the system may result in the restriction of some permissive behaviors of the initial system,optimal deadlock prevention policies can retain all permissive behaviors.The theory of regions can be used to achieve optimal deadlock control,which not only avoids deadlocks but also retains all permissive behaviors.At present,all Petri net supervisors designed through the supervisor synthesis method of supervisors based on the theory of regions are pure,which implies there are no self-loops.In fact,the existing P-invariant-based supervisor synthesis methods have proved that for some Petri nets,optimal pure Petri net supervisors do not exist.However,there are optimal non-pure Petri net supervisors.This thesis proposes a method of synthesizing a non-pure Petri net supervisor based on the theory of regions.It also can design an optimal non-pure Petri net liveness-enforcing supervisor for the Petri net without an optimal pure Petri net liveness-enforcing supervisor to achieve optimal deadlock control.The existing theory of regions has provided a synthesis method for obtaining a general Petri net with a reachability graph that is isomorphic to the given graph from a given finite directed graph.And the necessary and sufficient conditions for the existence of such a Petri net have been given.The main work completed in this thesis is described as follows.First,the general Petri net synthesis method based on the theory of regions is reinterpreted using Petri nets.Second,the synthesis method is applied to the Petri net deadlock prevention policy,and the synthesis method of non-pure Petri net supervisors is obtained.The designed supervisor is a feasible solution that satisfies the necessary and sufficient conditions for the existence of the optimal non-pure Petri net supervisor.Any self-loop in the supervisor only exists between a control place and a transition disabled by it.The design of the supervisor is divided into two steps.In the first step,all legal markings are identified from the reachability graph of an initial Petri net,and the reachability graph corresponding to the legal markings is used as a given graph.The second step is to design an optimal non-pure Petri net liveness-enforcing supervisor for the initial Petri net by using the method proposed in this thesis.The existence of such a supervisor ensures that all legal markings are retained,and no illegal markings are reachable in the controlled system,which implies that the designed supervisor is optimal.In the specific implementation of this method,the optimal non-pure Petri net liveness-enforcing supervisor is determined by solving a set of linear constraint equations.If the equations have a solution,the designed supervisor can achieve optimal deadlock control.Finally,the vector covering technique is used to simplify the constraints that the controller satisfies,which greatly reduces the scale of the linear equations and mitigates the computational complexity of the proposed supervisor synthesis method.