Design Of Liveness-enforcing Supervisors For FMS Based On MIP

This thesis focuses on the problem of deadlocks in automated flexible manufacturing systems (FMS). Based on Petri nets, several deadlock prevention policies are proposed for a special class of Petri nets,S~3PR. We distinguish emptiable minimal siphons in a net model by elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that it is invariant-controlled and the mixed-integer programming (MIP) technique is employed to guarantee that no emptiable control-induced siphon is generated due to the addition of the monitor. We can also use the MIP-based approach to find a maximal unmarked siphon and derive a minimal siphon from it over and over again. For each minimal siphon, a monitor is added to the plant model such that it is invariant-controlled and the mathematical programming technique is employed to guarantee that no emptiable control-induced siphon is generated due to the addition of the monitors. Both the novel deadlock prevention policies can usually lead to a more permissive supervisor by adding a small number of monitors and arcs than the existing ones in the literature for the design of liveness-enforcing Petri net supervisors.Based on the theory of regions, an optimal liveness-enforcing Petri net supervisor can be designed, but nets with large size can cause the problem of states explosion, which leads to complex computational cost. Different initial markings imply different supervisors, which need re-compute again and again. In this work, we can see that a net system will be deadlock-free if the initial marking of the supervisor satisfies a set of linear inequalities. That is to say, given a net sutructure, no matter how the initial marking changes, we can design a new supervisor by adjusting the number of tokens in the monitors, which avoid to sovle a large number of inequalities systems.