An extraction algorithm for a set of elementary siphons based on mixed-integer programming | |
Li, Shaoyong1,2; Li, Zhiwu1; Hu, Hesuan1; Al-Ahmari, Abdulrahman3; An, Aimin2 | |
2012-03-01 | |
发表期刊 | Journal of Systems Science and Systems Engineering |
ISSN | 10043756 |
卷号 | 21期号:1页码:106-125 |
摘要 | 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. © 2012 Systems Engineering Society of China and Springer-Verlag Berlin Heidelberg. |
关键词 | Discrete event simulation Flexible manufacturing systems Iterative methods Petri nets Siphons Deadlock prevention Deadlock prevention policy Elementary siphon Extraction algorithms Its efficiencies Mixed integer programming Mixed integer programming (MIP) Sequential process |
DOI | 10.1007/s11518-012-5188-z |
收录类别 | EI ; SCIE |
语种 | 英语 |
资助项目 | "863" High-tech Research and Development Program of China[2008AA04Z109] |
WOS研究方向 | Operations Research & Management Science |
WOS类目 | Operations Research & Management Science |
WOS记录号 | WOS:000302951400006 |
出版者 | Springer Verlag |
EI入藏号 | 20121314897424 |
EI主题词 | Integer programming |
EI分类号 | 619.1 Pipe, Piping and Pipelines - 913.4.1 Flexible Manufacturing Systems - 921 Mathematics - 961 Systems Science |
来源库 | Compendex |
分类代码 | 619.1 Pipe, Piping and Pipelines - 913.4.1 Flexible Manufacturing Systems - 921 Mathematics |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | https://ir.lut.edu.cn/handle/2XXMBERH/111514 |
专题 | 土木工程学院 电气工程与信息工程学院 |
通讯作者 | Li, Shaoyong |
作者单位 | 1.Xidian Univ, Sch Electromech Engn, Xian 710071, Peoples R China; 2.Lanzhou Univ Technol, Sch Civil Engn, Lanzhou 730050, Peoples R China; 3.King Saud Univ, Coll Engn, Riyadh 11421, Saudi Arabia |
第一作者单位 | 兰州理工大学 |
通讯作者单位 | 兰州理工大学 |
推荐引用方式 GB/T 7714 | Li, Shaoyong,Li, Zhiwu,Hu, Hesuan,et al. An extraction algorithm for a set of elementary siphons based on mixed-integer programming[J]. Journal of Systems Science and Systems Engineering,2012,21(1):106-125. |
APA | Li, Shaoyong,Li, Zhiwu,Hu, Hesuan,Al-Ahmari, Abdulrahman,&An, Aimin.(2012).An extraction algorithm for a set of elementary siphons based on mixed-integer programming.Journal of Systems Science and Systems Engineering,21(1),106-125. |
MLA | Li, Shaoyong,et al."An extraction algorithm for a set of elementary siphons based on mixed-integer programming".Journal of Systems Science and Systems Engineering 21.1(2012):106-125. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论