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

摘要

This paper studies the siphon computation problem for S4PR(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 S4PR nets.There exist redundant siphons in the set of siphons obtained by current siphon computation algorithms and supervisors added for these siphons will reduce the behavior permissiveness of the controlled systems.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 supervisors.Application examples are given to illustrate its feasibility and efficiency in deadlock prevention policies.%研究了S4PR(systems of sequential systems with shared resources)网的虹吸寻找问题.S4PR网是一类典型的用于建模顺序资源共享分配系统的Petri网模型.在S4PR网中,虹吸的不充分标识会导致死锁.现有的虹吸寻找算法得到的虹吸集合中,存在着不需要进行控制的冗余虹吸,对其添加控制器将会导致控制的冗余和受控系统行为允许度的降低.提出了一种基于混合整数规划(MIP)的虹吸寻找方法,并证明了当该方法没有合适的解时,网系统是活的.与现有的其他算法相比,这一方法能直接获取一个极小的虹吸,并剔除一些并不需要控制的虹吸,因此能用于设计更高允许度的虹吸控制器.应用实例说明了其用于死锁预防策略的可行性和有效性.