应用必需信标的Petri网死锁预防策略

A deadlock prevention policy in Petri nets using necessary siphons

本文提出了表征一个Petri网子类,即S4R网(system of sequential systems with shared resources)中死锁问题的必需信标的概念和一种将混合整数规划算法与必需信标控制相结合的死锁预防策略.在该策略的迭代过程中,混合整数规划算法发现被控的Petri网中是否存在最大的死标识信标,若存在,则通过库所分类和迭代式的信标提取,得到必需信标,添加相应的控制库所,满足必需信标的最大可控性,从而实现被控的Petri网活性的目的.理论分析和算例验证表明了该策略的正确性和有效性.

This paper puts forward the concept of necessary siphons that characterizes the deadlock problem in a subclass of Petri nets S4R（system of sequential systems with shared resources） and a deadlock prevention policy combining the mixed integer programming（MIP） and the control of necessary siphons. In the iteration of the proposed policy, the MIP- based deadlock-detection method explores whether a maximal deadly marked siphon exists in the controlled Petri net; if it is, this siphon is identified by the method of classification of places, and extracted as a necessary siphon to be controlled. A proper control place（CP） is applied to the necessary siphon to make it max-controlled, thus, ensuring the liveness of the controlled Petri nets. Theoretical analysis and an experimental example show the efficacy of the proposed policy.