¹School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China
²School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China

---

Abstract—In this paper, a fast method named algorithm 2 is proposed to extract all minimal siphons from maximal unmarked siphons obtained by the MIP-based deadlock detection method. Redundant computation is the major disadvantage of an existing method named algorithm 1 and it greatly decreases the computational efficiency of minimal siphons. In order to resolve this problem, the proposed method improves from three aspects. Firstly, no sink places and transitions exist in the subnet of the tree. Secondly, no equal non-null node exists in the tree. Thirdly, if the removal of one place from a subnet node leads to the removal of all places in this node, the same place of its son node is unnecessary to compute repeatedly. The applications of algorithm 2 are illustrated with FMS examples in the following sections and comparison of algorithm 1 with algorithm 2 is also presented. At the end, the result from experiment shows that the proposed method has higher efficiency.

Index Terms—deadlock,flexible manufacturing system (FMS), Petri net

[PDF]

Cite: Qiaoli Zhuang, Wenzhan Dai, "A Fast Method for Extracting all Minimal Siphons from Maximal Unmarked Siphons of a Petri Net," Journal of Software vol. 9, no. 3, pp. 582-588, 2014.