ABSTRACT
This chapter discusses, in three parts, Petri net(PN) siphon based approaches for detecting and preventing deadlocks in automated manufacturing systems. First, the chapter addresses the deadlock analysis of automated manufacturing systems modelled by PNs. It generalizes the well-known Commoner condition and exploits the notion of potential deadlocks, which are siphons that eventually become un marked. The chapter then presents a linear programming-based sufficient condi tion under which a siphon is not a potential deadlock. Using the new sufficient condition, a mathematical programming approach and a mixed-integer program ming approach are proposed for checking ordinary PNs and structurally bounded PNs, respectively, without explicitly generating siphons. In the second part of the chapter, stronger results are obtained for various PN models of a wide range of automated manufacturing systems. The classes of systems that we focus on are the classical net class, asymmetric-choice nets, as well as some recently proposed classes, including augmented marked graphs, S3PR, RCN merged nets, ERCN merged nets, and PNR. The third part of the chapter presents an iterative deadlock prevention approach for S3PR based on the above results.
