Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles.

An automated manufacturing system (AMS) contains a number of versatile machines (or workstations), buffers, an automated material handling system (MHS), and is computer-controlled. An effective and flexible alternative for implementing MHS is to use automated guided vehicle (AGV) system. The deadlock issue in AMS is very important in its operation and has extensively been studied. The deadlock problems were separately treated for parts in production and transportation and many techniques were developed for each problem. However, such treatment does not take the advantage of the flexibility offered by multiple AGVs. In general, it is intractable to obtain maximally permissive control policy for either problem. Instead, this paper investigates these two problems in an integrated way. First we model an AGV system and part processing processes by resource-oriented Petri nets, respectively. Then the two models are integrated by using macro transitions. Based on the combined model, a novel control policy for deadlock avoidance is proposed. It is shown to be maximally permissive with computational complexity of O (n2) where n is the number of machines in AMS if the complexity for controlling the part transportation by AGVs is not considered. Thus, the complexity of deadlock avoidance for the whole system is bounded by the complexity in controlling the AGV system. An illustrative example shows its application and power.     

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     

Deadlock Resolution in Automated Manufacturing Systems With Robots

An automated manufacturing system (AMS) contains a number of versatile machines (or workstations), buffers, and an automated material handling system (MHS). The MHS can be an automated guide vehicle (AGV) system, and/or a system that consists of multiple robots. Deadlock resolution in AMS is an important issue. For the AMS with an AGV system as MHS, the problems of deadlock resolution for part processing process and AGV system as an integrated system has been studied. It is shown that AGVs can serve as both material handling devices and central buffers at the same time to help resolve deadlocks. For AMS with robots as MHS, the existing work treated the robots just as material handling devices and showed that the robots had contribution to deadlock. In this paper, such AMS is modeled by resource-oriented Petri nets. Contrary to the existing work, it is shown that the robots have no contribution to deadlock by adopting such nets to control AMS. More interestingly, they can be used to resolve deadlock by serving as temporary part storage devices. A new deadlock control policy is proposed by treating robots as both material handling devices and buffers. The new policy outperforms the existing ones.     

Deadlock and Blockage Control of Automated Manufacturing Systems with an Unreliable Resource

This work studies the deadlock and blockage control problem of an automated manufacturing system (AMS) with a single unreliable resource. It aims to develop a robust control policy to ensure that AMS can produce all parts in the absence of resource failures, and when the unreliable resource fails, the system can continuously produce all parts that do not require the failed resource. To this end, we divide the system into two regions, continuous and non‐continuous, based on whether all parts in them can be produced continuously or not. For the non‐continuous region, dominating region constraints are established to ensure that all parts in it do not block the production of parts in the continuous region, and an optimal deadlock avoidance policy based on a Petri net model is introduced to guarantee its deadlock‐free operation. For the continuous region, we configure a resource order policy to ensure the smooth productions of AMS. By integrating the dominating region constraints and deadlock avoidance policy with the configured resource order policy, we propose a novel robust control policy. It is proven to be of polynomial complexity and more permissive than the existing one with the same resource order policy. Also, it is tested to be more permissive than other existing policies.     

Combined Siphon and Marking Generation for Deadlock Prevention in Petri Nets

In Petri-net (PN) modeling of flexible manufacturing systems, deadlock prevention is often addressed by means of siphon-control methods. Constraints that avoid the emptying of siphons can be easily implemented using additional places suitably connected to the PN transitions. Efficient siphon-based techniques achieve highly permissive solutions using as few control places as possible. One such technique employs a set-covering approach to optimally match emptiable siphons to critical markings. In this paper, a modified version of the method is proposed that achieves the same results in terms of permissivity and size of the control subnet but avoids full siphon enumeration. This greatly reduces the overall computational time and memory requirements and allows the applicability of the method to large-size models.     

具有多品种晶圆混合加工的单臂组合设备调度

为了提高晶圆制造中组合设备的生产效率,在考虑晶圆驻留时间约束条件下,研究没有共享加工模块的多品种晶圆混合加工的单臂组合设备调度问题.首先,采用面向资源的Petri网模型描述多种晶圆产品的混合加工过程,引入控制变迁避免模型的死锁,采用赋时库所和赋时变迁模拟系统资源的活动时间.其次,通过虚拟加工的方法平衡工序的负载,基于系统Petri网模型和拉式调度策略,推导出单臂组合设备在多品种晶圆混合加工情形下的可调度性判定条件,并以解析形式描述.最后,提出了系统稳态调度求解算法并以实例验证了算法的有效性和可行性.     

Comparing digraph and Petri net approaches to deadlock avoidance inFMS

Flexible manufacturing systems (FMSs) are modern production facilities with easy adaptability to variable production plans and goals. These systems may exhibit deadlock situations occurring when a circular wait arises because each piece in a set requires a resource currently held by another job in the same set. Several authors have proposed different policies to control resource allocation in order to avoid deadlock problems. These approaches are mainly based on some formal models of manufacturing systems, such as Petri nets (PNs), directed graphs, etc. Since they describe various peculiarities of the FMS operation in a modular and systematic way, PNs are the most extensively used tool to model such systems. On the other hand, digraphs are more synthetic than PNs because their vertices are just the system resources. So, digraphs describe the interactions between jobs and resources only, while neglecting other details on the system operation. The aim of this paper is to show the tight connections between the two approaches to the deadlock problem, by proposing a unitary framework that links graph-theoretic and PN models and results. In this context, we establish a direct correspondence between the structural elements of the PN (empty siphons) and those of the digraphs (maximal-weight zero-outdegree strong components) characterizing a deadlock occurrence. The paper also shows that the avoidance policies derived from digraphs can be implemented by controlled PNs.     

自动化仓库输送调度问题的建模与控制研究

基于面向对象着色Petri网模型和时态逻辑方法,对自动化仓库输送系统运行过程的调度问题进行研究。建立了系统的面向对象着色Petri网模型,讨论了该过程的死锁分析问题,给出了系统行为的时态逻辑规范和死锁避免的最大允许反馈控制策略。     

Robust supervision using shared-buffers in automated manufacturing systems with unreliable resources

It has been an active area of research to solve the modeling, analysis, and deadlock control problems for automated manufacturing systems (AMSs). So far, all the system resources are assumed to be reliable in most of the existing approaches for deadlock-free and nonblocking supervisory control. However, many resources of AMSs are subject to failure in the real world. In order to develop a more practical and applicable supervisor, this work takes into consideration of multiple unreliable resources in a class of AMSs. On the basis of two variants of Banker’s Algorithm, this paper presents a robust supervisory control policy to avoid deadlock and blocking in these systems. The policy tries to make the best use of buffers of the shared resources to achieve the control objectives. Our controller is qualified to handle simultaneous multi-resource failures. By using formal language and automata theory, we establish its correctness. Moreover, our proposed method is verified via an AMS example, and we make comparison studies between our policy and some of the other similar type of policies in the literature.     

Development of VHDL‐AMS neuro‐fuzzy behavioral models for RF/microwave passive components

The new generation of System‐on‐Chip (SoC) incorporates digital, analogue, RF/microwave and mixed‐signal components. Such circuits impose to reconsider the traditional design methods. Mixed‐signal designers need novel design methodologies which will have to include accurate behavioral libraries of devices and processes into hierarchical design flows. Thus, this paper describes a behavioral modeling approach which generates neuro‐fuzzy‐based models for RF/microwave devices. The models, so obtained, can be easily integrated into a VHDL‐AMS simulator. This modeling approach is applied to a microwave tunable phase shifter and it is illustrated by the development of a VHDL‐AMS model library for RF/microwave applications. © 2007 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2007.     

Deadlock avoidance policy for Petri-net modeling of flexiblemanufacturing systems with shared resources

Multiple products through a flexible manufacturing system (FMS) with limited resources can lead to deadlock. In this paper, the authors study the problem of deadlock avoidance by using the Petri net (PN) model for FMSs and introducing the concept of deadlock structure. The necessary and sufficient conditions to prevent deadlock are characterized. The authors use a state feedback restriction policy which prevents some enabled transitions from firing for avoiding deadlock in the system. In particular, when the number of any key kind of resources is greater than one, this policy is minimally restrictive and allows the maximal use of resources in the system. The authors present the PN realization of these restriction policies when the closed-loop system can be modeled by a live PN. The restriction policies can be easily implemented. An example is provided for illustration     

Programmable‐logical‐controllers Synthesis for Automated‐guided‐vehicle Systems Using Ordinary Petri Nets

An ordinary Petri‐net (PN) based approach is proposed to design the programmable logical controller (PLC) for preventing collisions between vehicles in an automated guided vehicles (AGV) system. First, method is proposed to model an AGV system as an ordinary PN, called the plant PN. Second, for collision prevention in an AGV system, module control methods are proposed to design the PN supervisor (the closed‐loop PN) by augmenting the plant PN. In detail, three modules are defined the line, divide, and merge modules, in the plant PN, and the control module methods are presented for each of these three modules. As a result, the closed‐loop PN of an AGV system is obtained and can be analyzed using the PN theory. Finally, method is proposed to translate a closed‐loop PN into a ladder diagram. Consequently, the PN supervisor is implemented by a PLC using these proposed methods. A laboratory AGV system is used to illustrate this approach.     

Fault-tolerant deadlock avoidance algorithm for assembly processes

Unreliable resources pose challenges in design of deadlock avoidance algorithms as resources failures have negative impacts on scheduled production activities and may bring the system to dead states or deadlocks. This paper focuses on the development of a suboptimal polynomial complexity deadlock avoidance algorithm that can operate in the presence of unreliable resources for assembly processes. We formulate a fault-tolerant deadlock avoidance controller synthesis problem for assembly processes based on controlled assembly Petri net (CAPN), a class of Petri nets (PNs) that can model such characteristics as multiple resources and subassembly parts requirement in assembly production processes. The proposed fault-tolerant deadlock avoidance algorithm consists of a nominal algorithm to avoid deadlocks for nominal system state and an exception handling algorithm to deal with resources failures. We analyze the fault-tolerant property of the nominal deadlock avoidance algorithm based on resource unavailability models. Resource unavailability is modeled as loss of tokens in nominal Petri Net models to model unavailability of resources in the course of time-consuming recovery procedures. We define three types of token loss to model 1) resource failures in a single operation, 2) resource failures in multiple operations of a production process and 3) resource failures in multiple operations of multiple production processes. For each type of token loss, we establish sufficient conditions that guarantee the liveness of a CAPN after some tokens are removed. An algorithm is proposed to conduct feasibility analysis by searching for recovery control sequences and to keep as many types of production processes as possible continue production so that the impacts on existing production activities can be reduced.     

Deadlock resolution strategy for automated manufacturing systems including conjunctive resource service

Automated manufacturing systems (AMSs) can process different parts according to operation sequences sharing a finite number of resources. In these systems, deadlock situations can occur so that the flow of parts is permanently inhibited, and the processing of jobs is partially or completely blocked. Hence, one of the tasks of the control system is ruling resource allocation to prevent such situations from occurring. A large part of the existing literature focused on systems in which every operation is performed by only one resource. This paper proposes a deadlock strategy to avoid deadlock conditions in more complex systems where multiple resource acquisitions are allowed to complete a working operation conjunctive resource service system (CRSS). The AMS structure and dynamics is described by a colored timed Petri net model, suitable for following resource changes and working procedure updating. Moreover, digraphs characterize the complex interactions between resources and jobs so that the conditions for the deadlock occurrence are derived. Finally, an event-based controller is defined to avoid deadlock in CRSSs on the basis of the system state knowledge and of the given priority law ruling the concurrent job selection.     

柔性制造系统中死锁避免的充要条件第二部分：资源的动态分配规则

本文根据在第一部分中推导出来的描述资源竞争的着色ＲＯＰＮ给出在柔性制造系统中无死锁运行的充分必要条件，从而得出相应的控制规律。它是一种资源动态分配的策略，它决定当一个资源空闲时，是否可以分配给一个任务，可以的话先分配给谁，以保证系统无死锁，并使得资源利用率最大。     

Process modeling and analysis of manufacturing supply chain networks using object-oriented Petri nets

This paper presents a systematic methodology for modeling and analysis of manufacturing supply chain business processes. The proposed approach first employs Computer Integrated Manufacturing Open System Architecture (CIMOSA) behavior rules to model the business process routing structures of manufacturing supply chain networks. Object-oriented predicate/transition nets (OPTNs) are then developed for the modular modeling and analysis of process models. Based on the structure of OPTNs, a procedure to obtain the system's P-invariants through objects’ P-invariants is suggested. From the P-invariants obtained, system structural properties such as deadlock and overflow can be analyzed. By using Petri net unfolding techniques and by extracting the process model of each object from the entire process model, the sequencing analysis for operations in supply chain processes becomes possible. Several manufacturing supply chain examples are used to illustrate the effectiveness of the proposed method.     

一种验证Web服务流程的新方法*

在实际的服务组合中,Web服务流程（process）的验证(verification)对于Web服务的组合实现和应用具有重要意义——通过验证可以证明一个组合服务的控制流满足某个重要或者期望的属性,如不包含死锁或不包含无限循环,诸如此类;而服务提供者可对Web服务流程进行验证,以确保所提供的Web服务是完全正确的。然而,针对这两种语言的验证方法较少被人们注意。提出一种验证Web服务流程的方法,该方法使用时序行为逻辑（TLA）建模服务流程,然后,利用模型检验（model checking）技术验证模型的某些属     

Unraveling Iterative Control Structures from Business Processes

Iterative control structures allow the repeated execution of tasks,activities or sub-processes according to the given conditions in a process model.Iterative control structures can significantly increase the risk of triggering temporal exceptions since activities within the scope of these control structures could be repeatedly executed until a predefined condition is met.In this paper,we propose two approaches to unravel iterative control structures from process models.The first approach unravels loops based on zero-one principle.The second approach unravels loops based on branching probabilities assigned at split gateways.The proposed methods can be used to unfold structured loops,nested loops and crossing loops.Since the unfolded model does not contain any iterative control structures,it can be used for further analysis by process designers during the modeling phase.The proposed methods are implemented based on workflow graphs,and therefore they are compatible with modeling languages such as Business Process Modelling Notation(BPMN).In the experiments,the execution behavior of unfolded process models is compared against the original models based on the concept of runs.Experimental results reveal that runs generated from the original models can be correctly executed in the unfolded BPMN models that do not contain any loops.     

A deadlock prevention approach for flexible manufacturing systems with uncontrollable transitions in their Petri net models

Deadlocks are a highly undesired situation in a fully automated flexible manufacturing system, whose occurrences are tied to the existence of shared resources that are competed by different production processes. In the last two decades, a fair amount of research has been done on deadlock analysis and control for flexible manufacturing systems, leading to a variety of strategies in the literature. Petri nets are a promising mathematical tool to handle deadlock problems in flexible manufacturing systems. However, most deadlock control policies based on a Petri net formalism assume that all the transitions in a plant model are controllable. However, uncontrollability of events are a natural feature in a real‐world production system. This paper proposes a deadlock prevention policy for a class of Petri nets by considering the existence of uncontrollable transitions. Deadlocks are prevented by adding monitors to a plant Petri net model, whose addition does not inhibit the firings of uncontrollable transitions. Linear programming techniques are employed to find transitions to which a monitor points in order that a more permissive liveness‐enforcing Petri net supervisor can be found. A number of manufacturing examples are used to demonstrate the proposed methods. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Application of Deadlock Risk Evaluation of Architectural Models

Software architectural evaluation is a key discipline used to identify, at early stages of a real‐time system (RTS) development, the problems that may arise during its operation. Typical mechanisms supporting concurrency, such as semaphores, mutexes or monitors, usually lead to concurrency problems in execution time that are difficult to be identified, reproduced and solved. For this reason, it is crucial to understand the root causes of these problems and to provide support to identify and mitigate them at early stages of the system lifecycle. This paper aims to present the results of a research work oriented to the development of the tool called ‘Deadlock Risk Evaluation of Architectural Models’ (DREAM) to assess deadlock risk in architectural models of an RTS. A particular architectural style, Pipelines of Processes in Object‐Oriented Architectures–UML (PPOOA) was used to represent platform‐independent models of an RTS architecture supported by the PPOOA –Visio tool. We validated the technique presented here by using several case studies related to RTS development and comparing our results with those from other deadlock detection approaches, supported by different tools. Here we present two of these case studies, one related to avionics and the other to planetary exploration robotics. Copyright © 2011 John Wiley & Sons, Ltd.