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

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

自动制造系统中的死锁

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

自动制造系统中的死锁及其主动控制

本文系统论述了当前制约自动制造系统（ＡＭＳｓ）实现的瓶颈问题－死锁问题及其产生的原因、种类、研究方法和数学工具,提出了死锁的主动控制的概念。     

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

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

自动制造系统中的死锁

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

柔性制造单元的无死锁监控方法

应用离散事件系统的监控理论,针对一类无中间缓冲区、顺序加工的柔性制造单元,提出了一种基于有限状态机模型的无死锁监控器的设计方法,证明了监控器的可行性,并通过具体的应用实例验证了理论分析的结果。     

多资源服务处理系统的活性控制策略

为解决一类具有多资源服务处理制造系统中的死锁问题,提出了利用Petri网描述系统结构和动态特征的方法,以及循环结构的新概念,证明了循环结构是导致系统死锁的惟一结构特征。利用辅助系统Petri网模型,提出了计算系统的所有基本极大循环结构的方法。对每个基本极大循环结构增加一个控制位置及其相关弧以限制其资源的利用,从而有效地避免系统死锁的发生。     

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

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

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

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

柔性制造系统一种次优化的死锁控制设计

为解决柔性制造系统中的死锁问题,以受控系统的许可行为作为指标,根据Petri网基本信标理论,提出了一种次优化的活性控制器设计方法.根据基本信标和从属信标的可控性关系,通过调整控制库所的初始标志,获得了具有较多许可行为的活性Petri网控制器.与文献中其他方法相比,所提的控制策略具有更好的许可性.     

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.     

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

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

Real-Time Deadlock Detection and Recovery for Automated Manufacturing Systems

The deadlock problems of automated manufacturing systems (AMS) are discussed in this paper. A dynamic-edge graph (DEG) with double labels was designed to model the AMS, to identify distinct part flows, to represent the states and capture the concurrent behaviour of the AMS. In the AMS, we assume that each resource has its own unit-capacity buffer to which it can be transferred when a deadlock situation occurs. The motivation of this research was to define the state of each part and propose a simple, dynamic and adaptable approach, based on double labels and some basic concepts in graph theory, for detecting a deadlock in real time and resolving deadlocks in the AMS. Through this approach both the utilisation of resources and the overall throughput can be improved. The proposed algorithmic procedure, in accordance with the states arrived at and generated from the model, can serve as a functional module for the operation of an AMS without the need to revise the original control extensively. In addition, the proposed procedure can be used cooperatively with a dispatching controller and expanded with little modification. ID="A1"Correspondance and offprint requests to: Dr W.-C. Yeh, Department of Industrial Engineering, Feng Chia University, PO Box 67-100, Taichung, Taiwan 407. E-mail: wcyeh@fcu.edu.tw     

自动制造系统中的事件、资源和Petri网

讨论了自动制造系统中事件的形式化表示方法，以及制造系统中的工序和资源的Ｐｅｔｒｉ网表示．在此基础上还讨论了一类自动制造系统Ｐｅｔｒｉ网关联矩阵的构造形式和初始标识的确定方法．最后提出了自动制造系统Ｐｅｔｒｉ网控制器的形式化设计方法．     

Matrix Controller Design and Deadlock Analysis of Automated Manufacturing Systems. Part 1. Designing the Matrix-Based Controller

A system theory approach is used to design rule-based discrete-event controllers for the sequencing of jobs in manufacturing systems. The controller is described in terms of matrix equations that are easy to implement on a personal computer. Industrial engineering (IE) techniques and the concepts of Petri nets (PN) are included. A standard bill of materials (BOM) is used in the first design step to make a "task sequencing matrix". Then a resource requirement matrix is constructed to add non-shared resources and shared resources (e.g. pallets, transport robots, and material handling machines). Non-shared resources are controlled using inner decision loops. However, shared resources require outer decision loops for dispatching and routeing that resolve conflicts, taking into account the specified performance measures to be optimised (e.g. percentage of idle time, throughput, etc.). Failures are simply represented as disturbance inputs, allowing design for failure recovery. The rule-based controller design algorithm is a step-by-step procedure with repeatability and guaranteed conflict/deadlock resolution. It shows that the closed-loop system, once designed, is equivalent to a Petri net (PN); this gives, as a by-product, an algorithm for PN design. Furthermore, the matrix formulation allows a rigorous analysis of deadlocks in terms of circular wait and blocking, and the resources available.