An extraction algorithm for a set of elementary siphons based on mixed-integer programming

doi:10.1007/s11518-012-5188-z

CORC > 兰州理工大学 > 兰州理工大学 > 土木工程学院

	An extraction algorithm for a set of elementary siphons based on mixed-integer programming
	Li, Shaoyong 1,2; Li, Zhiwu 1; Hu, Hesuan 1; Al-Ahmari, Abdulrahman 3; An, Aimin 2
刊名	Journal of Systems Science and Systems Engineering
	2012-03-01
卷号	21 期号:1 页码:106-125
关键词	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
ISSN号	10043756
DOI	10.1007/s11518-012-5188-z
英文摘要	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.
资助项目	"863" High-tech Research and Development Program of China[2008AA04Z109]
WOS研究方向	Operations Research & Management Science
语种	英语
出版者	Springer Verlag
WOS记录号	WOS:000302951400006
状态	已发表
内容类型	期刊论文
源URL	[http://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.