Deadlock Analysis and Avoidance for Automated Manufacturing Systems Based on Petri Nets With Forward-Conflict-Free Structures

While a deadlock control problem in complex resource allocation systems (RASs) has been extensively studied in the literature, the corresponding results that are applicable to assembly systems are quite limited, both, in terms of structural analysis of deadlocks and deadlock resolution. Taking Petri nets (PNs) as a modeling and analysis tool, this article focuses on the deadlock control problem for a forward-conflict free net (FCFN), which allows for batch assembly and multiple resource allocations. First, a new structural characterization of deadlocks in FCFN is proposed through two structural objects: 1) circuit and 2) <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\omega $ </tex-math></inline-formula>-structure. The starting point for this is motivated by the fact that deadlocks in assembly systems stem not only from the circular wait of resources but also the parts waiting for their assembly with other parts. Subsequently, based on these two objects, a necessary and sufficient condition about FCFNs liveness is obtained: 1) an FCFN is live if and only if no circuit and 2) <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\omega $ </tex-math></inline-formula>-structure are saturated at any reachable marking. Finally, in order to prevent each such object from inducing deadlocks, a hierarchical search algorithm appropriate for real-time implementation is developed to avoid its saturation. The proposed algorithm is proven to be capable of ensuring the deadlock-free operation of FCFNs. Moreover, several examples are provided to demonstrate its effectiveness.