Design of a Maximally Permissive Liveness-Enforcing Petri Net Supervisor for Flexible Manufacturing Systems

Deadlock prevention plays an important role in the modeling and control of flexible manufacturing systems (FMS). This paper presents a novel and computationally efficient method to design optimal control places, and an iteration approach that only computes the reachability graph of a plant Petri net model once in order to obtain a maximally permissive liveness-enforcing supervisor for an FMS. By using a vector covering approach, a minimal covering set of legal markings and a minimal covered set of first-met bad markings (FBM) are computed. At each iteration, an FBM from the minimal covered set is selected. By solving an integer linear programming problem, a place invariant is designed to prevent the FBM from being reached and no marking in the minimal covering set of legal markings is forbidden. This process is carried out until no FBM can be reached. In order to make the considered problem computationally tractable, binary decision diagrams (BDD) are used to compute the sets of legal markings and FBM, and solve the vector covering problem to get a minimal covering set of legal markings and a minimal covered set of FBM. Finally, a number of FMS examples are presented to illustrate the proposed approaches. Note to Practitioners-Flexible manufacturing systems (FMS) are widely used to produce various products with a limited number of shared resources in modern factories. Deadlocks are a constant threat to the continuous run of an FMS, which often leads to catastrophic results in highly automated production systems. Based on Petri nets, deadlock prevention is achieved by using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur. Most of the present deadlock prevention methods restrict the system such that a part of permissive behavior is excluded. This often affects the utilization of resources and reduces the productivity of the whole system. In order to handle the problem, this research proposes an efficient deadlock prevention approach that can keep an FMS running with maximally permissive behavior. It can almost be applied to all FMS Petri net models having been proposed in literature. It is of both theoretical and practical significance and can interest people in academic and engineering communities.