S^4PR网的极小信标计算方法

Method to compute minimal siphons in S^4PR nets

为了解决S4PR网的信标求解问题,提出了一种计算网中全部极小信标的方法.该方法通过分析资源库所内工作环与资源库所集合之间的关系构建有向图(C-R图),获取强连通的C-R子图集合,而每个C-R子图对应着一个信标,由此得到包含2个及2个以上资源库所的信标集合,将该集合与含有单个资源库所的极小信标集合进行并集运算,形成备选信标集合,通过算法对备选集合进行筛选,删除其中非极小的信标,进而得到网中全部的极小信标.该方法为获取S4PR网中全部的极小信标提供了有效、可行的方案,为下一步设计最优活性控制器奠定了基础.一个可用S4PR网建模的柔性制造系统实例验证了该极小信标计算方法的正确性.

This work proposed a method to find all the minimal siphons for an S4PR net.The method builds up a directed graph based on the relationship among resource places and their inner-working circuits（referred to as C-R graph）.It can be used to calculate the strongly connected subgraphs with each of them corresponding to one siphon.Based on these,the siphons having multiple resource places are computed.These siphons are combined with the ones having the single resource place to construct the siphon candidate set.An algorithm was used to do filtering to these siphon candidates and the non-minimal siphons were removed to achieve the set of minimal siphons in the S4PR net.This method provides an effective solution for calculating all the minimal siphons in S4PR nets,and builds a foundation for designing optimal liveness-enforcing supervisor.This method was verified by a flexible manufacturing system（FMS） example which could be modeled by an S4PR net.