Deadlock analysis of Petri nets using siphons and mathematical programming

摘要

This paper exploits the potential of siphons for the analysis of Petri nets, It generalizes the well-known Commoner condition and is based on the notion of potential deadlocks which are siphons that eventually become empty. A linear programming based sufficient condition under which a siphon is not a potential deadlock is obtained. Based on the new sufficient condition, a mathematical programming approach and a mixed-integer programming approach are proposed for checking general Petri nets and structurally bounded Petri nets respectively without explicitly generating siphons. Stronger results are obtained for asymmetric choice nets and augmented marked graphs. In particular, we show that an asymmetric choice net is live iff it is potential-deadlock-free and an augmented marked graph is live and reversible iff it is potential-deadlock-free.