On Algorithms For Computing Elementary Siphons In Petri Nets And Deadlock Avoidance Policy

Deadlocks caused by improper resource allocation in ?exible manufacturing sys-tems and semiconductor production lines that are the representatives of discrete eventsystems, can directly lead to the deterioration of productivity and fatal results. Petrinets are one of commonly used mathematical tools for modeling and analysis of dis-crete event systems. Deadlock prevention and deadlock avoidance have been twoprimary methodologies for handling deadlocks in Petri nets for the last two decades. Adeadlock prevention policy provides an of?ine resource allocation mechanism , whilea deadlock avoidance one needs an online decision-making algorithm. A monitor andrelated arcs are added for every emptible minimal siphon in a plant Petri net model bytraditional deadlock prevention methods in literature. Since siphons are a structuralobject of Petri nets and in theory, their number has an exponential relationship withthe net size, the structure of a large-sized Petri net's supervisor is usually too com-plicated to manage. The theory of elementary siphons has proved that a supervisorcan be computed and its size is linear with the size of the plant net model. But siphonenumeration is required for the purpose of determining a set of elementary siphons. Astate explosion problem is the bottleneck of the traditional deadlock avoidance policiesthat ensure a live net by forbidding its evolution into deadlocks. Usually, all reachablemarkings of the net are required to be known in advance and stored in memory.This dissertation aims to tackle the limitations mentioned above and the mainresults of this research are as follows.First, by studying the structure of S3PR nets, a subclass of Petri nets, it is provedthat the rank of the complementary matrix of an S3PR net is equal to the number ofits elementary siphons. Combining Petri nets and graph theory, the definitions of re-source digraphs of an LS3PR net and resource digraphs of an S3PR net are proposedrespectively. In an LS3PR net, it is verified that there exists a bijective mapping froma strongly connected block of its resource digraph into a strict minimal siphon. In anS3PR net, it is verified that there exists a bijective mapping from a strongly connectedcontributing subdigraph of its contributing resource digraph into a strict minimal siphonin it. An algorithm is given by which the number of elementary siphons of an LS3PRnet can be determined, and it is verified that the algorithm is of polynomial complexitywith respect to the number of resource places of the plant net. Based on the aboveresults, an algorithm for determining the number of elementary siphons in an S3PR net is developed, and it is verified that in the worst case this algorithm has an exponentialcomplexity relationship with respect to the number of resource places of an S3PR net.Fortunately, in special cases this algorithm has a polynomial complexity relationshipwith the number of its resource places.Second, based on binary search, an efficient algorithm is proposed for finding aset of elementary siphons given a set of strict minimal siphons of a Petri net.Third, by studying structural properties, extended complementary set of a siphonand extended complementary matrix of an ES3PR net, a subclass of Petri nets, arenewly defined. It is proved that the rank of extended complementary matrix of anES3PR net is equal to the number of its elementary siphons. Based on these newconcepts, the resource digraphs of an ELS3PR net are accordingly proposed. It isproved that a strongly connected block of the resource digraph of an ELS3PR netcorresponds to a siphon in it. Furthermore, a method to find the set of strict minimalsiphons is proposed.Fourth, a two-step deadlock avoidance policy is proposed. The first step is anof?ine method for calculating special markings, such as dead markings, bad markings,and dangerous markings, of the Petri net model of the system to be controlled. Thesecond step is an online method that makes sure that the system never reaches aforbidden state such as dead markings and bad markings. The major advantage ofthis policy lies in the fact that it is suitable for much larger systems than the mostavailable ones and the supervisory controller is maximally permissive. Meanwhile, thecomputation of the whole reachability graph of the Petri net is successfully avoided.The role of elementary siphons is fully and gradually recognized in simplifying thestructural complexity of liveness-enforcing Petri net supervisors. This research is ofsignificance to the theory of Petri nets and the supervisory control of discrete eventsystems in a Petri net formalism.