基于混合整数规划的一般Petri网死锁检测方法

Deadlock detection method using mixed integer programming for generalized Petri nets

信标的受控性是检测柔性制造系统(flexible manufacturing system,FMS)Petri网模型是否存在死锁的关键因素.对于普通Petri网,在任何可达标识下所有信标不被清空是检测网系统非死锁的充分条件.然而,该条件对于建模能力更强的一般Petri网并不适用,max可控性条件由此产生.研究证明,该条件对于一般Petri网的死锁检测过于严格了.虽然其后有很多研究者通过改进max可控性条件以求给出条件更宽松的一般Petri网非死锁的充分条件,但大部分的研究成果都仅仅局限于一种顺序资源共享分配系统Petri网模型S4PR(systems of sequential systems with shared resources)网.因此,本文在max可控性条件的基础上提出了新的名为max#可控的信标可控性条件,并在此条件的基础上实现了基于混合整数规划(mixed integer programming,MIP)的死锁检测方法.与现有研究成果相比,max#可控性条件更宽松,可适用于更多类型的一般网,为解决大规模柔性制造系统中死锁监督控制器的结构复杂性问题提供了有力的理论支撑.

The controllability of siphon is the key factor in detecting deadlocks which occur in the flexible manufacturing system based on Petri nets. The sufficient condition for deadlock-free detection of ordinary petri nets is that all siphons are not emptied. However, this Condition can not be applied to general ones. Therefore, a condition named max-controlled for deadlock detection of generalized petri nets is proposed. In recent years, some conditions have been developed to try to obtain the general sufficient one because the max-controlled condition has been proved to be overly restrictive, but most of them are only applicable for SapR （systems of sequential systems with shared resources） net. In this paper, a new condition named max#-controlled is introduced and the deadlock detection method based on MIP （mixed integer programming） is presented. Compared with previous conditions, the new one is more general to generalized petri nets and it can be a theoretical support for dealing with the structural complexity problems of liveness- enforcing supervisor in large scale of flexible manufacturing systems.