Open access

A Computationally Improved Optimal Solution for Deadlocked Problems of Flexible Manufacturing Systems Using Theory of Regions

Written By

Yen-Liang Pan

Submitted: 23 November 2011 Published: 29 August 2012

DOI: 10.5772/50873

From the Edited Volume

Petri Nets - Manufacturing and Computer Science

Edited by Pawel Pawlewski

Chapter metrics overview

2,100 Chapter Downloads

View Full Metrics

1. Introduction

While competing for a finite number of resources in a flexible manufacturing system (FMS), e.g., robots and machines, each part has a particular operational flow that determines the order in which such resources are needed. However, such competition for shared resources by concurrent job processes can leadto a system deadlock. It occurs when parts are blocked waiting for shared resources held by others that will never be granted. Its related blocking phenomena often incur unnecessary overhead cost, e.g.,a long downtime and low utilization rate of some critical and expensive resources, possibly leading to a catastrophic outcome in some highly automated FMS. Therefore, an efficient deadlock control policy must be developed to ensure that deadlocks do not occur. Having received considerable attention in literature, deadlock is normally prevented by using an offlinecomputational mechanism to control the resource requestsin order to avert deadlocks. Fanti and Zhou1 introduce three fundamental methods (i.e. prevention, detection and avoidance) to solve the deadlock problems.Deadlock prevention aims to impose system constraints to prevent a deadlock. Importantly, deadlock prevention algorithms do notrequire run-time costs since the problems are solved in system design and planning stages. This study belongs to the deadlock prevention field.

Petri nets (PN)2 have been recognized as one of the most powerful formal methods for modeling FMS.The reason is that they are well suited to represent such FMS characteristics as precedence relations, concurrence, conflict and synchronization. Their analysis methods used for deadlock prevention in FMS include structural analysis and reachability graphs. Deadlock prevention and avoidance schemes have been developed for controlling FMS3-8 by using the former. In particular, deadlock prevention problems are solved using the concept of siphons3-6. Li & Zhou propose an elementary siphon control policy (ESCP) to reduce the redundant siphons to obtain structurally simpler controllers9-10. However, they cannot obtain optimal ones. Reachability graph methods are used to obtain the live system behavior11-14. Without confining to a certain class of FMS, they can provide an optimal deadlock controller by adopting the theory of regions15. The theory is originally developed for a transition system (TS). A state-based representation with arcs labeled with symbols from an alphabet of events in a TS can be mapped into a PN model. For an elementary TS (ETS) there exists a PN with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original TS.

Uzam12 follows the theory of regions15 to define a deadlock-zone (DZ) and deadlock-free zone (DFZ) for preventing deadlocks. Hence, the concept of DZ and DFZ is used to solve ESSPs. An optimal controller can be obtained but suffers from many redundant control places. Ghaffariet al.13 propose a unique interpretation of the theory of regions and define MF (forbidden marking), MD (dangerous marking), ML (legal marking), and (the set of marking/transition-separation instances or MTSI). An optimal PN controller synthesis method for FMS is proposed based on both MTSI and the theory of regions. Unfortunately, redundant MTSIs cannot be entirely avoided for large FMS cases.

To reduce redundant control places, Li et al.16 adopt a combined algorithm based on siphon control and the theory of regions15. Its advantage is that the number of separation instances is significantly reduced after some sets of elementary siphons of a system are controlled. However, it fails to determine all sets of MTSIs and its application seems limited to some special nets only.

Uzam and Zhou propose an iterative control policy of liveness enforcement for PNs based on the theory of regions17. Less computation is required to obtain a controller. However, as indicated by Li et al18, it requires the repeated calculation of reachability graphs. Piroddi et al. propose a combined selective siphons and critical markings in a reachability graph algorithm to obtain optimal controllers via iterations19. They successfully identify the critical uncontrolled siphons and control them to make a deadlock-prone PN live. However, their algorithm also requires the repeated calculation of reachability graphs. Eventually, the controllers are not ordinary (i.e. they contain weighted arcs).

This work in this chapter aims to develop a computationally more efficient optimal deadlock control policy by using the theory of regions. It focuses on dead markings in a reachability graph. The concept of a crucial MTSI (CMTSI) is proposed to synthesize optimal controllers. The proposed method can reduce the computational burden of the MTSI method13 and redundant control places12-13. The experimental results indicate that it is the most efficient policy amongall known ones12-13, 16that can design optimal controllers.

Section 2 presents the basic definitions and properties of PNs and the theory of regions. Section 3 describes the proposed policy. Section 4 presents the experimental results. Section 5 gives the comparisons. Conclusions are made in Section 6.


2. Preliminaries

2.1. Petri nets2

A Petri net (PN) is a 5-tuple N = (P, T, F, W, M0)where P is a finite set of places; T is a finite set of transitions, with P T and P T =; F (P×T) (T×P) is the set of all directed arcs, W: (P×T) (T×P)→Nis the weight function where N= { 0, 1, 2, …}, and M0: PNis the initial marking. A PN is said to be ordinary, denoted as (P, T, F), if f F, W(f) = 1. [N]+(p, t) = W(p, t)is the input function that means the multiplicity of a directed arc from p to t if (p, t)F. [N]-(p, t) = W(t, p)is the output function that means the multiplicity of a directed arc from t to p if (t, p)F. The set of input (resp., output) transitions of a place p is denoted by •p (resp., p•). Similarly, the set of input (resp., output) places of a transition t is denoted by •t (resp., t•). A PN structure (P, T, F, W) is denoted by N. A PN with a given initial marking is denoted by (N, M0).

A PN is said to be pure if no place is both input and output places of the same transition. The so-called incidence matrix [N] of a pure Petri nets is defined as [N] = [N]- [N]+. A transition t is said to be enabled at marking M, if pt, M(p) W(p, t), or p is marked with at least W(p, t) tokens, as denoted by M[t>. A transition may fire if it is enabled. In an ordinary net, it is enabled iff p•t, M(p) 1. Firing t at M gives a new marking Msuch that pP, M(p) = M(p) – W(p, t) + W(t, p). It is denoted as M[t>M. M indicates the number of tokens in each place, which means the current state of the modeled system. When Mncan be reached from M0by firing a sequence of transitions σ, this process is denoted by M [σ >Mn and satisfies the state equationMn = M + [N]σ. Here, σis a vector of non-negative integers, called a firing vector, and σ(t) indicates the algebraic sum of all occurrences of t in . The set of all reachable markings for a PN given M0is denoted by R(N,M0). Additionally, a definition of linearized reachability set (using the state equation) is defined as R(N,M0)={M: M = M0 +[N](•σ)}. This definition is suitable for the incorporation of the state equation into a set of linear constraints. The markings in R(N,M0) - R(N,M0) are called spurious ones (with respect to the state equation)20. They may also be the solutions of the state equation but not reachable markings. In this work, ones just focus on the reachable markings.

A transition t is said to be live if for any MR(N,M0), there exists a sequence of transitions whose firing leads to M’ that enables t.A PNis said to be live if all the transitions are live. A PNcontains a deadlock if there is a marking MR(N,M0) at which no transition is enabled. Such a marking is called a dead marking.Deadlock situations are as a result of inappropriate resource allocation policies or exhaustive use of some or all resources. Liveness of a PN means that for each marking MR(N,M0) reachable from M0, it is finally possible to fire t, tT through some firing sequence.(N, M0)is said to be reversible, if MR(N,M0), M0R(N,M).Thus, in a reversible net it is always possible to go back to initial marking (state) M0.A marking Mis said to be a home state, if for each marking MR(N,M0), Mis reachable from M.Reversibility is a special case of the home state property, i.e. if the home state M= M0, then the net is reversible.

2.2. Theory of regions and synthesis problem13

The theory of regions is proposed for the synthesis of pure nets given a finite TS15, which can be adopted to synthesize the liveness-enforcing net supervisor (LENS) for a plant model12-13. For convenience, our method follows the interpretation of the theory of regions in13.

First of all, let T be a set of transitions and G be a finite directed graph whose arcs are labeled by transitions in T. Assume that there exists a node v in G such that there exists a path from it to any node. The objective of the theory of regions is to find a pure PN (N, M0), having T as its set of transitions and characterized by its incidence matrix [N](p, t) and its initial marking M0, such that its reachability graph is G and the marking of node v is M0. In the following, M denotes both a reachable marking and its corresponding node in G.

Consider any marking M in net (N, M0). Because (N, M0) is pure, Mcan be fully characterized by its corresponding incidence vector [N](p, )ΓM where ΓMis the firing vector of pathΓM. For any transition t thatis enabled at M, i.e., t is the label of an outgoing arc of the node M in G

M(p) = M(p) + [N](p, )ΓMM, (M, M) GM [ t>M' (1)

Consider now any oriented cycle of a reachability graph. Applying the state equation to a node in and summing them up give the following cycle equation:


where is an oriented cycle of G, γ(t)is a firing vector corresponding to , and C is the set of oriented cycles of G.

According to the definition of G, there exists an oriented path Mfrom M0 to M. Applying (1) along the path leads to M(p) = M0(p) + [N](p,)ΓM. There are several paths from M0 to M. Under the cycle equations, the product [N](p,)ΓM is the same for all these paths. As a result, ΓMcan be arbitrarily chosen. The reachability of any marking M in G implies that


The above equation is called the reachability condition. Notably, (3) is necessary but not sufficient. Hence, spurious markings are beyond this paper.

It is clear that the cycle equations and reachability conditions hold for any place p. For each pair (M, t) such that M is a reachable marking of G and t is a transition not enabled at M, t should be prevented from happening by some place p. Since the net is pure, t is prevented from happening at M by a place p iff


The above equation (4) is called the event separation condition of (M, t). The set of all possible pairs (M, t) where M is a reachable marking and t is not enabled at M is called the setof event separation instances or marking/transitions-separation instances (MTSI)13. Symbol is used to represent the set of MTSI in this paper. To solve the control problem, is identified. The corresponding control places can then be found to prevent the transitions of the controlled system from firing in order to keep all legal markings only.


3. Controller synthesis method

In this section, an efficient controller synthesis method is developed based on the theory of regions. Please note that all transitions of the PN models are regarded as controllable ones.

3.1. Supervisory control problem

It is assumed that a deadlock-prone PN model contains at least a dead marking in its reachability graph at which no transition is enabled. Its reachability graph contains dead and live zones. Consequently, this study attempts to propose a method to prevent the controlled systems from entering a dead zone/marking.

A dead marking cannot enable any transition and thus cannot go to any other markings. We can formally define the dead marking MD as follows.

Definition 1: The set of dead markingsMD= {MR(N, M0)| at M, no transition is enabled}.

Definition 2: A zone consisting of all dead markings is called a dead zone, denoted by ZD.

Once a marking enters a dead zone, the system is dead. If there is no dead zone in a reachability graph, the system is called a live one.

The goal of the work is to control a deadlock-prone system such that it is live. All markings of a reachability graph can be divided into three groups: legal markings (ML), quasi-dead markings (MQ), and dead markings (MD).

Definition 3: The set of quasi-dead markings MQ = {MR(N, M0)| M must eventually evolve to a dead one regardless of transition firing sequences}.

Definition 4: A zone consisting of all quasi-dead markings is called a quasi-dead zone, denoted by ZQ.

Definition 5: A zone consisting of all quasi-dead and dead markings, i.e., ZI = ZD ZQ, is called an illegal zone.

Markings except quasi-dead and dead markings are legal ones. Once a legal marking is enforced into the illegal zone, the net will eventually become deadlock.

Definition 6: A zone consisting of all legal markings is called a legal zone,i.e., ZL = R(N, M0) - ZI.

Ramadge and Wonham show that a system has the maximally permissive behavior if the system behavior equals ZL21. In other words, one must remove all the markings in illegal zone (i.e. quasi-dead and dead markings) from R(N, M0) if one wants to obtain the maximally permissive behavior. Ghaffari et al. propose the MTSI method to achieve their deadlock prevention based on the theory of regions13. However, the set of all MTSIs from the reachability graph must be identified. As a result, we can conclude that their method is computationally inefficient. A more efficient method is thus needed as described next.

3.2. Crucial MTSI (CMTSI)

Two types of CMTSIs are defined as follows.

Definition 7: Type I CMTSI: = {(M, t)|M ML, t T, and MMD, MML, and tT such that M [t>M and M [t>M}. Denote the set of all the dead markings related to as M'D, i.e., MD = {MMD | (M, t) such that M [t M}. They are called type I deadlocks.

Definition 7 explains a legal marking that can evolve into a dead or legal zone as shown in Figure 1 through a single transition’s firing. For those dead markings that are not type I deadlocks, we need to introduce Type II CMTSI and deadlocks.

Definition 8: A zone consisting of all type I deadlocks (M'D) is called type I dead zone, denoted by Z.

Definition 9: k is defined as a transition firing sequence starting in a quasi-dead marking (MQ) and ending in a deadlock marking in MD where i = |σk| is the number of transitions in σk, called its length. Denote a firing sequence with the shortest length (i.e., smallest i) from any quasi-dead marking to M' as σ*(M') given M'MD –M'D.

Definition 10: Type II CMTSI : = {(M, t)|MML, t T, and MMQ, MML, MMD, tT, and a firing sequence σ=σ*(M) from Mto Msuch that M [t>M, M [t>M, and M [σ>M}. The set of dead markings associated with Type II CMTSI is denoted as M"D, called type II deadlocks. MD = {MMD | (M, t) , MMQ and a firing sequence from M to Msuch that M[tMand σ=σ*(M)}.

Figure 1.

A structure of Type I CMTSI.

Definition 11: A zone consisting of all type II deadlocks (MD) is called type II dead zone, Z.

A Type II CMTSI contains a legal marking that cannot reach a dead marking with one single transition’s firing as shown in Figure 2. Given a dead marking in M"D,the shortest transition firing sequence needs to be found. The main reason is based on the fact that, for a dead marking, the length of the firing sequence from the initial marking to CMTSI is the longest path than those from the initial marking to MTSIs. Hence, the solutions of MTSIs will be totally covered by the solution of CMTSI. For example, as shown in Figure 3, σ*is the shorter path since |σ*| < |σ| (i.e. |σ*| =1 and |σ| = 3).

Remark 1: A dead marking is always with its corresponding CMTSI. As a result, the corresponding CMTSI is of either Type I or II. Type I may be viewed as a special case of Type II CMTSI by defining * = 0 (no need to enter ZQ but directly to ZD). Type I CMTSI will be processed first in our proposed method. In the following, Theorems 1-3 will help readers to understand how to choose CMTSIs, which are with the same firing sequence of legal markings, from Types I and II.

Theorem 1: If a dead marking MM'D is associated with two different CMTSIs, only one CMTSI needs to be controlled.

Proof: Assume that a dead marking M is with both CMTSIs {Mi, tm} and {Mj, tn} as shown in Figure 4. According to the state equation, Mi + [N](•tm) = Mj + [N](•tn) = M. Arranging the above equation, M0 + [N](•σM0Mi) + [N](•tm) = M0 + [N](•σM0Mj) + [N](•tn). According to (4), realizing either CMTSI, e.g., {Mi, tm}, leads to M0 + [N](•σM0Mi) + [N](•tm) -1, which in turn implies M0 + [N](•σM0Mj) + [N](•tn) -1 and vice versa. Hence, only one CMTSI needs to be controlled.

Remark 2: Based on Theorem 1, if a dead marking MM'D is associated with more than two CMTSIs, only one of them needs to be controlled.

Figure 2.

A structure of Type II CMTSI.

Figure 3.

The shorter path σ* in Type II CMTSI given a dead marking.

Theorem 2: If a dead marking MMD, is associated with two CMTSIs whose markings can reach a same quasi-dead marking M' via their respective single transition’s firing, only one CMTSI needs to be controlled.

Proof: Assume that a dead marking M is associated with Type II CMTSIs {Mp, tr} and {Mq, ts}. Mp and Mq reaches a quasi-dead markings M' via tr and ts’s firing, respectively as shown in Figure 5.

According to the state equation, Mp + [N](•tr) + [N](•σ*) = Mq + [N](•ts) + [N](•σ*) M. Arranging the above equation, one can realize that Mp + [N](•tr) =Mq + [N](•ts). According to (4), realizing either CMTSI, e.g., {Mp, tr}, leads to M0 + [N](•σM0Mp) + [N](•tr) -1, which in turn implies M0 + [N](•σM0Mq) + [N](•ts) -1 and vice versa. Hence, only one CMTSI needs to be controlled.

Theorem 3: A dead marking MMD, is associated with two CMTSIs whose markings can reach two different quasi-dead markings Mp and Mq via two different single transitions’ firing. Both need to be controlled if [N](•σr*) [N](•σs*).

Proof: Assume that a dead marking M is associated with both Type II CMTSIs {Mp, tr} and {Mq, ts}. Mp and Mq reach two different quasi-dead markings Mp and Mq via tr and ts’s firing, respectively as shown in Figure 6.

According to the state equation, Mp + [N](•tr) + [N](•σr*) = Mq + [N](•ts) + [N](•σs*) = M"D. Arranging the above equation, Mp + [N](•σr*) = Mq + [N](•σs*). Since [N](•σr*) [N](•σs*), Mpis not equal to Mq. And also according to the definition of the event separation condition equation, the first set of CMTSI {Mp, tr} leads to the first event separation condition equation is M0 + [N](•σM0Mp) + [N](•tr) -1; and the second set of CMTSI {Mq, ts} leads to the another event separation condition equation is M0 + [N](•σM0Mq) + [N](•ts) -1. Hence, one can infer that Mp and Mq are two different quasi-dead markings if [N](•σr*) [N](•σs*). It hints the two event separation condition equations are different. As a result, both CMTSIs need to be controlled.

Figure 4.

A type I deadlocks associated with two CMTSIs.

Figure 5.

Two CMTSIs connected to the same quasi-dead marking.

Definition 12: A legal marking MML can be led to a quasi-dead markingMq via a single transition firing. Mqmust eventually evolve to a dead one Md (i.e. MdMD) after a sequence n = t1t2…tn fires. Denote the set of all the markings on the path from Mq to Md as Mq-d.

Figure 6.

Two CMTSIs connected to two quasi-dead markings.

Remark 3: Based on Theorem 3, both CMTSIs still need to be controlled even if MP= Mq for the case shown in Figure 7.

Figure 7.

Two CMTSIs connected to two quasi-dead markings Mp and Mq with r* = s* = *(MD).

Control places are then found after CMTSIs. They are used to keep all markings of the controlled system within the legal zone.

Theorem 4: ()

Figure 8.

a) A Petri net model.22 (b) Its reachability graph.

Here, Figure 8(a) taken from existing literatures22 is used todemonstrate how to identify two types of CMTSIs from its reachability graph (i.e. Figure 8(b)). Assume that all transitions of PN models are immediately in this case. Therefore, one can easy identify there are two dead markings M'D(i.e. M2) and M"D (i.e. M15) and four quasi-dead markings (i.e. M11, M12, M13 and M14). Additionally, the markings M0, M1, M3-M10 are the legal markings. Based on the mentioned above, there are two sets of CTMSIs in the reachability graph system due to the two dead markings in the system. As a result, one can infer that {M0, t2} belongs to type I CMTSI and {M7, t1} belongs to type II. In this Petri net system model, there are only one type I CMTSI and only one type II.

3.3. Procedure of deadlock prevention policy

Next, quasi-dead, dead, and legal markings are identified. Based on12-13, the maximally permissive behavior means all of legal markings (ML) and the number of reachability condition equations equals |ML|. Additionally, all CMTSIs can be obtained such that the legal markings do not proceed into the illegal zone. The proposed deadlock prevention algorithm is constructed as Figure 9.

Theorem 5: The proposed deadlock prevention policy is more efficient than the method proposed by Ghaffari et al.13

Proof: The theory of regions is used to prevent the system deadlocks by both our deadlock prevention policy and the conventional one. All MTSIs can be controlled by the two control policies. Since () , the use of CMTSI can more efficiently handle the synthesis problem than that of MTSI13.

Figure 9.

The Proposed Deadlock Prevention Flowchart.


4. Experimentalresults

Two FMS examples are used to evaluate our deadlock prevention policy12-23.

Figure 10.

An FMS PN Model12.

Example I: An FMS is shown in Figure 1012. This PN is a system of simple sequential processes with resources (S3PR), denoted by (N1, M0). To do our deadlock prevention policy, R(N1, M0) of the PN system can be constructed as shown in Figure 11.

Two dead markings (i.e. M7 and M12) can then be identified. Next, '1 = {(M3, t5)} and '2 = {(M15, t1)} are obtained. The event separation condition equations can be obtained through them as follows.

M7(pc) = M0(pc) + 2[N](pc, t1)+ [N](pc, t2) + [N](pc, t5) -1 (5)

M12(pc) = M0(pc) + [N](pc, t1)+2[N](pc, t5) +[N](pc, t6) -1 (6)

Figure 11.

R(N, M0) of Example I.

Two cycle equations are as follows.

[N](pc, t1)+[N](pc, t2) + [N](pc, t3)+ [N](pc, t4) = 0 (7)

[N](pc, t5)+[N](pc, t6) + [N](pc, t7) + [N](pc, t8) = 0 (8)

After listing all reachability conditions, all legal markings can be determined. In detail, M0-M6, M8, and M13-M19 are legal. Hence, the following reachability conditions are obtained.

M0(pc) 0 (9)

M1(pc) = M0(pc) + [N](pc, t1) 0 (10)

M2(pc) = M0(pc) + [N](pc, t1) + [N](pc, t2) 0 (11)

M3(pc) = M0(pc) + 2[N](pc, t1)+ [N](pc, t2) 0 (12)

M4(pc) = M0(pc) + 2[N](pc, t1)+ [N](pc, t2) + [N](pc, t3) 0 (13)

M5(pc) = M0(pc) + 2[N](pc, t1)+ 2[N](pc, t2) + [N](pc, t3) 0 (14)

M6(pc) = M0(pc) + 3[N](pc, t1)+ 2[N](pc, t2) + [N](pc, t3) 0 (15)

M8(pc) = M0(pc) + [N](pc, t1)+ [N](pc, t2) + [N](pc, t3) 0 (16)

M13(pc) = M0(pc)+ [N](pc, t5) 0 (17)

M14(pc) = M0(pc) + [N](pc, t5) + [N](pc, t6) 0 (18)

M15(pc) = M0(pc) + 2[N](pc, t5) + [N](pc, t6) 0 (19)

M16(pc) = M0(pc) + 2[N](pc, t5) + [N](pc, t6) + [N](pc, t7) 0 (20)

M17(pc) = M0(pc) + 2[N](pc, t5) + 2[N](pc, t6) + [N](pc, t7) 0 (21)

M18(pc) = M0(pc) + 3[N](pc, t5) + 2[N](pc, t6) + [N](pc, t7) 0 (22)

M19(pc) = M0(pc) + [N](pc, t5) + [N](pc, t6) + [N](pc, t7) 0 (23)

Furthermore, two optimal control places CP1 and CP2 can be obtained when (5) and (7)-(23) are solved. Their detailed information is: M0(CP1) = 1, t1= t5= -1, t2= t6= 1, t3= t4= t7= t8 = 0; and M0(CP2)=1, t2= t5 = -1, t3 = t6= 1, t1= t4= t7= t8 = 0. By the same way, using (6) and (7)-(23),one can find two optimalcontrol places, Cp3 and Cp4. M0(CP3) = 1, t1= t6= -1, t2= t7 = 1, t3 = t4= t5= t8 = 0; and M0(CP4) = 1, t1 = t5= -1, t2 = t6 = 1, t3= t4= t7 = t8= 0. Notably, CP1 and CP4 are the same. Therefore, a redundant control place (CP4) can be removed. As a result, the system net can be controlled with the three control places CP1, CP2 and CP3. The optimally controlled system net(N1H, M0) is obtained as shown in Table 1.

It is worthy to emphasize that the three control places are obtained by using two CMTSIs and 36 equations under our control policy. However, six MTSIs/ESSPs and 108 equations have to be solved in two existing literatures12, 24.

Additional Control PlacesM0(Cpi)(Cp)(Cp)
Cp11t2, t6t1, t5
Cp21t3, t6t2, t5
Cp31t2, t7t1, t6

Table 1.

Control Places of the Net (N1H, M0)

Example II: This example is taken from23 and is used in12, 16, 24. Here, the PN model of the system, denoted as (N2, M0), is shown in Figure 12.

Figure 12.

The Petri nets model of example II.

To prevent deadlock, 282 reachable markings (M1 to M282) are identified according to the software INA25. 16 dead markings M9, M19, M70, M71, M76, M77, M78, M83, M84, M94, M99, M100, M105, M106, M112, and M113 are then located. Next, 61 quasi-dead markings M6, M7, M8, M14, M15, M16, M17, M18, M25, M48, M66, M67, M68, M69, M72, M73, M74, M75, M79, M80, M81, M82, M87, M101, M102, M103, M104, M108, M109, M110, M111, M124, M130, M135, M136, M141, M142, M143, M150, M162, M198, M203, M204, M210, M250, M251, M257, M258, M259, M260, M261, M262, M263, M265, M269, M270, M272, M273, M274, M277, and M278 are found based on Definition 3 in this paper. Hence, the number of legal markings (i.e. 288 – (16 + 61) = 205) can be determined. Type I and II CMTSIs can be obtained as shown in Table 2. Notice that {(M56, t9)} in M77 is a redundant one.

M9{(M65, t1)}M19{(M56, t1)}
{(M56, t9)}
M70{(M43, t9)}M76{(M65, t11)}
M71{(M51, t9)}M77{(M56, t9)}
{(M56, t11)}
M78{(M171, t9)}M83{(M128, t11)}
M94{(M93, t1)}M84{(M60, t9)}
{(M60, t11)}
M99{(M98, t1)}M105{(M93, t11)}
M100{(M98, t4)}M106{(M98, t11)}
M112{(M122, t11)}
M113{(M96, t11)}

Table 2.

The Dead Markings and Their Relative CMTSIs.

M(DEvent Separation Condition Equations
M9M0 + 3t1 + t2 + t3 + 2t9 + t10 -1
M70M0 + 3t1 + t2 + 2t3 + 2t4+ t6 + 2t9+ t10 -1
M0 + 3t1 + 2t2 + t3 + t4 + t5 + t6 + 2t9 + t10 -1
M71M0 + 3t1 + t2 + 2t3 + t4 + t5 + t6 + 2t9 + t10 -1
M0 + 3t1 + 2t2 + t3 + 2t5 + t6 + 2t9 + t10 -1
M78M0 + 2t1 + t2 + t3 + t4 + t5 + t6 + 2t9 + t10 -1
M0 + 2t1 + 2t2 + 2t5 + t6 + 2t9 + t10 -1
M0 + 2t1 + 2t3 + 2t4 + t6 + 2t9 + t10 -1
M94M0 + 2t1 + t3 + 3t9 + 2t10 + t11 + t12 -1
M99M0 + 3t1 + 2t3 + t4 + t6 + 3t9 + 2t10+ t11 + t12 -1
M0 + 3t1 + t2 + t3 + t5 + t6 + 3t9 + 2t10+ t11 + t12 -1

Table 3.

The Dead Markingsand Relative Event Separation Condition Equationsof Type I CMTSI.

Tables 3-4 show the event separation condition equations based on 18 CMTSIs. Here, the procedure of our method is introduced as follows. Due to the space limitation, we use only one example (i.e. dead marking M9) to illustrate how to prevent legal markings from leading to dead one M9 by using a CMTSI. To do so, 'C1 = {(M65, t1)} can be located due to M9. The event separation condition equation can then be identified as follows.

M9(CP1) = M0(CP1) + 3t1 + t2 + t3 + 2t9 + t10 -1 (24)

Next, three different cycle equations are:

t1 + t2 + t5 + t6 + t7 + t8 = 0 (25)

t1 + t3 + t4 + t6 + t7 + t8 = 0 (26)

t9 + t10 + t11 + t12 + t13 + t14 = 0 (27)

Finally, 205 reachability condition equations can be listed. They represent the sequence of all legal markings from the initial one. Moreover, control place CP1 can be computed, i.e., M0 (CP1) = 2, CP1= {t6, t13}, and CP1 = {t1, t11}. Similarly, other control places are obtained as shown in Tables 5-6.

M(DEvent Separation Condition Equations
M19M0 + 4t1 + t2 + 2t3 + t4 + t6 + t9 + t10 -1
M0 + 4t1 + 2t2 + t3 + t5 + t6 + t9 + t10 -1
M0 + 3t1 + t2 + 2t3 + t4 + t6 + 2t9 + t10 -1
M0 + 3t1 + 2t2 + 2t3 + t5 + t6 + 2t9 + t10 -1
M76M0 + 2t1 + t2 + t3 + 2t9 + t10 + t11 -1
M77M0 + 3t1 +t2 + 2t3 + t4+t6+t9+t10+t11 -1
M0 + 3t1 + 2t2 + t3+t5 + t6+t9+t10+t11 -1
M83M0 + t1 + t2 + 2t9 + t10 + t11 -1
M84M0 + 2t1 + t2 + t3 + t4 + t6 + t9 + t10 + t11 -1
M0 + 2t1 + 2t2 + t5 + t6 + t9 + t10 + t11 -1
M0 + 3t1 +t2 + 2t3 + t4+t6+2t9+t10 -1
M0 + 3t1 + 2t2 + t3+t5 + t6+2t9+t10 -1
M105M0 + t1 + t3 + 3t9 + 2t10 + 2t11 + t12 -1
M106M0 + 2t1 + 2t3 + t4 + t6 + 3t9 + 2t10+ 2t11 + t12 -1
M0 + 2t1 + t2 + t3 + t5+ t6 + 3t9 + 2t10 + 2t11+ t12 -1
M112M0 + 3t9 + 2t10 + 2t11+ t12 -1
M113M0+ t1 + t3+ t4 + t6 + 3t9+ 2t10 + 2t11 + t12 -1
M0 + t1 + t2+ t5 + t6+ 3t9 + 2t10 + 2t11+ t12 -1

Table 4.

The Dead Markings and Relative Event Separation Condition Equations of Type II CMTSI.

M9{(M65, t1)}2t6, t13t1, t11
M70{(M43, t9)}3t6, t11t2, t4, t9
3t5, t7, t11t2, t6, t9
3t7, t11t4, t5, t9
M71{(M51, t9)}3t7, t11t4, t5, t9
M78{(M171, t9)}3t7, t11t4, t5, t9
M94{(M93, t1)}2t6, t13t1, t11
M99{(M98, t1)}4t7, t11t1, t9
M100{(M98, t4)}3t7, t11t4, t5, t9

Table 5.

Control Places from TYPE I CMTSI.

Finally, the controlled net is obtained by adding the six control places as shown in Table 7. It is live and maximally permissive with 205 reachable markings. However, 59 ESSPs and nine control places are required in12. It hints that 59 sets of inequalities are needed in 12, while only 18 sets of inequalities suffice using our algorithm. Hence, our policy is more efficient than that in 12.

Li et al. solve this problem by using elementary siphons controlled policy (ESCP) and the theory of region 16. A two-stage deadlock prevention method is used. First, ESCP is used to replace a siphon control method5. Therefore, the number of dead markings is reduced. Second, the theory of regions is used to obtain the optimal solution. Three elementary siphons (i.e. S1 = {p2, p5, p13, p15, p18}, S2= {p5, p13, p14, p15,p18} and S3 = {p2, p7, p11, p13, p16p19}) can be identified. As a result, three control places VS1VS3 as shown in Table 8 are needed to handle three elementary siphons. Then a partially controlled PN system, denoted as (N2L1, M0), can be obtained after the first stage.

M19{(M56, t1)}2t6, t13t1, t11
4t7, t11t1, t9
{(M56, t9)}3t5, t7, t11t2, t6, t9
4t7, t11t1, t9
M76{(M65, t11)}1t5, t13t2, t11
M77{(M56, t11)}1t5, t13t2, t11
M83{(M128, t11)}1t5, t13t2, t11
M84{(M60, t9)}3t5, t7, t11t2, t6, t9
{(M60, t11)}1t5, t13t2, t11
M105{(M93, t11)}1t5, t13t2, t11
M106{(M98, t11)}1t5, t13t2, t11
M112{(M122, t11)}1t5, t13t2, t11
M113{(M96, t11)}1t5, t13t2, t11

Table 6.

Control Places from TYPE II CMTSI.

Additional Control PlacesM0(Cpi)(Cpi) (Cpi)
Cp11t5, t13t2, t11
Cp22t6, t13t1, t11
Cp33t6, t11t2, t4,t9
Cp43t5, t7, t11t2, t6,t9
Cp53t7, t11t4, t5,t9
Cp64t7, t11t1, t9

Table 7.

Control Places for the Net (N2H, M0).

However, (N2L1, M0) has a dead marking. Figure 13 shows a partial reachability graph and the deadlock marking M57 is included. M57 is one of the 210 reachable markings (i.e. the reachable markings M1-M210 as denoted in16. In16, 210 reachable markings are divided into two categories: legal and illegal zones. The illegal zone consists of quasi-dead markings (i.e. M54, M55, M56and M60) and a dead marking (i.e. M57). Obviously, some legal markings (i.e. M43, M44, M47, M48, M49, M53, M59 and M74) can enter the illegal zone (i.e. ZI = ZQZD). One can realize that they use the theory of regions to prevent these legal markings from entering ZI. Therefore, they must resolve 8 MTSIs (i.e. {(M43, t9)}, {(M44, t9)}, {(M47, t9)}, {(M48, t9)}, {(M49, t9)}, {(M53, t4)}, {(M59, t1)}, {(M74, t2)}) and many equations in this example. Then the additional three control places can be obtained as shown in Table 9. Eight MTSIs are needed. Hence, their control policy16 does not seem efficiently enough when the MTSI at the second stage is used to obtain control places.

To compare the efficiency of the deadlock prevention methods, the proposed one is examined in the system net (N2L1, M0). One can realize that M57 is the only deadlock marking in R(N2L1, M0). Based on our method, only the dead marking M57 needed to be controlled. Here, only one = {(M44, t9)} is needed. Obviously, the involved necessary equations are much less than those of the conventional one. We can obtain the same controlled net as that in 16. Hence, the proposed concept of CMTSIs can be used in their approach16 to improve its computational efficiency significantly as well.

Figure 13.

A Partial Reachability Graph of the Net (N2L1, M0)16.

Additional Control PlacesM0(Cpi)(Cpi) (Cpi)
Vs11t5, t13t2, t11
Vs22t4, t5, t13t1, t11
Vs33t7, t11t4, t5,t9

Table 8.

Additional Control Places for the Net (N2L1, M0)

Additional Control PlacesM0(Cpi)(Cpi) (Cpi)
Cp13t6, t11t2, t4,t9
Cp23t5, t7, t11t2, t6,t9
Cp34t2, t4, t7, t11t1,t6, t9

Table 9.

Control Places for (N2L1, M0) by Two-Stage Method.


5. Comparison with existing methods

One can attempt to make a comparison with the previous methods12, 16, 24 in terms of efficiency. The first one proposed by Uzam12, called Algorithm U, is totally based on the theory of regions. It solves six ESSPs in Example I. Then three control places are added on the net such that the controlled net is live and reversible. As for Example II, it solves 59 MTSIs. Nine control places are obtained. However, theproposed deadlock prevention policy called Algorithm P solves only two and 18 CMTSIs in Examples I and II, respectively.

The other one is proposed by Li et al.16, 24 called Algorithm L in which only the theory of regions is used in Example I. Notice that both the controlled results of Algorithms L and U are the same in Example I. In Example II, usingAlgorithm L, eight MTSIs are solved and six control places arecomputed. However, under the two-stage control policy, only one set of MTSI is needed by using our new policy to obtain the controlled result that is as the same asAlgorithm L in Example II. Note that both the definitions of ESSP and MTSI are the same. Hence, ESSP and CMTSI can be regarded as MTSI for the comparison purpose. The detailed comparison results are given in Table 10. However, only 18 MTSIs among 59 MTSIs are needed by using Algorithm P.

Example# of Places# of Resource PlacesMTSI
U, L, P
Control Places
U, L, P
I1136, 6, 23, 3, 315
II19659, ,189, , 6205
II (two stages) , 8, 1 , 6, 6

Table 10.

Comparison of the Controlled Systems.

For Example II, eight MTSIs are required to obtain the six control places under Algorithm L. Hence, one can infer that its performance is better than that of Algorithm U. Only one set of CMTSI is needed to obtain the same control result by Algorithm P. As a result, one can conclude that our proposed policy is more efficient than the other two methods.

To examine and compare the efficiency of the proposed method with those in16,24 in a system with large reachability graphs, one can use eight different markings of p1, p8, p15, p18, and p19: [6, 5, 1, 1, 1]T, [7, 6, 2, 1, 1]T, [7, 6, 1, 2, 1]T, [7, 6, 1, 1, 2]T, [9, 8, 2, 2, 2]T, [12, 11, 3, 3, 3]T, [15, 14, 4, 4, 4]T, and [18, 17, 5, 5, 5]T. Tables 11 and 12 show various parameters in the plant and partially controlled net models, where M (p15), M (p18), and M (p19) vary; |R|, |ML|, |RD|U, |RD|L, indicate the number of reachable markings (states), legal markings, and dead markings under Algorithms U and L, respectively. Additionally,MTSIs of Algorithms U,L, and P are symbolized by ||U, ||L and ||P, respectively. The last column is ra = ||P /||U in Table 11, and rb = |P /||L in Table 12. Notably, Algorithm G13 can be regarded as Algorithm U in Table 11 since the number of MTSIs and ESSPs are the same. In table 11, here, Nsep represents the number of MTSIs, and the Nsep/U,Nsep/L and Nsep/P represent the number of MTSIs of Algorithms U,L, and P, respectively. Obviously, the number of ||U in the plant model grows quickly from cases 1 to 8. For instance, when M (p15) = M (p18) = M (p19) = 5, ||U = 4311, meaning that one must solve 4311 MTSIs when AlgorithmU is used. However, since ||P = 228, only 228 equations (MTSIs) need to be solved under Algorithm P. As a result, Algorithm P is more efficient than Algorithm U in a large system.


Table 11.

Parametersin the Plant and Partially Controlled Models with Varying Markings: U vs. P.


Table 12.

Parametersin the Plant and Partially Controlled Models with Varying Markings: L vs. P.

In Table 12, the number of MTSIs calculated by Algorithm L can be controlled, but Algorithm Pis more efficient in these cases. For instance, when M (p15) = M (p18) = M (p19) = 5, ||L = 192, meaning that one still has to solve 192 MTSIs when Algorithm L is used. However, ||P =108. Only 108 MTSIs need to be solved by using Algorithm P. Importantly, the computational cost can be reduced by using our proposed method when it is compared with those in12, 16. In conclusion, Algorithm Pis more efficient in large reachability graph cases than those in12-13.


6. Conclusion

The proposed policy can be implemented for FMSs based on the theory of regions and Petri nets, where the dead markings are identified in its reachability graph. The underlying notion of the prior work is that many inequalities (i.e. MTSIs) must be solvedto prevent legal markings from entering the illegal zone in the original PN model. One must generate all MTSIs in a reachability graph and require high computation. This work proposes and uses CMTSI to overcome the computational difficulty. The detail information is also obtained in existing literatures.26-29 The proposed method can reduce the number of inequalities and thus the computational cost very significantly since CMTSIs are much less than MTSIs in large models.Consequently, it is optimal with much better computational efficiency than those existing optimal policies12-13, 16. More benchmark studies will be desired to establish such computational advantages of the proposed one over the prior ones. It should be noted that the problem is still NP-hard the same as other optimal policies due to the need to generate the reachability graph of a Petri net. The future research is thus much needed to overcome the computational inefficiency of all these methods.



The author is grateful to Prof. Yi-Sheng Huang and Prof. MengChu Zhou whose comments and suggestions greatly helped me improve the presentation and quality of this work.


  1. 1. Fanti MP, Zhou MC.Deadlock control methods in automated manufacturing systems.IEEE Trans Syst Man Cybern A Syst Humans, 2004;34(1):5-22.
  2. 2. Murata T.Petri nets: Properties, analysis and applications.In Proc IEEE. 1989;77(4):541-580.
  3. 3. EzpeletaJ.ColomJ. M.MartinezJ. A.Petrinet.baseddeadlock.preventionpolicy.forflexible.manufacturingsystems. I. E. E.IEEE Trans Robot Autom.1995112173184
  4. 4. Jeng MD.A Petri net synthesis theory for modeling flexible manufacturing systems.IEEE Trans Syst Man Cybern B Cybern. 1997272169183
  5. 5. Huang YS, Jeng MD, Xie XL, Chung SL.Deadlock prevention policy based on Petri nets and siphons Int J ProdRes. 2001;39(2):283-305.
  6. 6. Li ZW, Hu HS, Wang AR.Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE Trans Syst Man Cybern C Appl Rev. 2007374517526
  7. 7. Iordache MV, Moody JO, Antsaklis PJ.A method for the synthesis liveness enforcing supervisors in Petri nets.Procceedings of the 2001 American Control Conference; 2011Jun 25-27; Arlington, VA, USA. 494349480-78036-495-3
  8. 8. Park J, Reveliotis SA.Algebraic synthesis of efficient deadlock avoidance policies for sequential resource allocation systems IEEE Trans Autom Control. 2000;16(2):190-195.
  9. 9. Li ZW, Zhou MC.Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems.IEEE Trans Syst Man Cybern A Syst Humans.2004Jan;3413851
  10. 10. Li ZW, Zhou MC.On siphon computation for deadlock control in a class of Petri nets.IEEE Trans Syst Man Cybern A Syst Humans. 2008383667679
  11. 11. ChoH.KumaranT. K.WyskR. A.Graph-theoreticdeadlock.detectionresolutionfor.flexiblemanufacturing.systemsI. E. E.IEEE Trans Robot Autom.2000112190195
  12. 12. Uzam M.An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions.Int J Adv Manuf Technol. 2002193192208
  13. 13. Ghaffari A, Rezg N, Xie XL.Design of a live and maximally permissive Petri net controller using the theory of regions IEEE Trans Robot Autom. 2003;19(1):137-142.
  14. 14. Reveliotis SA,Choi JY.Designing reversibility-enforcing supervisors of polynomial complexity for bounded Petri nets through the theory of regions.Lecture Notes in Computer Science. 2006;4024:322-341.
  15. 15. BadouelE.DarondeauP.Theoryof.RegionsThird Advance Course on Petri Nets. Springer-Verlag, 1998
  16. 16. Li ZW, Zhou MC, Jeng MD.A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions.IEEE Trans Autom Sci Eng.200851183188
  17. 17. Uzam M,Zhou MC.An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems.IEEE Trans Syst Man Cybern A Syst Humans. 2007373362371
  18. 18. Li ZW, Zhou MC, Wu NQ.A survey and comparison of petri net-based deadlock prevention policies for flexible manufacturing systems.IEEE Trans Syst Man Cybern C Appl Rev.2008382173188
  19. 19. PiroddiL.CordoneR.FumagalliI.Selectivesiphon.controlfor.deadlockprevention.inPetri.netsI. E. E.IEEE Trans Syst Man Cybern A Syst Humans.200838613371348
  20. 20. SilvaM.TeruelE.ColomJ. M.Linear algebraic and linear programming techniques for the analysis of P/T net systems. LNCS, 19981491303373
  21. 21. Ramadge PJ, Wonham WM.The control of discrete event systems.Proc IEEE. 19897718198
  22. 22. ViswanadhamN.NarahariY.JohnsonT. L.Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Trans Robot Autom.199066713723
  23. 23. Abdallah IB, ElMaraghy HA.Deadlock prevention and avoidance in FMS: A Petri net based approach. Int J Adv Manuf Technol.19981410704715
  24. 24. LiZ. W.WangA.LinH. A.deadlockprevention.approachfor. F. M. S.usingsiphon.thetheory.ofregions.Proceedingof.theI. E. E. E.InternationalConference.onSystems.ManCybernetics;2004Oct 10-13; The Hague, Netherlands. 507950840-78038-566-7
  25. 25. IntegratedI. N. A. .NetAnalyzer.SoftwareA.Toolfor.Analysisof.PetriNets.Version 2.2, 31.07. 2003Online]. Available:
  26. 26. Huang YS, Pan YL.Enhancement of An Efficient Liveness-Enforcing Supervisor for Flexible Manufacture Systems. Int J Adv Manuf Technol. 201048725737DOI:s00170-009-2299-x)
  27. 27. Huang YS, Pan YL.An Improved Maximally Permissive Deadlock Prevention Policy Based on the Theory of Regions and Reduction Approach. IET Control Theory Appl. 20115910691078DOI:iet-cta.2010.0371.)
  28. 28. Pan YL, Huang YS. Solutions for Deadlocked Problem of FMSs Using Theory of Regions. Adv Mat Res. 2011;314-346 :535-538. (DOI:10.4028/ .535.)
  29. 29. HuangY. S.PanY. L.ZhouM. C.Computationally Improved Optimal Deadlock Control Policy for Flexible Manufacturing Systems. IEEE Trans Syst Man Cybern A Syst Humans. 2012422404415

Written By

Yen-Liang Pan

Submitted: 23 November 2011 Published: 29 August 2012