Strict Minimal Siphons Computation And Liveness-enforcing Supervisor Optimization Method For S~4PR

In flexible manufacturing systems, deadlock is a state of a set of processes being blocked by waiting for each other to release resources that are needed for their further performance. Deadlocks can lead to the deterioration of the system proformance and bring to production losses. S4PR nets are a subclass of Petri nets with good modeling capabilities, and are widely used in flexible manufacturing system modeling, analysis and deadlock prevention research. In recent years, deadlock prevention policy based on S4PR has been focused by many researchers. A monitor and related arcs are added for every strict minimal siphon in a plant Petri net model by classic deadlock prevention method, which first requires the calculation of all the strict minimal siphons in the Petri net. Since the number of siphons grows exponentially with the size of the net, the liveness-enforcing Petri net supervisor designed by the classic deadlock prevention method has the problems of high computational complexity, structural complexity and low behavioral permissiveness. Aimed to solve the three problems, a deadlock prevention method for S PR is researched in this thesis. The main conclusions are summarized as follows:1. A method to calculate all the strict minimal siphons in an S4PR is proposed. First, this method builts up a C-R graph based on the relationship among resource places, then the set of all strict minimal siphons is obtained from the C-R graph by the relevant formulas, theorems and algorithms. Though the time complexity of this method is exponential in the worst cases, this method still has two advantages compared to traditional traversal method:one is that the computational scale is reduced, since it is only related with the number of resource places rather than all places in an S4PR (usually, the number of resource places is far less than that of all the places); the other is that the method avoids the state explosion problem, because reachability analysis is not needed. Therefore, this method reduces the time complexity of calculating the siphons, at the same time, it builds a foundation for optimizing liveness-enforcing supervisor of S4PR.2. A method to optimize a liveness-enforcing S4PR supervisor is proposed based on linear integer programming technique. The concepts of Petri net monitor and combination-redundant monitor in S4PR are defined as3-tuples. And for a live S4PR net in which every strict minimal siphon is controlled by one monitor, it is proved to be live still if the combination-redundant monitors and related arcs are removed while remaining their bases. By this theorem, an optimized algorithm for liveness-enforcing S4PR supervisor is proposed not only to reduce structural complexity, but also to improve behavioral permissiveness.Computational complexity, structural complexity and behavioral permissiveness are three important parameters to evaluate the deadlock prevention policy of a Petri net. Experiments show that the proposed method performs well on the three parameters. Therefore, it is an effective deadlock prevention menthod for S4PR.