Maximally permissive liveness-enforcing supervisor with lowest implementation cost for flexible manufacturing systems

This paper develops a place invariant based deadlock prevention method to obtain a maximally permissive Petri net supervisor with the lowest implementation cost. A supervisor consists of a set of control places and the arcs connecting control places to transitions. We assign an implementation cost for each control place and control and observation costs for each transition. Based on reachability graph analysis, maximal permissiveness can be achieved by designing place invariants that prohibit all first-met bad markings but no legal markings. By solving an integer linear programming problem (ILPP), a set of optimal control places are obtained and the objective function is used to minimize the implementation cost of the final supervisor. A vector covering approach is used to reduce the number of considered markings, aiming to reduce the computational overhead of the proposed method. Finally, a number of examples are proposed to illustrate the proposed approach.