Optimality Test for Control Places of Petri Net Based Liveness Enforcing Supervisors of FMSs

In the past three decades, a lot of Petri net-based methods have been proposed for deadlock prevention/liveness enforcing in flexible manufacturing systems (FMSs). Firstly, a plant Petri net model of an FMS is obtained and then the liveness enforcing supervisor (LES) or the controller is computed as a Petri net. An LES contains of a set of control places (CPs). The plant Petri net model and the LES are merged to obtain the controlled model. Once the Petri net model of an FMS is live, deadlocks never occur. When all legal markings of a Petri net model are reachable by the live system, the controlled model is called maximally permissive or optimal. If the controlled model is optimal, then all CPs are also optimal. However, when the controlled model is suboptimal, some CPs are optimal while the others are not. In order to improve behavioral permissiveness and/or to reduce the structural complexity of the CPs, it is crucial to identify the set of suboptimal CPs. This important issue has not been tackled before. To-date, when dealing with suboptimal controlled models no attention has been paid to identify both sets of optimal and suboptimal CPs. An optimality test for an LES of an FMS is proposed in this paper to address this problem. The optimality test takes an LPN model, controlled by a set of CPs, as input and in the case of suboptimal controlled models it produces both sets of optimal and suboptimal CPs. The optimality test proposed is applicable to any LPN that contains a Petri net model (PNM), controlled by means of a set of CPs. The applicability of this method is shown by considering several examples from the literature.