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

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

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

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

自动制造系统中的死锁

本文综述了制约当前自动制造系统实现的瓶颈问题一死锁问题及其产生的原因，死锁的种类，研究方法及数学工具，提出了死锁的主动控制的概念。     

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

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

一种解决FMS刀具流死锁问题的方法

提出了一种解决FMS中刀具流死锁问题的方法———刀具流死锁图判定法,首次提出了刀具申请分配图的概念,定义了刀具流死锁图,把刀具流死锁和死锁图联系起来,建立了刀具流死锁的判定定理,给出了两种死锁检测算法。该方法解决了FMS中的刀具流死锁问题,为刀具流控制问题的深入研究奠定了理论和技术基础。     

FMS运控软件调试环境中的死锁检测方法

ＦＭＳ中存在死现象是理想的，此时系统至少存在一个等待环，环中工件处于互相等待彼此所占有资源的状态。对于一个ＦＭＳ控制软件，如果不具死锁的预测和回避方法，在实际运行过程中就会因可能出现的死锁现象而发生故障，在建立ＦＭＳ运控系统调试环境时，本文旨于确认被测ＦＭＳ运控软件的死锁预测和回避功能。在被测系统Ｐｅｔｒｉ网模型的基础上，根据选定的调度策略确定所有被占用资源上工件的目标库所集，以检验系统中是否在死     

基于刀具寿命约束的FMS刀具流死锁研究

刀具流死锁问题是柔性制造系统(FMS)调度中的重要核心内容,为实现合理的死锁回避,必须深入分析刀具流死锁的相关性质。在前期研究的基础上,分析了刀具寿命对刀具申请的影响,进一步建立了基于刀具寿命约束的刀具申请分配图,分析了死锁的相关性质,建立了在考虑刀具寿命的情况下的刀具流死锁判定定理,为下一步的深入分析死锁检测算法和死锁回避准备了基础。     

FMS刀具流死锁控制策略与分派算法的研究

刀具流死锁控制及刀具分派问题是柔性制造系统(FMS)调度中的重要核心内容,为实现合理的死锁回避和刀具分派,在前期研究的基础上,通过建立刀具申请分配图,分析了死锁的相关性质,指出了FMS中刀具流死锁的两大根源是工件选择的不合理和刀具分派的不合理。提出了一种解决刀具流调度问题的两级死锁控制策略,建立了动态调度原理模型,给出了死锁检测算法和刀具分派算法。分析表明该策略与算法能够使得刀具流死锁的两大根源均得以回避,实现了刀具流死锁控制与刀具分派。     

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

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

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

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

银行家算法在柔性制造系统中的改进和应用

提出了一种应用于柔性制造系统中的避免死锁的算法。该算法是对银行家算法的改进。银行家算法适用于操作系统，而操作系统与柔性制造系统之间存在差异，为使该算法适用于柔性制造系统，必须对其进行改进。通过研究操作系统中的进程与制造系统中的加工任务之间的差别，对算法进行改进。对制造系统采用形式化的建模方法，将建立的模型转换成适合进行模型检查的形式。运用SPIN来对此算法进行仿真，并验证此算法模型的正确性。     

Deadlock avoidance control for manufacturing systems with multiple capacity resources

This paper addresses the problem of designing a control scheme capable of avoiding deadlock conditions for a class of manufacturing systems. The considered model for the system under control is based on Petri nets, and is formulated according to well-known modelling rules. A deadlock avoidance policy is proposed which is an extension of a previously presented one. The proofs of its main properties are briefly sketched. Finally, an example of an automated manufacturing system for which such a deadlock avoidance policy has been applied is discussed.     

Deadlock Avoidance for Sequential Resource Allocation Systems: Hard and Easy Cases

Deadlock is a major problem for systems that allocate resources in real time. The key issue in deadlock avoidance is whether or not a given resource allocation state is safe: that is, whether or not there exists a sequence of resource allocations that completes all processes. Although safety is established as NP-complete for certain broad resource allocation classes, newly emerging resource allocation scenarios often exhibit unique features not considered in previous work. In these cases, establishing the underlying complexity of the safety problem is essential for developing the best deadlock avoidance approach. This work investigates the complexity of safe resource allocation for a class of systems relevant in automated manufacturing. For this class, the resource needs of each process are expressed as a well-defined sequence. Each request is for a single unit of a single resource and is accompanied by a promise to release the previously allocated resource. Manufacturing researchers have generally accepted that safety is computationally hard, and numerous suboptimal deadlock avoidance solutions have been proposed for this class. Recent results, however, indicate that safety is often computationally easy. The objective of this article is to settle this question by formally establishing the NP-completeness of safety for this class and investigating the boundary between the hard and easy cases. We discuss several special structures that lead to computationally tractable safety characteristics.     

Design of Supervisors to Avoid Deadlock in Flexible Assembly Systems

Modern production systems exhibit a high degree of resource sharing that can lead to deadlock conditions. Deadlock arises when some parts remain indefinitely blocked because each of them requests access to a resource held by some other parts. One of the tasks of the control system lies in preventing such situations from occurring by proper resource management.This article addresses the deadlock problem for an important class of production facilities, that is, flexible assembly systems, that can perform both manufacturing or assembly operations. In particular, we develop an approach to deadlock avoidance based on a supervisory control that works by inhibiting or enabling the events involving resource allocation. The article proposes two supervisors characterized by easy implementation, efficiency, and flexibility in resource management. The analysis of some case studies, performed by discrete event simulation, confirms the effectiveness of the approach.     

Deadlock-free multi-attribute dispatching method for AGV systems

This paper aims at developing a flexible, efficient, and deadlock-free dispatching method for automated guided vehicle systems. For this purpose, a deadlock-free multi-attribute dispatching method with dynamically adjustable weights (AWMA) is proposed. Traveling distance, input, and output buffer statuses are selected as dispatching attributes according to the efficiency and deadlock avoidance requirement. The weight for each attribute is dynamically adjusted according to the processing load and transportation load of the system. To ensure the system to be deadlock-free, a deadlock avoidance policy based on remaining capacity concept is introduced. It works by temporarily forbidding critical tasks according to the system state, which will otherwise cause system deadlock. The AWMA method is formed by integrating the deadlock avoidance policy into the multi-attribute dispatching procedure. To validate the effectiveness of the proposed method, several simulation experiments were carried out to compare three commonly used dispatching methods with the proposed one under different system settings. The simulation results indicate that the deadlock avoidance policy can guarantee the system to be deadlock-free and that the proposed method is efficient.     

A resource decoupling approach for deadlock prevention in FMS

Many deadlock prevention approaches have been suggested in the literature for Petri net models of flexible manufacturing systems, based on siphon enumeration and control. With medium and large problem dimensions, such methods often require both an excessive computational load and extremely large control sub-nets, making them unfeasible or impractical. In this work, a simple approach is proposed for the design of sub-optimal but compact controllers. The approach is based on the anticipated allocation of a sub-set of resources that decouples the deadlock prevention problem in two much smaller and simpler problems, each devoted to the deadlock prevention for a sub-set of resources only. The application of the two designed control sub-nets to the original Petri net together with resource anticipation ensures deadlock prevention. A heuristic algorithm is also provided for the selection of a suitable resource partition, in order to maximize the control quality and performance. Several illustrative benchmark examples are provided.     

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

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

Enhancement of an efficient liveness-enforcing supervisor for flexible manufacture systems

This paper presents an enhanced efficient control method to obtain a maximally permissive deadlock prevention policy for flexible manufacturing systems (FMSs) based on Petri nets and the theory of regions. It is well known that the marking/transition-separation instances (MTSIs) method with the theory of regions has been extensively studied as one of optimal policies (i.e., maximally permissive) in FMS deadlock problems. However, all MTSIs are required to identify for controlling the deadlock problems. Therefore, this paper proposes novel crucial MTSIs (CMTSIs) to alleviate the computation cost due to the involvement of few MTSIs. This article elucidates CMTSI is the foundation of MTSI. Moreover, a maximally permissive liveness-enforcing supervisor with efficient computation can be implemented based on the experimental results, demonstrating that the proposed control policy is the most efficient algorithm among the closely related approaches.     

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.     

A live subclass of petri nets and their application in modeling flexible manufacturing systems

In this paper a novel policy is proposed to solve the deadlock problem in a class of flexible manufacturing systems based on the notion that each shared buffer is partitioned into parts to store different types of products, respectively. A subclass of Petri nets called resource-shared net with buffers (RSNB) is defined. An RSNB is constructed by synthesizing some marked graphs, and each marked graph can model the process of manufacturing one type of product. RSNB cannot only model the concurrent execution of manufacturing processes, but also ensure that the modeled system is live. The process of constructing RSNB is described in detail, and a minimal siphon based necessary and sufficient condition is provided to characterize the liveness of RSNB.