| Many phenomena in the nature and engineering fields can be viewed as discrete event dynamic systems, where deadlock-freedom is one of the important properties.. Advanced control theory and methods have been proposed by scientists and engineers in the fields. Among them, Petri nets are a widely used and very suitable mathematical tools for such systems because their discreteness, concurrence, and scholasticness. Nearly all traditional deadlock prevention policies based on Petri nets come from such a point that controls all strict minimal siphons in a net such that the net system is controlled to be deadlock-free. However, these policies have been proved to be unfeasible since the number of strict minimal siphons in the net increases exponentionally with the size of the net. For this, a novel deadlock prevention policy based on elementary siphons in a net is presented. According to this policy, not all siphons in the net are needed to be explicitly controlled except the siphons named by elementary ones because it has been proved that all strict minimal siphons can be controlled to be marked when only the elementary ones are controlled. Different from the case of strict minimal siphons in a net system, the number of elementary ones is bounded by the smaller of place count and transition count. Based on the ideas mentioned above, this thesis proves that the set of elementary siphons is not unique, while different ones may lead to different control results. As a result, the concept of an optimal set of elementary siphons is proposed and also the algorithm which can be finished in polynomial time to find such a set. With the set of optimal elementary siphons, net supervisors can generally produce maximalreachable states. Also in this thesis, a deadlock prevention policy based on MIP is illustrated by this algorithm, where all siphons in the net does not need to be found during the generation of the control policy. This makes the policy based on elementary siphons more feasible.
|
PDF Full Text Request