The Number Of Siphons In Relation To The Structure Of LS~3PR Nets

Flexible manufacturing systems are the representatives of discrete event systems. Improper resource allocation can result in deadlock. Deadlock can directly lead to the deterioration of productivity and fatal results. Petri net is one of commonly used mathematical tools for modeling and analysis of discrete event systems. Siphon is a structural object of Petri nets. Emptied siphon is closely related to deadlock in Petri nets. Deadlock control has been a hot and difficult issue in theoretical study of Petri nets over the past two decades. Deadlock prevention and deadlock avoidance have been two primary methodologies for handing deadlocks in Petri nets. A deadlock prevention policy provides an offline resource allocation mechanism, while a deadlock avoidance one needs online decision-making algorithm. A monitor and related arcs are added for every emptiable siphon in a plant Petri net model for deadlock prevention. The structure of a Petri net’s supervisor becomes complicated with increasing number of siphons. In theory, the number of siphons in a Petri net has an exponential relationship with the net size.When LS3PRs, a subclass of Petri nets, are used to modeling flexible manufacturing systems, an emptiable siphon must be a strict minimal siphon. It was proved that there is one-to-one correspondence between a strict minimal siphon and a strongly connected sub-digraph of the resource digraph of an LS3PR net. It was also known that the number of strict minimal siphons in an LS3PR net is exponential with the number of resources places in it when the resource digraph of the LS3PR net is a complete digraph. As far as the author’s knowledge, there exists no research work on the relationship between the number of strict minimal siphons in an LS3PR net and the number of resource places in it when its resource digraph is not a complete digraph. This thesis focuses on this problem. Given n, the number of resource places in an LS3PR net, and |E|≤2·(n-1), the number of edges in its resource digraph, it is needed to determine how large the maximal number of strict minimal siphons will be and how the edges will be distributed in the resource digraph when the number of strict minimal siphons reaches its maximal value.It is easy to see that the amount of all the different distribution of edges in a resource digraph equals to Cn·(n-1)|E| where the resources number n and the edge number |E| are given. Firstly, with the help of enumeration of all the edge distribution cases satisfied the given conditions, several typical kinds of edge distribution can be obtained based on the condition that the number of strict minimal siphons in such cases is larger than that in other cases. Secondly, based on strict mathematic proof, it is proved that the maximal number of strict minimal siphons is max|П|=2n-1-1 when all the |E|=2·(n-1) edges of the resource digraph of an LS3PR net are distributed as a star-model. Furthermore, given |E|≤2·(n-1), it is also can be proved that the number of strict minimal siphons reaches its maximal value when all the edges are distributed as a star-model. According to a given resource digraph, an LS3PR net can be constructed where the number of strict minimal siphons equals to the number of strongly connected sub-digraph of the resource digraph. One other thing to note is that for the same resource digraph, different LS3PR nets can be obtained.The following problem is still an open problem:if the resource digraph of an LS3PR net meets the condition |E|>2·(n-1), and the number of strict minimal siphons reaches the maximal value, what distributing model should be taken by the edges in the resource digraph.