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

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

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

共享竞争择一资源Petri网的形式化设计方法

自动制造系统中有许多共享资源，例如，机器人、数控加工中心、无人导引自动小车等，竞争择一是其共享方式之一。以往，自动制造系统的Ｐｅｔｒｉ网控制系统器设计几乎都是试凑，而且一些性质不能得到满足，如无死锁。这主要是对共享资源的不适当设计造成的。对于多个子系统，为了使之能很好地工作，必须研究一种设计有界、无死锁的Ｐｅｔｒｉ网控制器的方法。本文在以往工作的基础上，提出了有界、无死锁、安全Ｐｅｔｒｉ网控制器…     

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

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

柔性制造系统的改进粒子群无死锁调度算法

基于柔性制造系统的Petri网模型,以制造期最小为优化目标,将死锁避免策略嵌入粒子群算法中,提出一种无死锁改进粒子群调度算法.该算法将粒子与工件的工序序列相对应,以位置数值的大小表示对应工件工序在执行顺序中的优先级.采用一步向前看的死锁避免策略方法对序列的可行性进行验证,提出一种跳出局部极值的策略.实例仿真结果表明了粒子群调度算法的可行性和有效性,以及改进粒子群调度算法的优越性.     

Synthesis a Petri net based control model for a FMS cell

Petri nets have been recognised as a high level formal and graphical specification language for modelling, analysis, and control of concurrent asynchronous distributed systems. This paper presents a PN model, synthesised by an extended version of the knitting synthesis technique. This method, as an incremental design approach, establishes the conditions under which the fundamental behavioural properties of the synthesised systems are fulfilled and preserved. That is, the synthesised models are live, bounded, and reversible (cyclic). A Petri net with the aforementioned properties is called a well-behaved Petri net system which is guaranteed to operate in a deadlock-free, stable, and cyclic fashion. Well-behaved Petri net models, synthesised using the proposed method can be compiled into control codes and implemented as real-time controllers for flexible manufacturing systems. The significance of this paper is due to the application of an extended version of knitting synthesis technique to a real life example of a flexible manufacturing system.     

考虑缓冲区的自动生产单元的无死锁调度策略

在制造系统中,必须防止死锁的发生.本文提出了一种在制造系统(带有有限缓冲区)中搜索最优的无死锁调度的算法.为此首先介绍了死锁问题及其图论表示方法,然后在遗传算法的基础上,运用图论算法来保证无死锁的调度结果.为了保证遗传算法生成的调度策略能够满足所要求的约束,运用图论方法选择无死锁个体,或添加缓冲区,从而在基本保证了系统的主要性能指标的同时,得到系统可行的无死锁调度结果.最后给出了一个运用此方法解决死锁问题的实例.     

Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy

Deadlock-free control and scheduling are vital for optimizing the performance of automated manufacturing systems (AMSs) with shared resources and route flexibility. Based on the Petri net models of AMSs, this paper embeds the optimal deadlock avoidance policy into the genetic algorithm and develops a novel deadlock-free genetic scheduling algorithm for AMSs. A possible solution of the scheduling problem is coded as a chromosome representation that is a permutation with repetition of parts. By using the one-step look-ahead method in the optimal deadlock control policy, the feasibility of a chromosome is checked, and infeasible chromosomes are amended into feasible ones, which can be easily decoded into a feasible deadlock-free schedule. The chromosome representation and polynomial complexity of checking and amending procedures together support the cooperative aspect of genetic search for scheduling problems strongly.     

Deadlock-free Supervisor Design for Robotic Manufacturing Cells With Uncontrollable and Unobservable Events

In this paper, a deadlock prevention policy for robotic manufacturing cells with uncontrollable and unobservable events is proposed based on a Petri net formalism. First, a Petri net for the deadlock control of such systems is defined. Its admissible markings and first-met inadmissible markings (FIMs) are introduced. Next, place invariants are designed via an integer linear program (ILP) to survive all admissible markings and prohibit all FIMs, keeping the underlying system from reaching deadlocks, livelocks, bad markings, and the markings that may evolve into them by firing uncontrollable transitions. ILP also ensures that the obtained deadlock-free supervisor does not observe any unobservable transition. In addition, the supervisor is guaranteed to be admissible and structurally minimal in terms of both control places and added arcs. The condition under which the supervisor is maximally permissive in behavior is given. Finally, experimental results with the proposed method and existing ones are given to show its effectiveness.      

Matrix approach to deadlock-free dispatching in multi-class finite buffer flowlines

For finite-buffer manufacturing systems, the major stability issue is "deadlock," rather than "bounded-buffer-length stability." The paper introduces the concept of "system deadlock," defined rigorously in Petri net terms, and system operation with uninterrupted part-flow is characterized in terms of the absence of this condition. For a large class of finite-buffer multiclass re-entrant flowline systems, an analysis of "circular waits" yields necessary and sufficient conditions for the occurrence of "system deadlock." This allows the formulation of a maximally permissive one-step-look-ahead deadlock-avoidance control policy for dispatching jobs, while maximizing the percent utilization of resources. The result is a generalized kanban dispatching strategy, which is more general than the standard multiclass last buffer first serve (LBFS) dispatching strategies for finite buffer flowlines that typically under-utilize the resources. The problem of computational complexity associated with Petri net (PN) applications is overcome by using certain sub-matrices of the PN incidence matrix. Computationally efficient matrix techniques are given for implementing the deadlock-free dispatching policy.     

Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets

Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times.     

基于平行Petri网的制造系统调度与控制一体化方法

为了消除制造系统调度层与控制层之间的隔阂,实现对生产事件快速灵活响应,本文提出了一种调度与控制一体化的方法.首先,定义了一种新型Petri网模型,即平行Petri网,从而集成地描述了传感器、执行器、任务和资源信息,构建制造系统的信息物理系统模型;其次,提出了一种从平行Petri网到赋时Petri网的抽象简化方法,大规模压缩优化调度所需搜索的状态空间;再次,定义了策略Petri网以描述最优调度策略.最后,给出了平行Petri网与策略Petri网同步执行算法,使得平行Petri网与物理系统同步执行.     

Robust manufacturing system design using multi objective genetic algorithms,Petri nets and Bayesian uncertainty representation

Decisions involving robust manufacturing system configuration design are often costly and involve long term allocation of resources. These decisions typically remain fixed for future planning horizons and failure to design a robust manufacturing system configuration can lead to high production and inventory costs, and lost sales costs. The designers need to find optimal design configurations by evaluating multiple decision variables (such as makespan and WIP) and considering different forms of manufacturing uncertainties (such as uncertainties in processing times and product demand). This paper presents a novel approach using multi objective genetic algorithms (GA), Petri nets and Bayesian model averaging (BMA) for robust design of manufacturing systems. The proposed approach is demonstrated on a manufacturing system configuration design problem to find optimal number of machines in different manufacturing cells for a manufacturing system producing multiple products. The objective function aims at minimizing makespan, mean WIP and number of machines, while considering uncertainties in processing times, equipment failure and repairs, and product demand. The integrated multi objective GA and Petri net based modeling framework coupled with Bayesian methods of uncertainty representation provides a single tool to design, analyze and simulate candidate models while considering distribution model and parameter uncertainties.     

柔性制造系统中生产调度问题的零压缩二叉决策图算法

针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.     

A Petri net-based particle swarm optimization approach for scheduling deadlock-prone flexible manufacturing systems

This paper proposes an effective hybrid particle swarm optimization (HPSO) algorithm to solve the deadlock-free scheduling problem of flexible manufacturing systems (FMSs) that are characterized with lot sizes, resource capacities, and routing flexibility. Based on the timed Petri net model of FMS, a random-key based solution representation is designed to encode the routing and sequencing information of a schedule into one particle. For the existence of deadlocks, most of the particles cannot be directly decoded to a feasible schedule. Therefore, a deadlock controller is applied in the decoding scheme to amend deadlock-prone schedules into feasible ones. Moreover, two improvement strategies, the particle normalization and the simulated annealing based local search, are designed and incorporated into particle swarm optimization algorithm to enhance the searching ability. The proposed HPSO is tested on a set of FMS examples, showing its superiority over existing algorithms in terms of both solution quality and robustness.     

串行加工系统Petri网控制器的形式化设计方法

提出了串行加工系统控制描述规格说明的设计方法,研究了规格说明的Petri网语 义.提出了系统Petri网控制器具有活性等希望性质的初始标识的确定算法.这样的Petri网 控制器经编译或算法转换可直接对系统进行实时控制.     

基于混合整数规划的一般Petri网死锁检测方法

信标的受控性是检测柔性制造系统(flexible manufacturing system,FMS)Petri网模型是否存在死锁的关键因素.对于普通Petri网,在任何可达标识下所有信标不被清空是检测网系统非死锁的充分条件.然而,该条件对于建模能力更强的一般Petri网并不适用,max可控性条件由此产生.研究证明,该条件对于一般Petri网的死锁检测过于严格了.虽然其后有很多研究者通过改进max可控性条件以求给出条件更宽松的一般Petri网非死锁的充分条件,但大部分的研究成果都仅仅局限于一种顺序资源共享分配系统Petri网模型S4PR(systems of sequential systems with shared resources)网.因此,本文在max可控性条件的基础上提出了新的名为max#可控的信标可控性条件,并在此条件的基础上实现了基于混合整数规划(mixed integer programming,MIP)的死锁检测方法.与现有研究成果相比,max#可控性条件更宽松,可适用于更多类型的一般网,为解决大规模柔性制造系统中死锁监督控制器的结构复杂性问题提供了有力的理论支撑.     

A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems

In this paper a divide-and-conquer-method for the synthesis of liveness enforcing supervisors (LES) for flexible manufacturing systems (FMS) is proposed. Given the Petri net model (PNM) of an FMS prone to deadlocks, it aims to synthesize a live controlled Petri net system. For complex systems, the use of reachability graph (RG) based deadlock prevention methods is a challenging problem, as the RG of a PNM easily becomes unmanageable. To obtain the LESs from a large PNM is usually intractable. In this paper, to ease this problem the PNM of a system is divided into small connected subnets. Each connected subnet prone to deadlocks is then used to compute the LES for the original PNM. Starting from the simplest subnet prone to deadlocks to make the subnet live, monitors (control places) are computed. The RG of each subnet is considered and split into a dead-zone (DZ) and a live-zone. All states in the DZ are prevented from being reached by means of a well-established invariant-based control method. Next, the computation of monitors is followed for bigger subnets. Previously computed monitors are included within the bigger subnets based on a criterion. This process keeps the DZ of the bigger subnets smaller compared with the original uncontrolled subnets. When all subnets are live we obtain a set of monitors that are included within the PNM to obtain a partially controlled PNM (pCPNM). A new set of monitors is also computed for the pCPNM. Finally, a live controlled Petri net system is obtained. The proposed method is generally applicable, easy to use, effective and straightforward although its off-line computation is of exponential complexity in theory. Its use for FMS control guarantees deadlock-free operation and high performance in terms of resource utilization and system throughput. Two FMS deadlock problems from the literature are used to illustrate the applicability and the effectiveness of the proposed method.     

An Iterative Synthesis Approach to Petri Net-Based Deadlock Prevention Policy for Flexible Manufacturing Systems

This paper proposes an iterative synthesis approach to Petri net (PN)-based deadlock prevention policy for flexible manufacturing systems (FMS). Given the PN model (PNM) of an FMS prone to deadlock, the goal is to synthesize a live controlled PNM. Its use for FMS control guarantees its deadlock-free operation and high performance in terms of resource utilization and system throughput. The proposed method is an iterative approach. At each iteration, a first-met bad marking is singled out from the reachability graph of a given PNM. The objective is to prevent this marking from being reached via a place invariant of the PN. A well-established invariant-based control method is used to derive a control place. This process is carried out until the net model becomes live. The proposed method is generally applicable, easy to use, effective, and straightforward although its off-line computation is of exponential complexity. Two FMS are used to show its effectiveness and applicability     

离散制造装配系统的活性控制

首次研究离散制造装配系统的活性控制问题.建立了系统的工件加工过程Petri网 模型.通过对系统Petri网模型的结构分析,提出了导致系统死锁的两类元素结构及活性特 征.对一类离散制造装配系统提出了避免死锁的Petri网控制器,这类控制器容易实现,对系 统的限制小,而且使得受控系统仍具Petri网模型.对一般离散制造装配系统提出了保证系统 活性的控制策略.