基于MIP的顺序资源共享分配系统的虹吸寻找方法  

MIP-based siphon computation for systems of sequential systems with shared resources

作　　者：董利达[1,2] 傅健丰[2] 朱丹[2] 朱承丞[2] 

机构地区：[1]杭州师范大学杭州国际服务工程学院,浙江杭州310012 [2]浙江大学电子电路与信息系统研究所,浙江杭州310027

出　　处：《浙江大学学报（理学版）》2013年第4期416-423,共8页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(No.61071062);浙江省自然科学基金资助项目(No.Y12F02030)

摘　　要：研究了S4PR(systems of sequential systems with shared resources)网的虹吸寻找问题.S4PR网是一类典型的用于建模顺序资源共享分配系统的Petri网模型.在S4PR网中,虹吸的不充分标识会导致死锁.现有的虹吸寻找算法得到的虹吸集合中,存在着不需要进行控制的冗余虹吸,对其添加控制器将会导致控制的冗余和受控系统行为允许度的降低.提出了一种基于混合整数规划(MIP)的虹吸寻找方法,并证明了当该方法没有合适的解时,网系统是活的.与现有的其他算法相比,这一方法能直接获取一个极小的虹吸,并剔除一些并不需要控制的虹吸,因此能用于设计更高允许度的虹吸控制器.应用实例说明了其用于死锁预防策略的可行性和有效性.This paper studies the siphon computation problem for S4 PR（systems of sequential systems with shared resources） nets, a typical class of Petri net model of flexible manufacturing systems. Insufficiently marked siphons lead to deadlocks in S4 PR nets. There exist redundant siphons in the set of siphons obtained by current siphon com- putation algorithms and supervisors added for these siphons will reduce the behavior permissiveness of the controlled sys- tems. This paper presents a new siphon computation method based on mixed integer programming （MIP） and proves that an S4 PR net is live if this method has no feasible solution. Compared with other algorithms, this one can directly obtain a minimal siphon and eliminate some redundant siphons. Hence it can be used to design more permissively controlled supervi- sors. Application examples are given to illustrate its feasibility and efficiency in deadlock prevention policies.

关 键 词：PETRI网 虹吸寻找 S4PR网 活性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]