Robustness analysis of Petri nets for assembly/disassembly processes with unreliable resources

In most application of Petri nets, resources are modeled as tokens. Unreliable resources pose challenges as existing Petri net theory is deficient in analyzing the impacts of the perturbation due to resource failures. One strategy to analyze a perturbed system is to study its robustness with respect to uncertainties. In this paper, we study the robustness of a class of controlled Petri nets called controlled assembly/disassembly Petri net (CADPN) for assembly/disassembly processes with unreliable resources. The number of tokens in CADPN is not conservative to capture the effects of resource failures. Based on the CADPN model, we characterize different types of tolerable resource failures allowed for a nominal marking of a live CADPN. We show that liveness of a CADPN can still be preserved under tolerable resource failures.     

Analysis of Flexible Assembly Processes Based on Structural Decomposition of Petri Nets

We propose a controlled assembly Petri net with alternative route (CAPN-AR) model for a class of flexible assembly processes with alternative routes and unreliable resources. Alternative routes significantly enhance the reliability through the routing flexibility of the system. It is not required for a CAPN-AR to be live to maintain production. For this reason, we propose the concept of persistent production for the CAPN-AR. However, alternative routes also add complexity to the analysis of the systems. As the PNs grow rapidly with the scale of the problem, an existing reachability-tree method is feasible only for small nets. We propose an analysis method that can scale with the problems based on structural decomposition of the CAPN-AR. We study the conditions for persistent production, propose a deadlock avoidance algorithm with polynomial complexity for CAPN-AR, and access its robustness property with respect to resource failures.     

On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets

A fair amount of research has shown the importance of siphons in the analysis and control of deadlocks in a variety of resource allocation systems by using a Petri net formalism. In this paper, siphons in a generalized Petri net are classified into elementary and dependent ones, as done for ordinary nets in our previous work. Conditions are derived under which a dependent siphon is controlled by properly supervising its elementary siphons, which indicates that the controllability of dependent siphons in an ordinary Petri net is a special case of that in a generalized one. The application of the controllability of dependent siphons is shown by considering the deadlock prevention problem for a class of resource allocation systems, namely, G-system that allows multiple resource acquisitions and flexible routings in a flexible manufacturing system with machining, assembly, and disassembly operations. We develop a monitor-based deadlock prevention policy that first adds monitors for elementary siphons only to a G-system plant model such that the resultant net system satisfies the maximal controlled-siphon property (maximal cs-property). Then, by linear programming, initial tokens in the additional monitors are decided such that liveness is enforced to the supervised system. Also, a simplified live marking relationship for a G-system between the initial tokens of the source places and those of the resource places is derived. Finally, the proposed deadlock prevention methods are illustrated by using an example.     

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.     

容错的分布式系统通用死锁模型检测解除算法

分布式系统技术为采用低成本购建高性能系统提供了有效的途径,但是由于资源的分配与需求可能产生冲突,造成系统中发生死锁,导致系统运行陷入停滞.在不可靠的分布式系统中,故障会干扰正常的死锁检测,但现有的死锁检测算法不具有容错功能.对失效形式进行了归类,提出一个容错的死锁检测解除算法.算法建立在通用的AND-OR模型基础上,采用扩散计算和集中规约方式,不仅能够检测到死锁,而且能给出死锁环的全部成员.若死锁拓扑处于静态且为环状,算法的消息复杂度的上限为e n-1,时间复杂度为d,其中e为死锁等待图中边的个数,n和d为构成死锁环的节点的个数,分析表明算法性能等于或优于同类算法.     

Robustness of deadlock avoidance algorithms for sequential processes

Although deadlock avoidance issue has attracted much attention and has been extensively studied, most of the existing results assume reliable machines. This assumption makes it difficult to apply existing deadlock avoidance algorithms to real manufacturing systems with unreliable machines. This paper presents the results to apply an existing deadlock avoidance algorithm to systems with unreliable machines by analyzing the robustness of the deadlock avoidance algorithm. Sequential production processes are considered in this paper, and Petri Net is adopted as the tool for modeling and analysis of the sequential processes. Different types of tolerable machine failures under which liveness property can be preserved are characterized. Computational complexity of the proposed algorithm is analyzed.     

Robustness analysis of holonic assembly/disassembly processes with Petri nets

Although the concept of holonic manufacturing systems (HMS) has been proposed for over a decade, several desired properties of HMS such as fault tolerance have not been quantitatively characterized and rigorously proven. This paper aims to provide a theoretical foundation for analyzing the fault tolerant properties of holonic assembly/disassembly processes in HMS. Fault tolerant analysis is concerned with the impact of resource failures on the operation and performance of HMS. The goal of fault tolerant analysis is to study the ability to retain the operation of holonic processes in the presence of resource failures. To study fault tolerant properties, we propose a collaborative Petri net (CPN) to model holonic assembly/disassembly processes and formulate an optimization problem to minimize the cost of CPN. We propose a greedy algorithm to find a nominal optimal solution. Based on the nominal solution, we analyze the effects of resource failures on the operation and performance of the holonic assembly/disassembly processes. Computational complexities are also analyzed.     

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.     

Deadlock Models and a General Algorithm for Distributed Deadlock Detection

This paper deals with the problem of deadlock detection in asynchronous message passing systems in a system model that covers unspecified receptions and non-FIFO channels. It presents a hierarchy of deadlock models and deadlock detection problems. It abstracts deadlocks by a general deadlock model that has the same modeling power as the OR-AND model; however, it has much concise expressive power. An abstract general definition of deadlocks in distributed systems is presented that defines deadlocks independently of the underlying deadlock model. This formulation can be used to design a single distributed deadlock detection algorithm which uniformly addresses all deadlocks in the context of various request models such as AND, OR, AND-OR, and k-out-of-n requests. A simple generalized deadlock detection algorithm that uses a circulating token is presented to illustrate the concept. The algorithm is formally described and proven correct. Moreover, possible refinements of the basic solution concerning improvements of token routing and parallel implementation are outlined and evaluated. Extensions to individual and global termination issues are also addressed. Since the proposed deadlock detection algorithm is designed around the abstract definition of deadlocks, it has some very favorable features.     

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.     

Monitor design for colored Petri nets: An application to deadlock prevention in railway networks

In this paper we use colored Petri nets (CPN) to model the dynamics of a railway system: places represent tracks and stations, tokens are trains. Using digraph tools, deadlock situations are characterized and a strategy is established to define off-line a set of constraints that prevent deadlocks. We show that these constraints limit the weighted sum of colored tokens in subsets of places. In particular, we extend the notion of generalized mutual exclusion constraints (GMEC) to CPN and we show that the above constraints, as well as the collision avoidance constraints, can be written as colored GMEC.To solve this problem, we extend the theory of monitor places for place/transition nets to the case of CPN and we show that these constraints can be enforced by a colored monitor place that minimally restricts the behavior of the closed-loop system.     

Petri net modeling and deadlock analysis of parallel manufacturing processes with shared-resources

Multiple resource-sharing is a common situation in parallel and complex manufacturing processes and may lead to deadlock states. To alleviate this issue, this paper presents the method of modeling parallel processing flows, sharing limited number of resources, in flexible manufacturing systems (FMSs). A new class of Petri net called parallel process net with resources (PPNRs) is introduced for modeling such FMSs. PPNRs have the capacity to model the more complex resource-sharing among parallel manufacturing processes. Furthermore, this paper presents the simple diagnostic and remedial procedures for deadlocks in PPNRs. The proposed technique for deadlock detection and recovery is based on transition vectors which have the power of determining the structural aspects as well as the process flow condition in PPNRs. Moreover, the proposed technique for dealing with deadlocks is not a siphon-based thus the large-scale PPNRs for real-life FMSs can be tackled. Finally, the proposed method of modeling and deadlock analysis in the FMS having parallel processing is demonstrated by a practical example.     

Modeling production configuration using nested colored object-oriented Petri-nets with changeable structures

Configuring production processes based on process platforms has been well recognized as an effective means for companies to provide product variety while maintaining mass production efficiency. The production processes of product families involve diverse variations in manufacturing and assembly processes resulted from a large variety of component parts and assemblies. This paper develops a multilevel system of nested colored object-oriented Petri nets with changeable structures to model the configuration of production processes. To capture the semantics associated with production configuration decisions, some unique modeling mechanisms are employed, including colored Petri nets, object-oriented Petri nets, changeable Petri net structures, and net nesting. The modeling formalism comprises resource nets, manufacturing nets, assembly nets and process nets. The paper demonstrates how these net definitions are applied to the specification of production process variants at different levels of abstraction. Also reported is a case study in an electronics company. The system model is further analyzed with focus on conflict prevention and deadlock detection.     

具有不可靠资源柔性制造系统的鲁棒控制器设计

如果柔性制造系统包含不可靠资源,则在对系统进行控制器设计时,不仅要考虑由于资源分配不合理带来的死锁现象,还要考虑不可靠资源发生损坏带来的堵塞现象.对此,首先利用Petri网对具有不可靠资源的柔性制造系统进行建模,结合Petri网图形结构(资源变迁回路),模拟系统中的死锁和堵塞现象;然后,利用有效变迁覆盖的概念,为系统设计一种结构简单、鲁棒性强的Petri网控制器;最后,利用两个例子验证所设计控制器的有效性.     

An efficient deadlock prevention approach for service oriented transaction processing

Transaction processing can guarantee the reliability of business applications. Locking resources is widely used in distributed transaction management (e.g., two phase commit, 2PC) to keep the system consistent. The locking mechanism, however, potentially results in various deadlocks. In service oriented architecture (SOA), the deadlock problem becomes even worse because multiple (sub)transactions try to lock shared resources in the unexpectable way due to the more randomicity of transaction requests, which has not been solved by existing research results. In this paper, we investigate how to prevent local deadlocks, caused by the resource competition among multiple sub-transactions of a global transaction, and global deadlocks from the competition among different global transactions. We propose a replication based approach to avoid the local deadlocks, and a timestamp based approach to significantly mitigate the global deadlocks. A general algorithm is designed for both local and global deadlock prevention. The experimental results demonstrate the effectiveness and efficiency of our deadlock prevention approach. Further, it is also proved that our approach provides higher system performance than traditional resource allocation schemes.     

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.     

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resourcetransition circuits and their saturated states. The concept facilities the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reach their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For an general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resource-transition circuits and their saturated states. The concept facilitates the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reaching their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For a general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

分布式系统死锁的预防、避免和检测

分布式系统涉及到资源和数据的高度共享,从而可能引发死锁。分布式系统的死锁是由于资源和通讯产生的。从分布式系统死锁产生的条件,解决策略,以及分布式系统中死锁预防、避免和检测的各种算法进行了具体阐述。