Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems

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.     

基于Petri网的柔性制造系统一种预防死锁方法

基于Petri网的结构特性分析,研究了FMS(柔性制造系统)一种预防死锁方法.提出了Petri网的一种特殊拓扑结构--基本信标的概念.在Petri网中基本信标的集合是SMS(严格极小信标)集合的一个真子集.尤其在大型Petri网系统中,基本信标的集合比SMS的集合要小得多.对于Petri网的一个子类S3PR,只对每一个基本信标添加一个库所使其不被清空,就可实现预防死锁,也就是说无须控制S3PR的所有SMS而达到无信标被清空的目的.此外,对于S3PR,还提出了一种求取SMS和基本信标的方法.相对于现在普遍采用的控制所有SMS来预防死锁的策略,其具三方面优势.1)只需控制少量的SMS即所谓的基本信标.相应地,添加少量的控制库所和连接弧,就可得到无死锁或活的Petri网.2)不需要先行计算出极小信标的集合.3)明显地,这种方法更适合大型Petri网系统.我们通过穿插在文中的一个例子来说明这些方法.     

Extended Elementary Siphons and Their Application to Liveness‐Enforcement of Generalized Petri Nets

As a significant structural object, siphons are extensively employed to implement a large number of deadlock prevention and liveness‐enforcing methods for flexible manufacturing systems modeled by Petri nets. By linear combinations, a set of elementary siphons is chosen from all strict minimal ones to be controlled and thus the structural complexity of a supervisor is greatly reduced. The concept of elementary siphons is originally proposed for ordinary Petri nets. When applied to generalized Petri nets, their selection and controllability require an additional study. In this work, the concept of augmented siphons is proposed to extend the application of the elementary ones to a class of generalized Petri nets, GLS³PR. Based on graph theory, a siphon extraction algorithm is developed to obtain all strict minimal siphons, from which augmented elementary ones are computed. In addition, the controllability conditions of dependent siphons are developed. Through fully investigating the net structure, especially weight information, the set of augmented elementary siphons is more compact and well suits for generalized Petri net models under consideration. Some examples are used to illustrate the proposed method.     

信标基底的可选择性在制造系统死锁控制中的应用

本文基于Petri网模型,讨论柔性制造系统的死锁控制问题.为了建立结构简单的Petri网控制器,本文在以前的工作中提出了信标基底的概念.信标基底是一组满足特定条件的严格极小信标集合.本文证明基于不同的信标基底,建立的受控系统其容许性能也不同.而容许性是评价死锁控制策略优劣的重要标准之一.故如何选择信标基底,提高受控系统的容许性能是值得研究的问题.本文讨论了使受控系统容许性能大大提高的信标基底的选择条件.基于该条件,为柔性制造系统建立有效的死锁控制策略.最后,通过两个例子解释该条件和策略.     

自动制造系统Petri网的公平活性控制策略

基于Petri网的不变式理论,针对典型的自动制造系统,提出了Petri模型强制公平性和活性的方法.首先,基于网论T-不变式的概念,把系统的网模型设计为一个公平网.此后,利用P-不变式把一个公平网设计为一个活的且公平网.同时,提出了非冗余严格极小信标的概念,大大简化了系统的分析与设计.一般说来,非冗余严格极小信标是系统严格极小信标一个小的子集,尤其对于复杂系统的网模型.研究结果表明,只要使非冗余的严格极小信标受控,则系统所有的严格极小信标就不会被清空.文中举例说明了这些控制方法的应用.研究结果适用于一大类柔性制造系统,具有相当的普遍性.这种方法对于自动制造系统的调度设计也具有一定意义和价值.     

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

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

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming

In this article we deal with deadlock prevention problems for S⁴PR, a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems where deadlocks are caused by insufficiently marked siphons. We present a deadlock prevention methodology that is an iterative approach consisting of two stages. The first one is called siphon control, which is to add for each insufficiently marked minimal siphon a control place to the original net. Its objective is to prevent a minimal siphon from being insufficiently marked. The second one, called control-induced siphon control, is to add a control place to the augmented net with its output arcs connecting to the source transitions, which assures that there are no new insufficiently marked siphons generated. At each iteration, a mixed integer programming approach is adopted for generalised Petri nets to obtain an insufficiently marked minimal siphon from the maximal deadly siphon. This way complete siphon enumeration is avoided that is much more time-consuming for a sizeable plant model than the proposed method. The relation of the proposed method and the liveness and reversibility of the controlled net is obtained. Examples are presented to demonstrate the presented method.     

An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming

This paper presents a novel and computational deadlock prevention policy for a class of generalized Petri nets, namely G-systems, which allows multiple resource acquisitions and flexible routings with machining, assembly and disassembly operations. In this research, a mixed integer programming (MIP)-based deadlock detection technique is used to find an insufficiently marked minimal siphon from a maximal deadly marked siphon for generalized Petri nets. In addition, two-stage control method is employed for deadlock prevention in Petri net model. Such proposed method is an iterative approach consisting of two stages. The first one is called siphons control, which adds a control place to the original net for each insufficiently marked minimal siphon. The objective is to prevent minimal siphons from being insufficiently marked. The second one, called control-induced siphons control, is to add a control place to the augmented net with its output arcs connecting to source transitions, which assures that there is no new insufficiently marked siphon generated due to the addition of the monitors. Compared with the existing approaches, the proposed deadlock prevention policy can usually lead to a non-blocking supervisor with more permissive behavior and high computational efficiency for a sizeable plant model due to avoiding complete siphon enumeration. Finally, a practical flexible manufacturing system (FMS) example is utilized to illustrate the proposed method.     

A deadlock prevention approach for a class of timed Petri nets using elementary siphons

To solve the problem of deadlock prevention for timed Petri nets, an effective deadlock prevention policy based on elementary siphons is proposed in this paper. Without enumerating reachable markings, deadlock prevention is achieved by adding monitors for elementary siphons, increasing control depth variables when necessary, and removing implicit, liveness‐restricted and redundant control places. The final supervisor is live. First, a timed Petri net is stretched into a stretched Petri net (SPN). Unchanging the system performance, each transition in the SPN has a unit delay time. Then the siphon‐control‐based approach is applied. Monitors computed according to the marking constraints are added to the SPN model to ensure all strict minimal siphons in the net invariant‐controlled. A liveness‐enforcing supervisor with simple structure can be obtained by reverting the SPN into a TdPN. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Necessary and sufficient liveness condition of GS3PR Petri nets

Structural analysis is one of the most important and efficient methods to investigate the behaviour of Petri nets. Liveness is a significant behavioural property of Petri nets. Siphons, as structural objects of a Petri net, are closely related to its liveness. Many deadlock control policies for flexible manufacturing systems (FMS) modelled by Petri nets are implemented via siphon control. Most of the existing methods design liveness-enforcing supervisors by adding control places for siphons based on their controllability conditions. To compute a liveness-enforcing supervisor with as much as permissive behaviour, it is both theoretically and practically significant to find an exact controllability condition for siphons. However, the existing conditions, max, max′, and max″-controllability of siphons are all overly restrictive and generally sufficient only. This paper develops a new condition called max*-controllability of the siphons in generalised systems of simple sequential processes with resources (GS³PR), which are a net subclass that can model many real-world automated manufacturing systems. We show that a GS³PR is live if all its strict minimal siphons (SMS) are max*-controlled. Compared with the existing conditions, i.e., max-, max′-, and max″-controllability of siphons, max*-controllability of the SMS is not only sufficient but also necessary. An example is used to illustrate the proposed method.     

基于信标的柔性制造系统的优化死锁预防策略

针对柔性制造系统（FMS）中的死锁问题,根据矩阵理论给出了Petri网中基本信标的概念,进而提出一种基于基本信标和混合整数规划法（MIP）的死锁预防策略．该策略将最优基本信标作为控制对象,以混合整数规划法给出的系统无死锁条件为目标函数．不考虑从属信标受控条件便可在多项式时间内使系统受控．该控制策略的显著特点是以较低的计算复杂度实现整个系统受控,并使需要添加的控制库所和连接弧大大减少．控制实例证明了其有效性．     

On Siphon Computation for Deadlock Control in a Class of Petri Nets

As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.     

A deadlock prevention approach for flexible manufacturing systems without complete siphon enumeration of their Petri net models

Siphons are very important in the analysis and control of deadlocks in a Petri net. However, it is quite time-consuming or even impossible to get the complete siphon enumeration of a Petri net. This paper focuses on the deadlock prevention problems in flexible manufacturing systems that are modeled with S⁴PR, a general class of Petri nets. The analysis of S⁴PR leads us to characterize deadlock situations in terms of insufficiently marked siphons. The method proposed in this paper is an iterative approach. At each iteration, a non-max-marked siphon is computed by solving a mixed integer linear programming problem. Then the siphon is max-marked through a P-invariant by adding a monitor place. This process is carried out until no non-max-marked siphon can be found in the net. As a result all the siphons in the net are max-controlled. Then the net becomes live. Without computing all the siphons, a monitor-based liveness-enforcing Petri net supervisor can be found with more permissive behavior. A number of flexible manufacturing examples are used to demonstrate the proposed methods.     

On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets

A fair amount of research has shown the importance of siphons in the analysis and control of deadlocks in a variety of resource allocation systems by using a Petri net formalism. In this paper, siphons in a generalized Petri net are classified into elementary and dependent ones, as done for ordinary nets in our previous work. Conditions are derived under which a dependent siphon is controlled by properly supervising its elementary siphons, which indicates that the controllability of dependent siphons in an ordinary Petri net is a special case of that in a generalized one. The application of the controllability of dependent siphons is shown by considering the deadlock prevention problem for a class of resource allocation systems, namely, G-system that allows multiple resource acquisitions and flexible routings in a flexible manufacturing system with machining, assembly, and disassembly operations. We develop a monitor-based deadlock prevention policy that first adds monitors for elementary siphons only to a G-system plant model such that the resultant net system satisfies the maximal controlled-siphon property (maximal cs-property). Then, by linear programming, initial tokens in the additional monitors are decided such that liveness is enforced to the supervised system. Also, a simplified live marking relationship for a G-system between the initial tokens of the source places and those of the resource places is derived. Finally, the proposed deadlock prevention methods are illustrated by using an example.     

Petri网极小虹吸的计算方法与性能分析

虹吸是Petri网的一种重要结构,可以用来分析所模拟系统的许多重要特性,如可达性、可逆性和活性等.文中首先提出了虹吸子网的概念,并给出了将Petri网划分成虹吸子网的多项式算法,进而给出其性能分析.通过求解虹吸子网的极小虹吸得到原Petri网的所有极小虹吸.而对于每个虹吸子网,首先求解它的一个极小虹吸,并根据此极小虹吸对子网进行分解,将分解得到的子网做类似原网的处理过程,直到每个子网的位置集就是一个极小虹吸或不包含任何极小虹吸为止.性能分析及实验表明,所构造的求解Petri网所有极小虹吸的算法是一个有效的算法.     

Extension of the lower bound of monitor solutions of maximally permissive supervisors to non-α net systems

Traditional region-based liveness-enforcing supervisors focus on (1) maximal permissiveness of not losing legal states, (2) structural simplicity of minimal number of monitors, and (3) fast computation. Lately, a number of similar approaches can achieve minimal configuration using efficient linear programming. However, it is unclear as to the relationship between the minimal configuration and the net structure. It is important to explore the structures involved for the fewest monitors required. Once the lower bound is achieved, further iteration to merge (or reduce the number of) monitors is not necessary. The minimal strongly connected resource subnet (i.e., all places are resources) that contains the set of resource places in a basic siphon is an elementary circuit. Earlier, we showed that the number of monitors required for liveness-enforcing and maximal permissiveness equals that of basic siphons for a subclass of Petri nets modelling manufacturing, called α systems. This paper extends this to systems more powerful than the α one so that the number of monitors in a minimal configuration remains to be lower bounded by that of basic siphons. This paper develops the theory behind and shows examples.     

Enumeration algorithms for minimal siphons in Petri nets based on place constraints

The paper addresses the problem of enumerating minimal siphons in an ordinary Petri net. The algorithms developed in this work recursively use a problem partitioning procedure to reduce the original search problem to multiple simpler search subproblems. Each subproblem has specific additional place constraints with respect to the original problem. Some results on algorithm correctness, convergence, and computational complexity are provided, as well as an experimental evaluation of performance. The algorithms can be applied to enumerate minimal, place-minimal siphons, or even siphons that are minimal with respect to given subsets of places.     

Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming

This article develops a deadlock prevention policy for a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems. The analysis of such a system leads us to characterise the deadlock situations in terms of the insufficiently marked siphons in its generalised Petri-net model. The proposed policy is carried out in an iterative way. At each step a minimal siphon is derived from a maximal deadly marked siphon that is found by solving a mixed integer programming (MIP) problem. An algorithm is formalised that can efficiently compute such a minimal siphon from a maximal one. A monitor is added for a derived minimal siphon such that it is max-controlled if it is elementary with respect to the siphons that have been derived. The liveness of the controlled system is decided by the fact that no siphon can be derived due to the MIP solution. After a liveness-enforcing net supervisor computed without complete siphon enumeration, the output-arcs of the additional monitors are rearranged such that the monitors act while restricting the system less. Examples are presented to demonstrate the proposed method.     

Control of Elementary and Dependent Siphons in Petri Nets and Their Application

The importance of siphons is well recognized in the analysis and control of deadlocks in a Petri net. To minimize the number of siphons that have to be explicitly controlled, siphons in a net are divided in a net into elementary and dependent ones. The concepts of token-rich, token-poor, and equivalent siphons are newly presented. More general conditions under which a dependent siphon can be always marked are established. The existence of dependent siphons in a Petri net is investigated. An algorithm is developed to find the set of elementary siphons in a net system for deadlock control purposes. The application of the proposed elementary siphon concept to the existing deadlock control policies is discussed. A few different-sized manufacturing examples are used to demonstrate the advantages of elementary siphon-based policies. The significant value of the proposed theory via a particular deadlock control policy is shown. Finally, some interesting and open problems are discussed.     

Petri网信标和陷阱计算的矩阵半张量积方法

本文基于矩阵半张量积(semi-tensor product,STP)方法研究了普通Petri网(Petri nets,PNs)信标和陷阱的计算问题.首先,利用STP方法建立了两个矩阵方程,分别称为Petri网的信标方程(siphon equation,SE)和陷阱方程(trap equation,TE).其次,证明了计算Petri网的信标和陷阱分别等价于求信标方程(SE)和陷阱方程(TE)的非零解.同时,给出了计算Petri网所有信标和陷阱的算法.最后,实例和实验结果说明了本文方法的可行性与有效性.本文所提出的方法对于Petri网信标和陷阱的计算是非常有效的,它只涉及到矩阵的乘法运算.