Deadlock Prevention Policies For FMS Based On Elementary Siphons

This thesis develops a methodology to synthesize supervisors for a special class of Petri nets that can well model many flexible manufacturing systems. In our previous work, siphons in a Petri net are divided into elementary and dependent ones on the condition that all emptiable siphons are computed, which is very time-consuming when the size of the system is large. In this research, a method is developed to find all elementary siphons whose number is bounded by the smaller of place count and transition count, without complete siphon enumeration for the class of Petri nets. For each elementary siphon, a monitor is added to the plant model such that it is invariant-controlled. Our method guarantees that no emptiable control-induced siphon is generated due to the addition of the monitors. When all elementary siphons are controlled, the controllability of a dependent siphon may be ensured by that of its related elementary siphons and verified by mixed integer programming techniques. Compared with the existing approaches, the novel deadlock prevention policy can lead to a structurally simple liveness-enforcing supervisor by adding only a small number of monitors and arcs. More importantly, complete siphon enumeration is avoided since only elementary siphons are explicitly found and then controlled. A sizable FMS example is utilized to illustrate the proposed methods.