Efficient optimal deadlock control of flexible manufacturing systems

The development of an efficient deadlock avoidance policy (DAP) is a critical step in the design and operation of a flexible manufacturing system (FMS). However, even for a simple FMS, the computation of an optimal DAP is intractable. This work addresses the optimal deadlock control problem of FMSs. Based on their Petri net models, it introduces the concept of κ-resources and proves that an FMS containing no κ-resources has only two types of reachable states: safe ones and deadlocks. It then can obtain an optimal DAP with polynomial computational complexity for a broader class of FMSs, which was never seen before. At the same time, for these FMSs, new structurally simpler optimal Petri net controllers are proposed.