Deadlock Prevention For Petri Nets Based On Time Constraints

As a graphical and mathematical tool,Petri nets are widely used in modeling,analysis,and deadlock control of automated manufacturing systems(AMSs).Resource competition may cause deadlock problems of AMSs,which lead to unnecessary costs or catastrophic result-s.Therefore,in order to ensure the efficient and safe operation of AMSs,the deadlock problems must be resolved.Aiming at solving deadlock problems of AMSs,many analysis methods and control strategies based on Petri nets are proposed.However,most control strategies are implemented by adding control places and do not consider time factors in ac-tual production.In order to be more in line with the actual situation of AMSs and avoid the structure of controlled systems from being complicated,time-based deadlock prevention policies are proposed in this thesis,such that the deadlock problems of AMSs can be solved without control places.The main work is as follows:By adding suitable firing intervals to the transitions of a Petri net to schedule the firing pri-ority of transitions,the transition sequences that cause deadlocks cannot occur.There are two kinds of ideas for deadlock control,one is based on reachable state space analysis,and the other is based on structure analysis.Based on the parametric safety model checking technology of time Petri nets(TPNs),a method of adding time constraints based on marking graphs is proposed.First,we add para-metric firing intervals to the transitions of a Petri net to extend it into a parametric TPN and propose a calculation method of the extended markings for an extended TPN.Then,the algorithm of depth-first search is used to explore the extended marking graph of an ex-tended TPN and retrieve the kind and the bad transitions of each reachable marking.Next,the deadlock prevention conditions for dangerous markings and permissive conditions for good markings are established.TPN extensions whose parameter values on the firing inter-vals meet the deadlock prevention conditions are deadlock-free.On the basis of deadlock prevention conditions,the introduction of permissive conditions yields more permissive so-lutions for TPN extensions.In order to avoid the state explosion problem in marking graph-based methods,a method of adding time constraints based on siphons is proposed.First,by analyzing the relationship between siphons(SMSs)and deadlocks in a Petri net,a method of adding time constraints to an SMS is established.This method can make a siphon controlled.Then,according to the structure of SMSs,S³PRs(systems of simple sequential processes with resources)can be divided into S³PR₄)s with independent SMSs only and S³PR_{(9)s with dependent SMSs,and corresponding time constraint adding methods for these two types of nets are designed.For an S³PR4},it is controlled if each of its independent SMS is controlled by adding time constraints.An S³PR₍(9)is controlled if its dependent siphons are controlled by the time con-straints on its elementary siphons.For a GS³PR(generalized system of simple sequential processes with resources),its deadlock control is achieved by adding firing coefficients to time constraints.Finally,some examples are used to illustrate and verify the control strategies proposed in this thesis.The results show that whether from the perspective of marking graphs or siphons,a net system can be deadlock-free by adding time constraints.Compared with the traditional deadlock control strategies,these time-based deadlock control strategies mainly have advan-tages in terms of structural complexity.