Although deadlock avoidance issue has attracted much attention and has been extensively studied, most of the existing results assume reliable machines. This assumption makes it difficult to apply existing deadlock avoidance algorithms to real manufacturing systems with unreliable machines. This paper presents the results to apply an existing deadlock avoidance algorithm to systems with unreliable machines by analyzing the robustness of the deadlock avoidance algorithm. Sequential production processes are considered in this paper, and Petri Net is adopted as the tool for modeling and analysis of the sequential processes. Different types of tolerable machine failures under which liveness property can be preserved are characterized. Computational complexity of the proposed algorithm is analyzed.
Deadlock is a highly undesirable situation in which a set of parts or jobs are requesting or waiting for resources held by other parts or jobs in the same set, with the set of parts or jobs in circular waiting. In the context of manufacturing systems, deadlock issue has attracted much attention in the last decade (Lawley & Sulistyono, 2002; Hsieh, 2000; Wu, 1999; Reveliotis, 1999; Lawley, 1998; Lawley, Spyros, Reveliotis, & Placid, 1998; Reveliotis, Lawley, & Ferreira, 1997; Cho, Kumaran, & Wysk, 1995; Ezpeleta, Colom, & Martinez, 1995; Hsieh & Chang, 1994; Wysk, Yang, & Joshi, 1991; Banaszak & Krogh, 1990; Viswanadham, Narahari, & Johnson, 1990). Banaszak and Krogh (1990) proposed a production Petri net (PPN) model and developed a simple and low computational complexity deadlock avoidance restriction policy. Hsieh (Hsieh & Chang, 1994) overcame the drawbacks of the above approach by formulating a deadlock avoidance controller (DAC) synthesis problem for a class of Petri net called CPPN. Ezpeleta et al. (1995) formulated a policy that prevents deadlocks by establishing the equivalence between deadlocks and unmarked siphons in a class of Petri net called S3PR. Wysk et al. (1991) and Cho et al. (1995) proposed graph-theoretic models for deadlock detection and avoidance of manufacturing systems.
Uncertainties such as machine failure poses challenges in control of manufacturing systems as resource failures may reduce the number of available resources which may in turn result in deadlocks or lead to dead states. As existing papers assume reliable machines in development of deadlock avoidance algorithms, there is a gap between the development of theory and application to real manufacturing systems. The main results of this paper show that the existing deadlock avoidance control (DAC) algorithm possesses desirable robustness properties capable of dealing with unreliable machines. The concept of critical path is proposed to quantitatively characterize the safety margins with which the system can still be kept live using the remaining resources available. The results of this paper show that it is possible to tailor existing deadlock avoidance algorithms to be applicable to systems with unreliable machines.
