Strict Minimal Siphons Computation And Reachable States Analysis Based On Petri Net Decomposition Techniques

A flexible manufacturing system(FMS)is a typical resource allocation system composed of limited resources,and several sequential processes.In the parallel operation of a sys-tem,competition between different processes for resources will lead to deadlocks.When the system enters a deadlock state,processes running will wait for each other's to release resources,which greatly reduces the efficiency or even leads to system paralysis.There-fore,the deadlock problem must be solved.As a mathematical tool,Petri nets are widely used to model,analyze and control flexible manufacturing systems.Deadlock prevention and control strategies based on Petri nets are generally divided into two types:one is based on structural analysis,such as from the perspective of siphon;the other is based on regional theory method,which needs to enumerate all reachable states of a Petri net.Therefore,strict minimal siphons(SMSs)and reachability states of a net play a key role in deadlock preven-tion control strategies of FMS.In general,the numbers of SMSs and reachable states in a net increase exponentially with the size of this net.How to efficiently calculate SMSs and reachable states of a net has become a key issue.This thesis focuses on the computation of SMSs and reachable states in a system of simple sequential processes with resources(S~3PR).The main work are as follows:1.An efficient SMS calculation method based on net decomposition is proposed.First,an S~3PR is decomposed and specific resource places are added.Then,siphons of subnets obtained by the decomposed net are calculated.Finally,by analyzing the relationship be-tween siphons of subnets and siphons of the entire net,a method for computing SMSs of an S~3PR is obtained.Compared with the efficient method based on loop resource subsets,our method has the following advantages:1)for a large-scale net,the number of siphons of subnet decreases significantly with the number of appropriate net decomposition;2)the result of subnet SMSs merging does not contain redundant data;3)our method avoids the judgment of whether the characteristic resource subnet of each resource circuit is strongly connected.Therefore,method proposed in this thesis greatly improves the efficiency of cal-culating SMSs.Examples are utilized to illustrate the efficiency of our method.2.A method of computing reachable states based on a net decomposition solution is pro-posed.First,an S~3PR is decomposed based on shared resources or shared transitions.Sec-ond,on the basis of calculating reachable states of subnets,we analyze the relationship be-tween the states of subnets and that of the entire net,and propose a method of merging states of subnets.The states of the entire net consists of two parts,one is the states of subnets,and the other is obtained by merging the states of different subnets.There are spurious states in merged states,and a method to determine spurious states in merged states is proposed.Fi-nally,the reachable states can be calculated by removing the spurious states.Experimental results are utilized to illustrate the applicability of this method.