应用控制变迁的柔性制造系统死锁控制策略

不同于目前许多文献中基于添加控制库所的死锁预防策略,本文提出了控制变迁方程(CTE)的概念和相应的基于添加控制变迁(CT)的死锁控制策略(DCP).通过分析存在死锁的原网(N0, M0)的可达图(RG),该DCP求解出所有死锁标识(DM).基于CTE,构造出所需的控制变迁.然后,对每个DM添加相应的CT,进而消除了原网(N_0, M_0)中的死锁标识,得到了活性受控网系统(N~?, M~?).通过理论分析和相关算例的应用,该DCP的正确性和有效性得到了验证.此外,该DCP获取的活性受控网系统(N~?, M~?)可达数目与原网(N_0, M_0)是相同的,即最大可达数(MRN).     

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

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

基于Petri网模型的FMS死锁结构

死锁是柔性制造系统中容易发生的异常现象,如不加以消除,将会导致整个系统的瘫痪.文中通过Petri网模型对FMS的结构分析,揭示出导致FMS死锁的结构元素和活性特征,在此基础上,提出了FMS的无死锁Petri网控制器算法,并举例说明这种控制器算法在FMS中的应用.     

柔性制造系统中多路径条件下的死锁避免第二部分:控制策略

在第一部分推导出的面向资源的着色Ｐｅｔｒｉ的基础上讨论ＦＭＳ中多路径条件下的死锁避免控制策略问题，给出了无死锁运行的充要条件及其相应的控制策略。     

避免FMS死锁的控制策略

本文利用ＦＭＳ的Ｐｅｔｒｉ网模型讨论系统的死锁问题，给出了系统死锁的必要充分条件，提出了避免系统死锁的反馈控制策略，这种策略对系统的限制小，在许多情形下是最优的。     

基于Petri网模型的FMS死锁结构

死锁是柔性制造系统中容易发生的异常现象，如不加以消除，将会导致整个系统的瘫痪。文中通过Petri网模型对FMS的结构分析，揭示出导致FMS死锁的结构元素和活性特征，在此基础上，提出了FMS的无死锁Petri网控制器算法，并举例说明这种控制器算法在FMS中的应用。     

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

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

柔性制造系统中多路径条件下的死锁避免 第一部分:系统建模

路径选择柔性是柔性制造系统的重要特性，但它使系统的调度和控制复杂化．从避免死锁这一重要要求出发，讨论了多路径条件下系统的建模．给出了一种称之为面向资源的着色Ｐｅｔｒｉ网（ＣＲＯＰＮ），它不仅能很好地描述系统中的动态资源竞争，而且能准确地描述系统中的工件流．利用这一模型，将获得避免死锁的充要条件．     

具有多项式时间复杂性的避免制造系统死锁控制策略

基于系统 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.     

Synthesis of deadlock prevention policy using Petri nets reachability graph technique

This paper proposes a subclass of generalized stochastic Petri net (GSPN) model, called TS³PR, which is modified the systems of simple sequential processes with resources (S³PR) with timed information. Based on the subclass of GSPN, a new deadlock prevention policy is developed by using reachability graph technique. The foundation of the new control policy is to manipulate all the dead states of the system nets. This study is able to change dead states into vanishing ones by additional immediate transitions. A live TS³PR model can then be obtained. It is worthwhile to notice that this study is different from adding additional control place policies in previous literature. Experimental results, indicate that our new control policy is with maximally permissive markings than conventional place‐control ones. As a result, we can infer that our proposed control policy seems to be used in Petri nets deadlocked systems. To our knowledge, this is the first work that employs the additional transitions to obtain the deadlock prevention policy. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

自动制造系统的稳健控制方法的综述

随着科学技术的快速发展,制造自动化在制造工厂已经成为一个主流方向.在过去的几十年中,研究人员已经对自动制造系统的死锁问题做了大量的研究.但是大多数解决方案总是假设分配的资源不会故障.然而,任何一个制造研究者都知道,资源故障来自各种各样的原因,包括工件破损、传感器故障、零件缺失和电器失灵等.显然,一旦资源发生故障,后续加工路径中需要使用这个故障资源的进程将停滞,不能完成其加工生产,直到故障资源被修复.那些不使用故障资源的支路也会被发生停滞的进程所阻塞.最坏的情况就是一个简单的资源故障可能会导致整个系统的崩溃.因此,制造系统中的资源故障问题急需解决.通过分析大量的文献资料,本文对解决死锁和阻塞问题的控制方法做了系统的总结研究.同时,对本文提出的稳健无死锁控制策略以及亟待开展的研究工作做了详细的介绍.     

A deadlock prevention approach for a class of timed Petri nets using elementary siphons

To solve the problem of deadlock prevention for timed Petri nets, an effective deadlock prevention policy based on elementary siphons is proposed in this paper. Without enumerating reachable markings, deadlock prevention is achieved by adding monitors for elementary siphons, increasing control depth variables when necessary, and removing implicit, liveness‐restricted and redundant control places. The final supervisor is live. First, a timed Petri net is stretched into a stretched Petri net (SPN). Unchanging the system performance, each transition in the SPN has a unit delay time. Then the siphon‐control‐based approach is applied. Monitors computed according to the marking constraints are added to the SPN model to ensure all strict minimal siphons in the net invariant‐controlled. A liveness‐enforcing supervisor with simple structure can be obtained by reverting the SPN into a TdPN. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Petri net based process scheduling: A model of the control system of flexible manufacturing systems

In this paper, we propose a class of algorithms for the sub-optimal solution of a particular class of problems of process scheduling, particularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, each formed by a number of temporally related tasks (segments). Tasks are executable by alternate resource sets, different both in performance and costs. Processes and tasks are characterized by release times, due dates, and deadlines. Time constraints are also present in the availability of each resource in resource sets. It has been proven that such a problem does not admit an algorithm for an optimal solution in polynomial time. Our proposed algorithm finds a sub-optimal schedule according to a set of optimization criteria, based on task and process times (earliness, tardiness), and/or time independent costs of resources. Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling algorithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) theautomatic synthesis of Petri net models of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose kernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-optimal multi-criteria algorithms. Furthermore, the paper defines the interaction mechanisms between the coordination and scheduling subsystems. Our approach clearly distinguishes the mechanism of the net execution from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: theexecutor and thescheduler levels. One of the outstanding differences between these levels is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distributed component, whose behavior may heavily depend on the problem class. If the scheduler fails, the executor is, in any case, able to proceed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.     

A comparative performance analysis of deadlock avoidance control algorithms for FMS

A deadlock condition for flexible manufacturing systems is characterized by a set of parts, which have been processed but cannot be discharged by a set of machines or buffers. To avoid such problems, it is necessary to adopt suitable control policies which limit the resource allocation in the system, thus affecting the overall system performance. In the present work, we address the problem of evaluating and comparing the performance of deadlock avoidance control policies applied to FMS. The problem is discussed for both untimed and timed models, and for models both with and without deadlock avoidance control policies. Different control algorithms, among the most common in the literature, have been considered. Imperfect deadlock avoidance control policies are also considered. In addition, some indices are proposed to assess the structural properties of FMS with respect to deadlock occurrence and their performance. Two different application examples are analyzed, with the help of a commercial simulation package. Finally, an adaptive algorithm which can learn from system evolution to avoid deadlocks is illustrated.     

基于Petri网的柔性制造系统无死锁遗传调度算法

对以最小化加工时间为目标的柔性制造系统无死锁调度问题, 提出了一种遗传调度算法. 算法考虑到同类工件具有预先确定的相同加工路径, 而各工序的处理时间与工件有关. 用Petri网对工序和资源分配进行逻辑建模,利用遗传算法, 采用工序自然编码方式, 基于系统的最佳避免死锁Petri网控制器, 检测染色体的可行性, 修复不可行染色体使其对应的调度满足资源约束和无死锁控制约束, 从而保证算法所利用的所有染色体都对应系统的可行调度. 仿真结果表明了算法的可行性和有效性.     

A best deadlock control for S3PMR to reach all states

This study proposes a new approach that recovers the system from deadlock states to its former live states, and reaches the same number of states as the original uncontrolled model by adding monitors (and control arcs) with no new problematic siphons. We further propose a lossless approach by coloring some arcs to avoid the material loss. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society