AN EXTRACTION ALGORITHM FOR A SET OF ELEMENTARY SIPHONS BASED ON MIXED-INTEGER PROGRAMMING

作     者：Shaoyong LI Zhiwu LI Hesuan HU Abdulrahman AI-AHMARI Aimin AN 

作者机构：School of Electro-Mechamcal Engmeermg Xidian University Xi＇ an 710071 P. R. China School of Ctvil Engmeertng Lanzhou University of Technology Lanzhou 730050 P. R. China College of Engineering King Saud University Riyadh 11421 Saudi Arabia 

出 版 物：《Journal of Systems Science and Systems Engineering》 (系统科学与系统工程学报（英文版）)

年 卷 期：2012年第21卷第1期

页      面：106-125页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：supported by the Natural Science Foundation of China under Grant No.60773001,61074035, 61064003,and 50978129 the Fundamental Research Funds for the Central Universities under Grant No. JY 10000904001 the National Research Foundation for the Doctoral Program of Higher Education,the Ministry of Education,P.R.China,under Grant No.20090203110009 the"863"High-tech Research and Development Program of China under Grant No.2008AA04Z 109 the Alexander von Humboldt Foundation 

主　　题：Petri net flexible manufacturing system deadlock prevention mixed integer programming elementary siphon 

摘      要：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.