On structural reduction of liveness-enforcing Petri net supervisors for flexible manufacturing systems: an algebraic approach

A deluge of studies has been carried out on deadlock prevention and liveness enforcement for flexible manufacturing systems (FMSs). This paper reports an algebraic procedure to find a set of merged place invariants, aiming to reduce the structural complexity of a liveness-enforcing Petri net supervisor for an FMS. Firstly, given an uncontrolled Petri net model, a set of control places as well as their corresponding place invariants are computed by using the existing methods. A systematic approach is developed to find a set of merged place invariants that are much more compact than the original supervisor structure, which remarkably reduces the number of control places in a liveness-enforcing Petri net supervisor for an FMS. The structurally reduced supervisor provides the same or more permissive behavior than that of an original one. As an algebraic approach, the proposed method is computationally trivial and is applicable to all manufacturing-oriented Petri net classes currently available in the literature. Several typical manufacturing examples are used to demonstrate the approach reported in this research.