Avoiding unsafe states in manufacturing systems based on polynomial digraph algorithms

A deadlock-free unsafe (DFU) state of Resource Allocation System (RAS) is deadlock-free but inevitable to enter a deadlock state. Previous research revealed that in many special systems, DFU states do not exist and polynomial deadlock avoidance policy (DAP) using one-step look ahead algorithms can avoid deadlock states. This paper first establishes the NP-completeness on determining the existence of DFU states. Then, giving necessary conditions of DFU states based on digraph analysis, it provides polynomial avoidance policies that inhibit loading new jobs to avoid DFU states. Furthermore, this method is generalized to mixed capacity systems and systems with flexible routings. Examples and simulation results are also presented.