Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems
Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems
复制标题
DOI：
10.1109/tsmca.2003.820576
复制
发表时间：
2004-01
期刊：
影响因子：
--
通讯作者：
Zhiwu Li;Mengchu Zhou
中科院分区：
文献类型：
--
作者：
Zhiwu Li;Mengchu Zhou
在柔性制造系统（FMS）中防止死锁产生的各种重要的基于Petri网的方法是在严格的最小虹吸管（SMS）上增加一些控制位置和相关弧线，使虹吸管不能被清空。由于最小虹吸管的数量通常与Petri网的大小呈指数增长，它们的缺点在于它们经常在网络中添加太多额外的位置，从而使最终的网络模型比原始的网络模型复杂得多。本文探讨了在达到相同控制目的的同时最小化新增场所的方法。首次提出了基本虹吸管的概念，它是一类特殊的虹吸管。Petri网中的基本虹吸管集通常是所有SMS集的适当子集。其较小的基数在大型Petri网模型中变得明显。证明了通过在每个基本虹吸管上增加一个控制位置来确保其被标记，可以成功地防止死锁的发生。与现有方法相比，新方法所需的控制场所数量少得多，因此适用于大规模Petri网。最后以FMS为例说明了所提出的概念和策略，并展示了该方法相对于以往方法的显著优势。
A variety of important Petri net-based methods to prevent deadlocks arising in flexible manufacturing systems (FMS) are to add some control places and related arcs to strict minimal siphons (SMS) such that no siphon can be emptied. Since the number of minimal siphons grows in general exponentially with respect to a Petri net size, their disadvantages lie in that they often add too many additional places to the net, thereby making the resulting net model much more complex than the original one. This paper explores ways to minimize the new additions of places while achieving the same control purpose. It proposes for the first time the concept of elementary siphons that are a special class of siphons. The set of elementary siphons in a Petri net is generally a proper subset of the set of all SMS. Its smaller cardinality becomes evident in large Petri net models. This paper proves that by adding a control place for each elementary siphon to make sure that it is marked, deadlock can be successfully prevented. Compared with the existing methods, the new method requires a much smaller number of control places and, therefore, is suitable for large-scale Petri nets. An FMS example is used to illustrate the proposed concepts and policy, and show the significant advantage over the previous methods.