基于变迁覆盖的制造系统死锁控制策略

基于系统Petri网模型,研究柔性制造系统的死锁控制问题.论文利用变迁覆盖为系统设计活性控制器.变迁覆盖是由一组极大完备资源变迁回路组成的集合,其变迁集覆盖了Petri网中所有极大完备资源变迁回路的变迁集.验证变迁覆盖的有效性,然后仅对有效变迁覆盖中的极大完备资源变迁回路添加控制位置,就得到系统的活性受控Petri网.这种受控Petri网包含的控制位置个数少,从而结构相对简单.最后通过一个例子说明了所提出的死锁控制策略的构成与特点.     

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.     

Maximally Permissive Petri Net Supervisors for Flexible Manufacturing Systems with Uncontrollable and Unobservable Transitions

This paper presents a deadlock prevention policy to obtain behaviorally optimal supervisors for flexible manufacturing systems with uncontrollable and unobservable transitions. The conditions of uncontrollability and unobservability of transitions are revealed in the sense of the implementation of a Petri net supervisor. Then, integer linear programming models are designed to obtain a Petri net supervisor such that all legal markings are reachable and the number of control places is reduced. We also show that a controllable transition can be unobservable and self‐loops can be used to disable the transition but do not observe its firing. Finally, examples are provided to illustrate the proposed approach.     

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

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

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

本文基于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.     

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

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

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网的抽象简化方法,大规模压缩优化调度所需搜索的状态空间;再次,定义了策略Petri网以描述最优调度策略.最后,给出了平行Petri网与策略Petri网同步执行算法,使得平行Petri网与物理系统同步执行.     

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.     

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.     

Modeling production configuration using nested colored object-oriented Petri-nets with changeable structures

Configuring production processes based on process platforms has been well recognized as an effective means for companies to provide product variety while maintaining mass production efficiency. The production processes of product families involve diverse variations in manufacturing and assembly processes resulted from a large variety of component parts and assemblies. This paper develops a multilevel system of nested colored object-oriented Petri nets with changeable structures to model the configuration of production processes. To capture the semantics associated with production configuration decisions, some unique modeling mechanisms are employed, including colored Petri nets, object-oriented Petri nets, changeable Petri net structures, and net nesting. The modeling formalism comprises resource nets, manufacturing nets, assembly nets and process nets. The paper demonstrates how these net definitions are applied to the specification of production process variants at different levels of abstraction. Also reported is a case study in an electronics company. The system model is further analyzed with focus on conflict prevention and deadlock detection.     

Deadlock-free Supervisor Design for Robotic Manufacturing Cells With Uncontrollable and Unobservable Events

In this paper,a deadlock prevention policy for robotic manufacturing cells with uncontrollable and unobservable events is proposed based on a Petri net formalism.First,a Petri net for the deadlock control of such systems is defined.Its admissible markings and first-met inadmissible markings(FIMs)are introduced.Next,place invariants are designed via an integer linear program(ILP)to survive all admissible markings and prohibit all FIMs,keeping the underlying system from reaching deadlocks,livelocks,bad markings,and the markings that may evolve into them by firing uncontrollable transitions.ILP also ensures that the obtained deadlock-free supervisor does not observe any unobservable transition.In addition,the supervisor is guaranteed to be admissible and structurally minimal in terms of both control places and added arcs.The condition under which the supervisor is maximally permissive in behavior is given.Finally,experimental results with the proposed method and existing ones are given to show its effectiveness.     

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resourcetransition circuits and their saturated states. The concept facilities the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reach their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For an general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resource-transition circuits and their saturated states. The concept facilitates the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reaching their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For a general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

Structuring Acyclic Petri Nets for Reachability Analysis and Control

The incidence matrices—from places to transitions and vice versa—of an acyclic Petri net can obtain a block-triangular structure by reordering their rows and columns. This allows the efficient solution of some reachability problems for acyclic Petri nets. This result is further used in supervisory control of Petri nets; supervisors for Petri nets with uncontrollable transitions are constructed by extending the method of Yamalidou et al. (1996) to Petri nets where transitions can be executed simultaneously. A large class of Petri nets with uncontrollable transitions is given for which the maximally permissive supervisor can be realized by a Petri net. The original specification is algorithmically transformed—by using the results for acyclic Petri nets—into a new specification to take the presence of uncontrollable transitions into account. The supervisor is obtained by simple matrix multiplications and no linear integer programs need to be solved. Furthermore, a class of Petri nets is given for which the supervisor can be realized by extending the enabling rule with OR-logic.     

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.     

Robust design of flexible manufacturing systems using, colored Petri net and genetic algorithm

A method is presented for the robust design of flexible manufacturing systems (FMS) that undergo the forecasted product plan variations. The resource allocation and the operation schedule of a FMS are modeled as a colored Petri net and an associated transition firing sequence. The robust design of the colored Petri net model is formulated as a multi-objective optimization problem that simultaneously minimizes the production costs under multiple production plans (batch sizes for all jobs), and the reconfiguration cost due to production plan changes. A genetic algorithm, coupled with the shortest imminent operation time (SIO) dispatching rule, is used to simultaneously find the near-optimal resource allocation and the event-driven schedule of a colored Petri net. The resulting Petri net is then compared with the Petri nets optimized for a particular production plan in order to address the effectiveness of the robustness optimization. The simulation results suggest that the proposed robustness optimization scheme should be considered when the products are moderately different in their job specifications so that optimizing for a particular production plan creates inevitably bottlenecks in product flow and/or deadlock under other production plans.     

Comments on “An Iterative Synthesis Approach to Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems”

In the above paper, it proposes a deadlock prevention policy for a flexible manufacturing system (FMS), which needs the complete state enumeration of the FMS that is modeled with Petri nets. The reachability graph of a Petri-net model is divided into two parts: the live zone (LZ) and the deadlock zone (DZ). The states in the LZ of the reachability graph of a Petri net constitute the legal behavior of the net from the viewpoint of deadlock prevention. The concept of first-met bad markings is proposed. A first-met bad marking is a node in DZ, whose father nodes are in LZ. The deadlock prevention policy is used in an iterative way. At each iteration, a first-met bad marking is identified from the reachability graph of a Petri net to be controlled. The reachability of a first-met bad marking is prohibited by adding a monitor, establishing a marking invariance relationship between the additional monitor and the activity places that are marked under the first-met bad marking. To achieve this, without a formal proof, [Lemma 1] is developed as shown in this article.     

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.