doi: 10.4304/jsw.9.3.582-588
A Fast Method for Extracting all Minimal Siphons from Maximal Unmarked Siphons of a Petri Net
- 1 School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China
- 2 School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China
Abstract
In this paper, a fast method named algorithm 2is proposed to extract all minimal siphons from maximalunmarked siphons obtained by the MIP-based deadlockdetection method. Redundant computation is the majordisadvantage of an existing method named algorithm 1 andit greatly decreases the computational efficiency of minimalsiphons. In order to resolve this problem, the proposedmethod improves from three aspects. Firstly, no sink placesand transitions exist in the subnet of the tree. Secondly,no equal non-null node exists in the tree. Thirdly, if theremoval of one place from a subnet node leads to theremoval of all places in this node, the same place of its sonnode is unnecessary to compute repeatedly. The applicationsof algorithm 2 are illustrated with FMS examples in thefollowing sections and comparison of algorithm 1 withalgorithm 2 is also presented. At the end, the result fromexperiment shows that the proposed method has higherefficiency.
Keywords
- deadlock
- flexible manufacturing system (
How to Cite
Qiaoli Zhuang and 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. https://doi.org/ 10.4304/jsw.9.3.582-588
Copyright & License
Copyright © 2014 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).