%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 }