复杂并行共享资源与系统死锁

研究了制造过程共享资源引起的死锁问题。提出了并行资源死锁结构的概念。对于包含该结构的系统，给出了Petri网模型具有可能死锁的充要条件。基于资源向量的概念，提出了一个简单方法，用于判断系统是否具有可能的死锁。针对包含死锁结构的系统，提出了系统Petri网无死锁的设计方法，举例说明了这种方法的应用。     

自动制造系统的一种死锁避免策略

基于Petri网的结构分析理论，提出了自动制造系统Petri网模型的一种死锁控制方法，在这种策略的控制下，避免了系统中死锁的产生，从而许多制造系统的Petri网模型具有活性，提出了一种保证所有严格极小信标至少含有一个托肯的方法，对冗余严格极小信标的研究，提高了Petri网复杂自动制造系统的建模能力。结果表明，在设计无死锁的Petri网格型时，不是所有的严格极小信标都要考虑，从而简化了设计结果和控制算法。     

复杂并行共享资源柔性制造系统中的死锁结构

深入研究了独立制造过程共享资源引起的死锁问题 ,提出了并行资源死锁结构的概念。同时 ,基于资源向量 ,给出了一种简单的形式化方法 ,用于判断一个系统是否由于包含并行共享而具有可能的死锁 ,提出了一种使并行共享资源制造系统 ,其 Petri网控制器无死锁的设计理论和方法 ,这种方法的主要特点是计算简单 ,最后举例说明了这种方法的应用。     

一种半导体自动化制造系统中的死锁避免

在半导体自动化制造TRACK系统中，由于没有缓冲空间，死锁避免更加困难，保守策略大大降低资源利用率，而路径的柔性为获得更有效的死锁避免策略提供了可能性，本文采用面向资源的着色Petri网建模，基于该模型并利用路径柔性，提出一个系统无死锁的充分条件，并给出相应的控制规律，依据该规律，系统中任务的个数不受限制，并能处理多晶片类型，最后，给出一个说明方法的实用实例。     

冗余信标及其在Petri网结构控制中的应用

提出了冗余严格极小信标的概念 ,冗余信标是网拓扑的一种特殊结构。在保证网系统的所有信标不被清空时 ,只需要考虑那些非冗余的严格极小信标即可。这样便降低无死锁Petri控制器设计的复杂性 ,大大增强了Petri网处理复杂系统的能力。同时提出了一种死锁控制的迭代算法 ,使用冗余信标的概念可以大大简化Petri网的设计。以自动制造系统为例 ,说明了这种概念的应用。     

基于有色Petri网的FMS生产系统的研究

运用有色Petri网对FMS柔性生产系统进行建模,在深入研究Petri网和扩展Petri网相关理论的基础上,从整个生产系统的控制功能方面验证了利用Petri网所建立系统模型的正确性。再在CPNTools环境下对生产系统模型进行了仿真,通过对生产系统仿真模型运行状态的跟踪,发现了具体导致生产系统运行出现死锁状态的原因,并提出相应的改进方法,该方法成功地应用于FMS生产系统的整个加工过程中。     

自动小车存取系统中轨道导引小车环路死锁控制的研究

为防止自动小车存取系统中轨道导引小车环路死锁现象,提出了一种基于Petri网和有向图的死锁控制方法.该方法首先应用有色赋时Petri网建立了自动小车存取系统的动态模型,并结合有向图工具,阐述了导致环路死锁的原因.在此基础上,针对单一轨道双向运行的轨道导引系统,探讨了其环路死锁的主要表现形式,给出了轨道导引小车无死锁运行的充要条件,并提出了包含临界状态在内的死锁避免控制策略.最后,结合实例说明了环路死锁控制的有效性.     

一种扩展了条件和概率信息的Petri网

为了使Petri网具有根据Token中记录的信息和当前处理情况,进行处理路线选择和分析各个变迁及所有可能变迁集执行概率的功能,提出了一种扩展了条件和概率信息的Petri网.该网为经典Petri网的库所和变迁扩展了输入条件集、概率输出条件集及选择函数.通过条件概率Petri网的表示定义了其建模图的表达方法,通过运行过程分析描述了该网的运行原理,通过可达、死锁路线发现及概率计算的方法分析了各个变迁、所有可能变迁集及死锁路线的执行概率,并给出了死锁的解决策略.最后利用条件概率Petri网对叶片的制造过程进行建模分析,显示了其对复杂业务流程建模和指导优化资源配置的能力.     

S3PMR网的一种死锁预防优化策略

针对Petri网的S3PMR中的死锁预防问题,提出一种优化的控制器设计方法.当控制器的优化性不能保证时,要对所添加的控制器进行结构分析,提出了一个输出弧位置最优化的死锁预防控制算法.将S3PMR中的严格极小信标分为基本信标和从属信标,对每一个基本信标添加一个控制库所,使其P-不变式可控,且不会产生新的可被清空信标,对从属信标的控制则通过调整基本信标的控制深度变量来实现.从而用少量的控制库所得到结构更简单、许可行为更多的活性Petri网控制器.     

一种基于Petri网和AGA算法的测试系统死锁预防策略

在自动测试系统中,很多任务需要并行测试.测试过程比串行测试复杂,较容易出现死锁现象,因此提出一种基于Petri网和自适应遗传算法(adaptive genetic algorithm)的死锁预防策略.在该策略中,首先为自动测试系统建立一个Petri网模型,然后将Petri网的状态方程作为约束条件,最后求出模型的发射序列即系统中无死锁的任务调度路径.Petri网的发射序列求解一直是NP问题,针对这种情况,引入自适应遗传算法对可行解空间进行全面的搜索,可得到所有无死锁的路径.最后,通过雷达接收机的并行测试例子,和启发式算法搜索进行对比,进一步体现了该死锁预防策略的优越性.     

Deadlock control of concurrent manufacturing processes sharing finite resources

A novel deadlock control policy is developed for modeling the concurrent execution of manufacturing processes with limited shared resources through a class of nets, ES³PR. A relevant property of the system behavior is that it is deadlock-free. Recent work has shown that deadlock situations in a plant system can be easily characterized by the structural analysis of the system, particularly, in terms of unmarked or insufficiently marked siphons in its Petri net model. The strict minimal siphons in a plant ES³PR net model are divided into elementary and dependent ones. The proposed deadlock prevention policy is to make all siphons satisfy maximal cs-property when the elementary siphons in the plant Petri net model are properly supervised via explicitly adding monitors for them with appropriate initial markings. Compared with the existing approaches in the literature, the advantage of the policy is that a much smaller number of supervisory places (monitors) are added and unnecessary iterative processes are avoided. Finally, its application is illustrated by a flexible manufacturing example.     

Application of Petri nets for deadlock analysis and avoidance in flexible manufacturing systems

Unreasonable dispatching resources to jobs in flexible manufacturing system (FMS) may result in a deadlock situation. This serious situation is studied and avoided through Petri net (PN) analysis techniques in this paper. Firstly, a production Petri net (PPN) model for a given FMS is developed. Based on a certain set of resources in PPN, the concepts of a deadlock state and a potential deadlock state are introduced. Then, we present a deadlock avoidance method that consists of two parts. One is the construction of a deadlock state equation that describes the intrinsic relationship between resources assignation and a deadlock state in PPN. This equation is a necessary and sufficient condition for the occurrence of a deadlock situation. The other is the construction of a restrictive PN controller for each deadlock state equation. This restrictive PN controller can control the resources dispatching by excluding some enabled transitions from firing, consequently avoiding the deadlock. This method is minimally restrictive and allows the maximal use of resources not only for normal FMS, but also for special FMS with cyclic deadlock structure chain (i.e., a pathological type of circular waiting structure). Finally, two applications are given to illustrate the validity of this method. The results show that this method can be efficiently implemented in practical FMS.     

Design of deadlock prevention supervisors using Petri nets

This paper proposes a methodology to synthesize supervisors for a class of sequential resource allocation system for flexible manufacturing systems. The type of Petri nets are called S3PR, where deadlocks are related to emptied siphons. In a former paper (Huang et al., IEEE Trans Syst Man Cybern, 2007), a deadlock prevention policy was proposed based on Petri nets siphons for the type of Petri nets. Since all minimal siphons should be controlled, the deadlock prevention policy is very time-consuming when the system is large. In this research, a concept of the elementary siphon is used to reduce the number of control places. A new siphon-based policy of deadlock prevention for the type of Petri nets is presented. This policy consists of two main stages: The first stage, called elementary siphons control, adds control places to the original net model to prevent elementary siphons from being emptied. The second stage, called generalized siphons control, adds control places that adopt a conservative policy of controlling only the release of parts into the system are used. Compared to the existing approaches, the new deadlock prevention policy can obtain a structurally compact deadlock prevention supervisor by adding only a few control places. Finally, numerical experiments under reachable states illustrate that the proposed algorithm appears to be more permissive than the closely related approaches.     

Deadlock control of flexible manufacturing systems via invariant–controlled elementary siphons of petri nets

Effective resolution for deadlock problems plays an important role in the operation of automated flexible manufacturing systems (FMS). Based on P-invariants and elementary siphons of Petri nets, a deadlock prevention policy is developed for a special class of Petri nets that can well model many FMS. Siphons in a plant net model are divided into elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that the siphon is invariant-controlled. Our method guarantees that no emptiable control-induced siphon is generated due to the addition of the monitors. When all elementary siphons are controlled, the controllability of a dependent siphon is ensured by properly setting the control depth variables of its related elementary siphons. An FMS example is utilized to illustrate the proposed methods.     

FMS中资源共享导致的死锁状态及其避免方法

针对FMS中多种操作对有限资源的竞争会导致死锁状态，采用Petrinet分析技术对其进行了研究。建立了FMS的PPN模型，并在此基础上给出了直接死锁和潜在死锁的定义；引入了死锁状态方程的概念并给出了其构造方法；描述了死锁状态和资源分布之间的内在联系，并提出了一种死锁避免方法。实例表明该方法能够简单有效地避免死锁的产生，并允许资源的最大利用。     

USING COLORED TIMED PETRI NET FOR THE SOLUTION OF DEADLOCK IN A FLEXIBLE ASSEMBLY SYSTEM

0 INTRODUCTIONThe manufacturing process and assembly inworkshop are regarded as discrete events.Thesystem,which involves these process is called discreteevent dynamic system (DEDS). Many modeling toolshave been employed for modeling this kind of system,such as, queuing theory, critical path method, max-min algebra, perturbation analysis and Petrinet.AInong these tools, Petri nets are graphical andmathematical modeling too1 which is applicable tomany systems. They are promising tools fo…     

Deadlock prevention and avoidance in FMS: A Petri net based approach

The use of structure theory of Petri nets to develop efficient deadlock prevention and deadlock avoidance methods for flexible manufacturing systems (FMSs) modelled by S⁴R nets is demonstrated. Major synchronisation patterns, such as generalised parallel and sequential mutual exclusion, frequently observed in FMS contexts can be represented by this class. The liveness property of a given S⁴R net (deadlock-freeness in the context of FMSs) is characterised in terms of structural Petri net elements called siphons. An efficient method for controlling minimal siphons of a given S⁴R net is developed where local control places are added to the net. A sufficient condition for liveness of the augmented net is provided. This constitutes a deadlock prevention approach. When the net liveness condition is not satisfied, an on-line controller, using a dynamic resource allocation policy, is developed for the augmented net. The performance of the proposed approaches is illustrated using several examples.     

On a maximally permissive deadlock prevention policy for automated manufacturing systems by using resource-oriented Petri nets

It is theoretically and practically significant to synthesize a maximally permissive (optimal) controller to prevent deadlocks in an automated manufacturing system (AMS). With an AMS being modeled with Petri nets, by the existing methods, integer linear programming (ILP) problems are usually formulated and solved to obtain optimal policies by forbidding illegal markings at the same time no legal marking is excluded. Without an efficient technique for solving an ILP, such a method is usually computationally prohibitive. A resource-oriented Petri net (ROPN) is employed to model a class of AMS for resolving the deadlock control problem with maximal permissiveness in this paper. Efficient methods are developed to figure out the key structures in an ROPN model for deadlock prevention. Based on the structural properties of ROPN models, this work explores several types of illegal markings that can be prohibited optimally by structural analysis. For these markings, a deadlock prevention policy can be derived in an algebraic way without solving a notorious ILP problem. For the other markings, linear programming (LP), instead of ILP, approaches are developed to forbid them optimally. Thus, a maximally permissive controller can be developed while the computational cost is reduced greatly. The proposed methods are verified by typical examples in the literature.     

自动制造系统中的迭代式死锁预防策略

为解决自动制造系统中的死锁问题,提出一种将混合整数规划算法和Petri网相结合的迭代式预防策略。在该策略中,混合整数规划算法中的0／1变量用来表示Petri网模型中的库所和变迁是否与一个最大的可被清空的信标相关。由于从一个最大的可被清空的信标中可以容易地计算出一个严格极小信标,就可以在不遍历所有的严格极小信标的情况下,直接求得一组基本信标,从而大大地降低了策略的时间算法复杂度。同时,控制该组基本信标可以确保目标系统具有简单的控制器结构和尽可能多的许可行为。实验结果表明了该控制策略的有效性和高效性。