In: IEEE Trans. on Systems, Man, and Cybernetics; B: Cybernetics, Vol. 30, No. 5, pages 783-798. 2000.
Abstract: Flexible manufacturing systems (FMSs) are modern production facilities with easy adaptability to variable production plans and goals. These systems may exhibit deadlock situation occurring when a circular wait arises because each piece in a set requires a resource currently held by another job in the same set. Several authors have proposed different policies to control resource allocation in order to avoid deadlock problems. These approaches are mainly based on some formal models of manufacturing systems, such as Petri nets (PNs), directed graphs, etc. Since they describe various pecularities of the FMS operation in a modular and systematic way, PNs are the most extensively used tool to model such systems. On the other hand, digraphs are more synthetic than PNs because their vertices are just the system resources. So, digraphs describe the interactions between jobs and resources only, while neglecting other details of the system operation. The aim of this paper is to show the tight connection between the two approaches to the deadlock problem be proposing a unitary framework that links graph-theoretic and PN models and results. In this context, a direct correspondence between the structural elements of the PN (empty siphons) and those of the digraphs (maximal-weight-zero-outdegree strong components) characterizing a deadlock occurrence. The paper also shows that the avoidance policies derived from digraphs can be implemented by controlled PNs.
Keywords: Petri nets, deadlock avoidance, flexible manufacturing systems.