Elementary siphons are useful in the development of a deadlock prevention policy for a discrete event system modeled with Petri nets. This paper proposes an algorithm to iteratively extract a set of elementary siphons in a class of Petri nets, called system of simple sequential processes with resources (S3PR). At each iteration, by a mixed-integer programming (MIP) method, the proposed algorithm finds a maximal unmarked siphon, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. This algorithm iteratively executes until no new unmarked siphons can be found. It finally obtains a unique set of elementary siphons and avoids a complete siphon enumeration. A theoretical analysis and examples are given to demonstrate its efficiency and practical potentials.
%0 Journal Article
%1 LiLiHuAiAn12
%A Li, Shaoyong
%A Li, Zhiwu
%A Hu, Hesuan
%A Al-Ahmari, Abdulrahman
%A An, Aimin
%D 2012
%I Systems Engineering Society of China, co-published with Springer-Verlag GmbH
%J Journal of Systems Science and Systems Engineering
%K calculo, cerrojos, citas, citeulike computation, elementary, extraction, referencias, siphons
%N 1
%P 106--125
%R 10.1007/s11518-012-5188-z
%T An extraction algorithm for a set of elementary siphons based on mixed-integer programming
%U http://dx.doi.org/10.1007/s11518-012-5188-z
%V 21
%X Elementary siphons are useful in the development of a deadlock prevention policy for a discrete event system modeled with Petri nets. This paper proposes an algorithm to iteratively extract a set of elementary siphons in a class of Petri nets, called system of simple sequential processes with resources (S3PR). At each iteration, by a mixed-integer programming (MIP) method, the proposed algorithm finds a maximal unmarked siphon, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. This algorithm iteratively executes until no new unmarked siphons can be found. It finally obtains a unique set of elementary siphons and avoids a complete siphon enumeration. A theoretical analysis and examples are given to demonstrate its efficiency and practical potentials.
@article{LiLiHuAiAn12,
abstract = {{Elementary siphons are useful in the development of a deadlock prevention policy for a discrete event system modeled with Petri nets. This paper proposes an algorithm to iteratively extract a set of elementary siphons in a class of Petri nets, called system of simple sequential processes with resources (S3PR). At each iteration, by a mixed-integer programming (MIP) method, the proposed algorithm finds a maximal unmarked siphon, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. This algorithm iteratively executes until no new unmarked siphons can be found. It finally obtains a unique set of elementary siphons and avoids a complete siphon enumeration. A theoretical analysis and examples are given to demonstrate its efficiency and practical potentials.}},
added-at = {2017-09-08T10:52:59.000+0200},
author = {Li, Shaoyong and Li, Zhiwu and Hu, Hesuan and Al-Ahmari, Abdulrahman and An, Aimin},
biburl = {https://www.bibsonomy.org/bibtex/21667a84b9ec7312682aafcaf9c69327a/fernand0},
citeulike-article-id = {10481569},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/s11518-012-5188-z},
citeulike-linkout-1 = {http://www.springerlink.com/content/d46570k66197x5r8},
day = 1,
doi = {10.1007/s11518-012-5188-z},
interhash = {b554f2840431153d78294fa73577f04a},
intrahash = {1667a84b9ec7312682aafcaf9c69327a},
issn = {1004-3756},
journal = {Journal of Systems Science and Systems Engineering},
keywords = {calculo, cerrojos, citas, citeulike computation, elementary, extraction, referencias, siphons},
month = mar,
number = 1,
pages = {106--125},
posted-at = {2012-05-10 09:14:30},
priority = {2},
publisher = {Systems Engineering Society of China, co-published with Springer-Verlag GmbH},
timestamp = {2017-09-08T10:53:23.000+0200},
title = {{An extraction algorithm for a set of elementary siphons based on mixed-integer programming}},
url = {http://dx.doi.org/10.1007/s11518-012-5188-z},
volume = 21,
year = 2012
}