Design of liveness-enforcing supervisors with simpler structures for deadlock-free operations in flexible manufacturing systems using necessary siphons

Siphons can be used to characterize deadlock states and solve deadlock problems in Petri nets that model flexible manufacturing systems. This paper presents an iterative siphon-based control (ISC) deadlock prevention policy for Petri nets via the combination of mixed integer programming (MIP) and the concept of necessary siphons (NSs). At each iteration in this ISC policy, a maximal deadly marked siphon that is closely related to deadlocks in a Petri net can be conveniently found by an MIP-based deadlock detection method. Then the places in it are classified and an NS is derived from the classified places. For each NS found, depending on its complementary set, the proposed policy adds a proper control place (CP) to make it marked (max-controlled). Moreover, during the ISC procedure, a test for redundant NSs is carried out under a certain condition in order to avoid the addition of the corresponding CPs. The siphon control process proceeds iteratively until the controlled system is live. Compared with the existing approaches, the proposed policy usually leads to a structurally simple liveness-enforcing supervisor by adding as few CPs as possible and achieves better control results. Some examples are introduced to illustrate the proposed approach.     

离散制造装配系统的活性控制

首次研究离散制造装配系统的活性控制问题.建立了系统的工件加工过程Petri网模型.通过对系统Petri网模型的结构分析,提出了导致系统死锁的两类元素结构及活性特征.对一类离散制造装配系统提出了避免死锁的Petri网控制器,这类控制器容易实现,对系统的限制小,而且使得受控系统仍具Petri网模型.对一般离散制造装配系统提出了保证系统活性的控制策略.     

离散制造装配系统的活性控制1)

首次研究离散制造装配系统的活性控制问题.建立了系统的工件加工过程Petri网模型.通过对系统Petri网模型的结构分析,提出了导致系统死锁的两类元素结构及活性特征.对一类离散制造装配系统提出了避免死锁的Petri网控制器,这类控制器容易实现,对系统的限制小,而且使得受控系统仍具Petri网模型.对一般离散制造装配系统提出了保证系统活性的控制策略.     

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

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

一类FMS的最佳活Petri网模型的综合

利用Petri网为一类柔性制造系统建模,并讨论避免系统死锁问题.通过Petri网模型的结构分析,证明了系统产生死锁的一个充分必要条件.给出了避免死锁的最佳控制器,它可以通过给系统的Petri网模型增加一些新的位置与相应的弧来实现.从而导出了这类制造系统的最佳活Petri网模型.     

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     

POC net,a subclass of Petri nets,and its application to timed Petri nets

Liveness is one of the most important properties of the Petri net analysis. This property is concerned with a capability for firing of transitions. On the other hand, place-liveness is another notion related to liveness, which is concerned with a capability for having tokens in places. Concerning these liveness and place-liveness problems, this paper suggests a new subclass of Petri net, ‘POC nets’, as a superclass of AC nets and DC nets. For this subclass, the equivalence between liveness and place-liveness is shown and a sufficient condition for liveness for this POC net is derived. Then the results are extended to liveness problem of timed Petri nets which have transitions with finite firing durations and the earliest firing rule. Although liveness of a (non-timed) Petri net is neither necessary nor sufficient condition for liveness of a timed Petri net, it is shown that liveness is preserved if the net has POC structure. Furthermore, it is pointed out that if a POC net satisfies some additional condition, Petri net liveness is equivalent to timed Petri net liveness. Finally, it is shown that liveness of timed POC nets with TC structure and the earliest firing rule is decidable with deterministic polynomial time complexity.     

On systematic methods to remove redundant monitors from liveness-enforcing net supervisors

Petri nets based deadlock prevention for flexible manufacturing systems has received much attention over the past decade, primarily due to the seminal work of Ezpeleta et al. in 1995. A Petri net based deadlock prevention mechanism is usually implemented by adding monitors or control places to a plant Petri net model such that liveness can be enforced. The significance of this methodology lies in that both a plant model and its supervisor are in a same formalism-Petri nets. Due to the inherent complexity of Petri nets, in theory, the number of additional monitors that have to been added to achieve liveness-enforcement purpose for an uncontrolled plant model is exponential with respect to the size of the model. This paper first proposes a systematic method to minimize the number of additional monitors in a liveness-enforcing Petri net supervisor such that the resultant net system has the same permissive behavior while liveness can still be preserved. Furthermore, for the liveness-enforcing Petri net supervisors of flexible manufacturing systems, which have some particular property, an algorithm is developed such that more permissive liveness-enforcing Petri net supervisors can be obtained after liveness-restrictive monitor removal. Compared with the existing techniques of eliminating redundant monitors in the literature, the complete state enumeration of a supervisor is avoided, which implies the high computational efficiency of the methods in this paper. Flexible manufacturing examples are used to demonstrate the proposed approaches.     

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

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

基于Petri网语言的并发系统性质研究

给出Petri网弱活性（无死锁）与活性的两个语言刻画,讨论了同步合成Petri网的语言性质,基于Petri网语言,给出了判定Petri网活性的充分必要条件。同时研究了Petri网同步合成过程中活性保持问题,给出保持活性的充分必要条件。这些结果为讨论网的活性测试和控制提供了形式语言的方法。     

可分解非对称选择网的活性和有界性

活性和有界性是网系统的重要行为特性.从分解以及尽可能简单分解的角度得到了非对称选择网的一个子类,可分解非对称选择网(简称DAC网),证明了DAC网系统活性的充分必要条件,同时给出了DAC网系统活性有界性的充分必要条件,也进一步讨论了判定一个Petri网系统是否是活的有界的DAC网系统的多项式算法.     

公平网的活性判断

Petri网的活性判断一直是一个广为关心的问题。本文就公平网的活性进行了研究。指出如果一个公平网的有界子网是活的,那么该公平网是活的。并给出了一个公平网活的充分必要条件。     

T-网的活性分析及其判断算法

Petri网的活性反映了实际系统的元死锁性.本文讨论了一类结构简单的Petri网-T-网的活性问题,给出了各类T-网的活性判定定理并给出了判定算法.算法主要计算工作是变迁的前序库所集和后继变迁集以及回路的判断,这三个过程实际上是一个树的搜索过程,因此算法易于实现,判定效率也大大提高.     

共享路径合成网的活性和公平性分析

本文提出了Ｐｅｔｒｉ网的共享路径合成网的概念,研究了合成网对子网的活性和公平性继承关系,最后给出一种实现共享路径合成网活性和公平性的控制装置,这些结果为网系统合成提供了有力手段,并对发系统的相关性质分析有重要的应用价值。     

加权非对称选择网活性和有界性分析

给出了Petri网系统的一个重要子类,即加权非对称选择网(weighted asymmetric choice net,简称WAC网)系统活性的一个充分条件和一个必要条件;同时,提出了活的有界的WAC网系统的判定条件,进而给出了WAC网活性满足单调性的充分必要条件.     

Timing and liveness in continuous Petri nets

Fluidification constitutes a relaxation technique for studying discrete event systems through fluidified approximated models, thus avoiding the state explosion problem. Moreover, the class of continuous models thus obtained may be interesting in itself. In Petri nets, fluidification leads to the so-called continuous Petri nets, which are technically hybrid models. Under infinite server semantics, timing a continuous Petri net model preserves the liveness property, but the converse is not necessarily true, and if the autonomous net model is not live, the timing may transform it into a live model. In this paper, we investigate the conditions on the firing rates of timed continuous models that make a given continuous system live.     

Design of liveness‐enforcing supervisors via transforming plant petri net models of FMS

This paper focuses on the deadlock prevention problems in a class of Petri nets, systems of simple sequential process with resources, S³PR for short. By structure analysis, we propose an approach that can transform a plant net model into a weighted S³PR (WS³PR) that is behaviorally equivalent to the plant model. The WS³PR is made to be live by properly reconfiguring its weight distribution such that its all strict minimal siphons are self‐max'‐controlled. The resulting WS³PR can serve as a liveness‐enforcing Petri net supervisor for the plant model after removing some idle and operation places. A live controlled system can be accordingly obtained by synchronizing a plant model and the places whose weights are regulated. This research shows that a small number of monitors is obtained, leading to more permissive behavior of the controlled system. Examples are used to demonstrate the proposed concepts and methods. 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.     

一类Petri网—S4R的死锁预防策略

S4R网作为一种特殊的Petri网子类,与S' PR网相比可以建模更为复杂的、拥有多个并行加工进程的资源分配系统。针对S4R网提出了一种综合的死锁预防策略。利用MIP检验由S4R网建模的柔性制造系统的活性,在新的信标控制概念的基础上对需要控制的系统进行控制。再利用MIP检验受控网系统的活性,进一步控制不活的网系统。避免了对一些网不必要的控制以及一些网过于保守的控制,得到许可行为较多的控制器。     

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.