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.     

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.     

Robust Deadlock Avoidance Policy for Automated Manufacturing System With Multiple Unreliable Resources

This work studies the robust deadlock control of automated manufacturing systems with multiple unreliable resources. Our goal is to ensure the continuous production of the jobs that only require reliable resources. To reach this goal, we propose a new modified Banker's algorithm(MBA) to ensure that all resources required by these jobs can be freed. Moreover,a Petri net based deadlock avoidance policy(DAP) is introduced to ensure that all jobs remaining in the system after executing the new MBA can complete their processing smoothly when their required unreliable resources are operational. The new MBA together with the DAP forms a new DAP that is robust to the failures of unreliable resources. Owing to the high permissiveness of the new MBA and the optimality of the DAP, it is tested to be more permissive than state-of-the-art control policies.     

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.     

Generalized Algebraic Deadlock Avoidance Policies for Sequential Resource Allocation Systems

Currently, one of the most actively researched approaches regarding the design of deadlock avoidance policies for sequential resource allocation systems is based on concepts and techniques provided by the, so called, theory of regions, that addresses the broader problem of synthesizing PN models with prespecified behaviors. However, one limitation of the theory of regions and its aforementioned derivatives is that they cannot be applied when the target behavior has a nonconvex representation in the underlying state space. In this note, we show how this problem can be circumvented by appropriately generalizing the employed class of the candidate policies.     

New Controllability Condition for Siphons in Ws3PR Nets

Existing policies for deadlock control are mainly based on siphons due to their ability to indicate deadlocks, and can be used as a powerful tool to deal with deadlock situations in flexible manufacturing systems. In order to avoid deadlocks, researchers often add monitors to control siphons. This may result in redundant monitors, unnecessary cost, and restriction of the behavior permissiveness. For example, for a system of sequential systems with shared resources (S⁴R), the existing deadlock control policies based on max, max′ or max′′‐controlled siphons tend to overly restrict the behavior of a controlled system. To ensure maximal permissive behavior of controlled systems, a new concept of siphon controllability named W‐control is defined and then a sufficient and necessary condition under which a WS³PR is live if all its siphons are W‐controlled. Examples are given to demonstrate them.     

On Siphon Computation for Deadlock Control in a Class of Petri Nets

As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.     

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-net-based robust supervisory control of automated manufacturing systems

Supervisory control that ensures deadlock-free and nonblocking operation has been an active research area of manufacturing engineering. So far, most of deadlock control policies in the existing literature assume that allocated resources are reliable. Additionally, a large number of methods are for systems of simple sequential processes with resources (S³PRs), where a part uses only one copy of one resource at each processing step. In contrast, we investigate the automated manufacturing systems (AMSs) that can be modeled by a class of Petri nets, namely S^*PUR. S^*PUR is a generalization of the S^*PR Petri net model, while S^*PR is a superclass of S³PR. This work addresses the robust supervision for deadlock avoidance in S^*PUR. Specifically, we take into account unreliable resources that may break down while working or being in idle, and the considered AMSs allow the use of multiple copies of different resources per operation stage. Our objective is to control the system so that: 1) when there are breakdowns, the system can continue producing parts of some types whose production does not need any failed resources; and 2) given the correction of all faults, it is possible to complete all the on-going part instances remaining in the system. We illustrate the characteristics of a desired supervisor through several examples, define the corresponding properties of robustness, and develop a control policy that satisfies such properties.     

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.     

Controller design and performance evaluation for deadlock avoidance in automated flexible manufacturing cells

In this paper, the design of a deadlock avoidance controller is described. The uncontrolled system is modeled using colored Petri nets. The system controller is based on a restrictive (not maximally permissive) deadlock avoidance policy to resolve deadlocks and control the real-time resource allocation decisions in the system. Performance evaluation of systems controlled by not maximally permissive algorithms is essential in determining the applicability and effectiveness of the control algorithms. The performance of the controlled system is compared with performance of optimal control policies to quantify the effects of the restrictiveness of the deadlock avoidance policy on system performance.     

On supervisory policies that enforce liveness in completelycontrolled Petri nets with directed cut-places and cut-transitions

The process of synthesizing a supervisory policy that enforces liveness in a Petri net (PN), where each transition can be prevented from firing by an external agent, can be computationally burdensome in general. We consider PNs that have a directed cut place or a cut-transition. A place (transition) in a connected PN is said to be a cut place (cut-transition) if its removal will result in two disconnected component PNs. A cut place is said to be a directed cut-place, if in the original PN, all arcs into this cut place emanate from transitions in only one of the two disconnected component PNs. The authors show there is a supervisory policy that enforces liveness in the original PN if and only if similar policies exist for two PNs derived from the disconnected components obtained after the removal of the directed cut-place (cut-transition). The utility of this observation in alleviating the computational burden of policy synthesis is illustrated via example     

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     

On the Optimality of Randomized Deadlock Avoidance Policies

This paper revisits the problem of selecting an optimal deadlock resolution strategy, when the selection criterion is the maximization of the system throughput, and the system is Markovian in terms of its timing and routing characteristics. This problem was recently addressed in some of our previous work, that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open in the problem treatment of that past work, was whether the proposed policy randomization is essential, i.e., whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The work presented in this paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput—or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time—randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix. Furthermore, the undertaken analysis provides an analytical characterization of the dependence of the aforementioned performance measures on the transition rates relating to the various events of the underlying state space, which can be useful for the broader problem of synthesizing efficient scheduling policies for the considered class of resource allocation systems.     

Deadlock avoidance schemes in a distributed robotic system: Petri net modeling and analysis

This article presents a Petri net-based approach to modeling and evaluating four different deadlock avoidance schemes for a distributed robotic system, i.e., a five-robot-five-assembly-line system. Among these four schemes are the conventional, full synchronization, global semaphore, and partial synchronization schemes. To explore such issues as the system performance and control structure complexity, this article conducts detailed Petri net modeling for this system and evaluates performance of the deadlock avoidance schemes using stochastic Petri nets. The interesting results presented include that: (1) any possible system deadlock can seriously degrade the system performance even if effective deadlock resolution techniques are available; (2) conservative use of resources is likely to be the best policy; and (3) higher resource utilization may not necessarily imply higher system production rate in a resource-sharing environment. The related results need to be further explored for the larger resource-sharing discrete event systems. © 1995 John Wiley & Sons, Inc.     

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.     

避免FMS死锁的控制策略

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

A deadlock avoidance approach for nonsequential resource allocation systems

The paper concentrates on the deadlock-avoidance problem for a class of resource allocation systems modeling manufacturing systems. In these systems, a set of production orders have to be executed in a concurrent way. To be executed, each step of each production order needs a set of reusable system resources. The competition for the use of these resources can lead to deadlock problems. Many solutions, from different perspectives, can be found in the literature for deadlock-related problems when the production orders have a sequential nature [sequential resource allocation systems (S-RAS)]. However, in the case in which the involved processes have a nonsequential nature [nonsequential resource allocation systems (NS-RAS)], the problem becomes more complex. In this paper, we propose a deadlock avoidance algorithm for this last class of systems. We also show the usefulness of the proposed solution by means of its application to a real system.     

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

基于系统 Petri 网模型, 研究自动制造系统的避免死锁问题. 对不含中心资源的制造系统, 证明了它只包含安全和死锁两类可达状态. 通过一步向前看的方法, 给出了系统多项式时间复杂性的最佳避免死锁策略. 对一般系统定义了一种辅助 Petri 网. 利用辅助网的最佳避免死锁策略, 提出了综合一般制造系统多项式复杂性的避免死锁策略的方法.     

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