ABSTRACT
This chapter focuses on deadlock avoidance strategy specifications based on the graph theory approaches. In a pioneer contribution, Wysk et al. introduces a digraph representation of the jobs/resources interactions. The chapter presents an algorithm for deadlock detection used in conjunction with resolution procedures. It establishes notations and recalls the two basic digraphs describing the resource allocation system. The chapter also recalls some particular figures of the transition digraph (TD) to state a necessary and sufficient condition for a deadlock occurrence. It analyses the conditions for the second level deadlock (SLD) occurrences. The chapter proposes a digraph framework to characterize deadlock conditions of the manufacturing systems exhibiting multiple capacity resources. It employs the working procedure digraph (WPD) for representing all the possible interactions between jobs and resources and the TD to consider only their current relations occupations and requests.
