MIP Based Deadlock Prevention Monitor Design For S~4PR Nets

Flexible manufacturing system is a typical class of resource allocation systems. In such systems, parallel production processes compete for limited resources. Once some of the processes have occupied part of the resources, and circular waiting for the resources occupied by other processes would lead the system into deadlocks, which prevent the system from running smoothly and cause losses. Petri net is one of the main tools to model resource allocation systems. S4PR nets, one of the subclasses of Petri nets, has been extensively applied in deadlock prevention researches recently, for its excellent modeling ability and appropriate difficulty on analysis. One of the classic deadlock prevention policies is based on siphon control. Usually, monitors are obtained on the basis of siphon’s max-controlled conditions for S4PR nets, and by constructing a P-invariant following a series of trival steps. However, we found that for a kind of certain structures in S4PR nets, the existing methods are not able to design monitors to satisfy the max-controlled conditions. In addition, the existence of unobservable and uncontrollable transitions is not considered in these methods. Therefore, this thesis develops two monitor design methods based on siphon control for S4PR nets. The main contributions are summarized as follows:(1) The existing siphon’s max-controlled conditions for S4PR nets are improved. The new conditions restrict less on the P-invariant to be constructed, and hence can be used for arbitrary S4PR nets. Accordingly, a monitor design method by solving an MIP optimization problem to construct a P-invariant is proposed. In this method, the improved max-controlled conditions and structural characteristics of monitor are given as optimization constraints, and the optimization objective is set as the minimization of supervised region to maintain the most behavior permissiveness. Compared with the classic method, the proposed one reserves the advantages of high computational efficiency and simple monitor structure. Thanks to the MIP technique, the proposed method is free of trival analysis on net structure, and is applicable to S4PR nets with unobservable transition.(2) On the basis of the previous work, an improved monitor design method is developed. In order to prevent the problem of control-induced siphons which are not max-controlled, the method proposed in point (1) restricts that the output arcs of monitor should attach to source transitions. In this way, there would be a number of legal states forbidden unnecessarily. Hence, a two-phase monitor design method is proposed, which is realized by solving an MIP optimization problem as well. The first phase designs a monitor to supervise the complementary places of a siphon and makes it max-controlled. If this monitor induces a deadly marked siphon in the resultant system, then it is redesigned in the second phase by taking the complementary places of the new siphon into the supervisory region. The second phase would be repeated till the monitor induces no more deadly marked siphon. Compared with the existing two-phase methods, the proposed one is more accurate in monitor rearrangement, and can obtain monitors that are simpler on structure. Above all things, the proposed two-phase method is able to obtain a supervisor with higher behavioral permissiveness than the existing ones.The experimental results show that the two proposed methods in this thesis are applicable to S4PR nets in which the classic method is not suitable. Reserving the advantages of efficient computation and simple structure, they have enhanced behavioral permissiveness of the resultant system at the same time. In conclusion, the two proposed methods perform well in the three criteria of valuing a Petri net based deadlock prevention strategy.