Optimization Algorithm Of A Liveness-enforcing Supervisor For FMS Based On The Theory Of Regions

In recent years, the theory of regions as a new deadlock prevention strategy can derive a maximally permissive liveness-enforcing Petri net supervisor if such a supervisor exists. However, it suffers from a number of technical problems with the increase of the size of a Petri net plant model, which are the state explosion problem and the iterative solving linear programming problems, leading the inhibitive computational complexity.This research first generates a complete reachability graph for a Petri net system. The control places are designed and added by the reachability conditions, cycle equations, and separation conditions. And then combining with the characteristics of ordinary nets, we improve the separation conditions. A set of elementary separation conditions are obtained. By solving such a set of separation conditions, a set of control places is computed for the original plant model. Finally, a liveness-enforcing supervisor with simple structure and maximally permissive behavior is obtained by eliminating redundant control places. Case study shows that the method can lower computational complexity of the theory of regions. To some certain extent, the proposed method improves the computational complexity problem resulting from state explosion and solution to the linear programming problems. The number of control places which is needed to add for any ordinary net system will not exceed the smaller of the number of separation instances and |T|+1. By the algorithm formulated in this study, a liveness-enforcing supervisor of FMS with simple structure and maximally permissive behavior can be found.