Two-stage deadlock prevention policy based on resource-transition circuits

This paper presents a suboptimal deadlock controller for a class of manufacturing systems of sequential processes with resources, where deadlocks are characterized by saturated maximal perfect resource-transition circuits (MPRT-circuits), and the controller consists of two parts. In the maximally permissive Petri net controller, which avoids all MPRT-circuits being saturated, some control places are redundant. By deleting all redundant control places and their related arcs, the first part of our controller, non-redundant controller, is obtained. In the controlled system with the non-redundant controller, deadlocks may occur if the system contains crucial resources. Then we propose for the first time the concept of the maximal perfect control-transition circuits (MPCT-circuits), which is used to characterize the deadlock in the controlled system with the non-redundant controller. When deadlock occurs under a reachable marking, some MPCT-circuits in the controlled system become empty. The Petri net controller to prevent all MPCT-circuits from being empty is the second part of our controller. It is proved that the controller consisting of two parts can guarantee the liveness of the controlled system.