柔性制造系统非阻塞监督控制器优化设计

针对一类含有并发执行装配过程的柔性制造系统G-systems,提出一种新的死锁预防策略保证该系统的非阻塞性,即在控制下,受控系统从任意可达状态都可以到达理想状态.首先对Petri网模型中基本信标实施控制,保证了基本信标的最大可控,然后通过线性规划算法求取所有从属信标满足可控性的条件,即获得基本信标的控制深度变量.与现有方法相比,该策略优点在于只需加入少量的控制库所,就可避免不必要的迭代过程;其次是提出控制器输出弧位置优化策略,得到了结构更为简单、许可行为更多的非阻塞Petri网控制器.     

基于Petri网的无死锁控制器设计

对柔性制造系统提出了一种新的死锁预防控制算法。运用区域理论对Petri网模型设计一个控制器,对控制器中所有严格极小信标求取控制库所与资源库所的代数式,保证了所有的严格极小信标受控。与现有方法相比,该策略不必考虑控制器结构,只需根据这些代数式分布控制器中的资源,就可以得到相应无死锁监督控制器。     

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

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

一类活性Petri网控制器的冗余检测及结构简化

S4R(systems of sequential systems with shared resources)网是分析和解决柔性制造系统死锁现象常用的一种重要的Petri网子类模型,现有的基于S4R网的死锁预防方法通常采用对部分或者全部严格极小信标添加控制库所来实现.此类方法的不足在于得到的活性S4R控制器中往往存在冗余控制库所.针对已为网中每一个严格极小信标都逐一添加了控制库所和相关连接弧的活性S4R控制器,本文提出并设计了一种基于整数规划技术的冗余检测及结构简化方法,由此得到结构更简单、行为允许度更高的活性S4R控制器.该方法的核心思想是:如果网中已经存在一个p-不变式使得某个严格极小信标满足最大受控条件,那么为该严格极小信标添加的控制库所就是冗余的.由于该方法无需进行Petri网的可达性分析,避免了状态组合爆炸问题,因此具有较高的可行性和计算效率.最后用实验验证了本文方法的正确性和有效性.     

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

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

Petri网的子类G–system网的死锁控制策略

由于柔性制造系统中的死锁问题与对应建模Petri网中信标密切相关, 如何准确和快捷地求解这样的信标, 对于基于信标可控的死锁控制策略设计而言, 是十分重要的. 本文提出了基于G-system网灵巧信标的迭代式求解与受控的死锁控制策略. 与目前求解导致死锁信标所采用的部分枚举方法相比, 该方法避免了先求解出最大的死标识信标, 进而从中提取极小信标的步骤, 提高了信标的计算效率. 同时, 通过添加适当的控制库所, 使得灵巧信标满足max'-controlled, 获取的活性受控G–system网系统的许可行为数目可以得到进一步的提升. 通过理论分析和算例验证, 表明了该死锁控制策略的正确性和有效性.     

普通Petri网最大可达数的两段式死锁控制策略

针对普通Petri网的死锁问题,本文提出了可实现最大可达数的两段式死锁控制策略(deadlock control policy,DCP).第1步,该策略求解原网(N0,M0)的基本信标(elementary siphons,ES)和从属信标(dependent siphons,DS),对每个基本信标添加控制库所(control place,CP)和控制变迁(control transition,CT),获得拓展网系统(N′,M′).第2步,构建拓展网系统的P–不变式整数规划问题,测试原网中从属信标的可控性.若所有从属信标满足可控条件,则直接得到活性受控网系统(N*,M*);反之,对不满足可控条件的从属信标也添加控制库所和变迁,从而也得到了(N*,M*).通过理论分析和算例验证,表明了该死锁控制策略的正确性和有效性.相比目前文献中的可实现最大许可行为数目(number of maximally permissive behavior,NMPB)的普通Petri网死锁预防策略,该DCP获取的活性受控网系统(N*,M*)可达数目与原网(N0,M0)是相同的,且最大可达数(maximally reachable number,MRN)高于最大许可行为数目NMPB.     

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

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

JMS死信处理机制的设计

JMS运行过程中,队列或持久化主题中存在的死信成为系统性能的瓶颈和系统运行的不安全因素。通过对JMS通信模型和消息头进行分析,找到死信产生的原因以及消息头中涉及到如何判断死信的两个重要属性。首先提出死信判断规则和一种过滤死信的方案,然后提出一种在过滤的基础上周期性地对死信进行处理的解决方案,最后从性能的角度上提出两种处理方法,同时对死信在队列中存在的最大不合法时间进行了计算,并对每于中方案的优缺点进行了分析。     

无线传感器网络定位算法中的信任评估

为增强无线传感器网络中信标节点之间的信任关系并消除恶意节点,提出基于区块链的信任管理算法.算法核心是对基于行为和数据的信任进行评估.在行为部分从4个维度进行计算,保证全面性;将每个信标节点的行为、反馈以及数据的信任值,广播到基站以生成信任值的区块链;为保证无线传感器网络定位的可靠性和一致性,该算法将信任值最小的信标节点丢弃.实验结果表明,所提算法各方面性能均优于现有算法.     

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.     

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.     

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

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

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.     

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.