东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

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

ISSN号：1004-3756
期刊名称：《系统科学与系统工程学报：英文版》
时间：0
分类：O221.4[理学—运筹学与控制论;理学—数学] TP311.13[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
作者机构：[1]School of Electro-Mechamcal Engmeermg, Xidian University, Xi＇ an 710071, P. R. China, [2]School of Ctvil Engmeertng, Lanzhou University of Technology, Lanzhou 730050, P. R. China, [3]College of Engineering, King Saud University, Riyadh 11421, Saudi Arabia
相关基金：This work is 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. JY10000904001; the National Research Foundation for the Doctoral Program of Higher Education, the Ministry of Education, ER. China, under Grant No. 20090203110009; the ＂863＂ High-tech Research and Development Program of China under Grant No. 2008AA04Z109; and the Alexander von Humboldt Foundation.

作者： Shaoyong LI[1,2], Zhiwu LI[1], Hesuan HU[1], Abdulrahman AI-AHMARI[3], Aimin AN[2]

关键词：混合整数规划, 提取算法, 离散事件系统, PETRI网, 信标, 虹吸管, 预防策略, 小学, Petri net, flexible manufacturing system, deadlock prevention, mixed integer programming, elementary siphon

中文摘要：

基本虹吸在为与 Petri 网建模的一个分离事件系统的一条僵局预防政策的发展是有用的。这篇论文建议一个算法反复地在 Petri 网络的一个类上提取一套基本虹吸，有资源(S3PR ) 的简单顺序的进程的叫的系统。在每次重复，由混合整数编程(MIP ) 方法，建议算法发现最大的未做记号的虹吸，在它分类这些地方，从分类地方提取基本虹吸，并且增加新限制以便提取下一基本虹吸。这个算法反复地执行直到没有新未做记号的虹吸能被发现。它最后获得基本虹吸的一个唯一的集合并且避免完全的虹吸枚举。理论分析和例子被给表明它的效率和实际潜力。

英文摘要：

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.

同期刊论文项目