Design of Optimal Transition-Based Supervisors for Flexible Manufacturing Systems via Resource Requirement Graphs

In this article, we introduce a novel weighted digraph, namely, a resource requirement graph, to address deadlock problems in flexible manufacturing systems (FMSs) modeled with Petri nets. A liveness-enforcing supervisor consisting of recovery transitions designed to be enabled at pre-partial deadlocks is synthesized. First, a resource requirement graph is directly derived from a Petri net model of an FMS and is used to represent competition relations for shared resources by various processes. Subsequently, the notion of pre-partial deadlock, described as a set of linear inequalities, is introduced by analyzing a resource requirement graph. Then, an algorithm is presented to develop a supervisor consisting of recovery transitions that are only enabled at the identified pre-partial deadlocks. The controlled Petri net model of an FMS under the designed supervisor is shown to be live with all initial reachable markings retained. The method proposed in this article offers computational efficiency since the resource requirement graph is structurally compact compared to its counterpart net model. Finally, several examples are provided to demonstrate the developed techniques.