Flexible manufacturing systems (FMSs) are modern production facilities with
easy adaptability to variable production plans and goals. These systems ma
y exhibit deadlock situations occurring when a circular wait arises because
each piece in a set requires a resource currently held by another job in t
he same set. Several authors have proposed different policies to control re
source 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 peculiaritie
s of the FMS operation in a modular and systematic way, PNs are the most ex
tensively used tool to model such systems. On the other hand, digraphs are
more synthetic than PNs because their vertices are just the system resource
s. So, digraphs describe the interactions between jobs and resources only,
while neglecting other details on the system operation.
The aim of this paper is to show the tight connections between the two appr
oaches to the deadlock problem, by proposing a unitary framework that links
graph-theoretic and PN models and results, In this context, we establish a
direct correspondence between the structural elements of the PN (empty sip
hons) and those of the digraphs (maximal-weight zero-outdegree strong compo
nents) characterizing a deadlock occurrence. The paper also shows that the
avoidance policies derived from digraphs can be implemented by controlled P
Ns.