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

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 Zhou¹ 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)² 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 FMS^3-8 by using the former. In particular, deadlock prevention problems are solved using the concept of siphons^3-6. Li & Zhou propose an elementary siphon control policy (ESCP) to reduce the redundant siphons to obtain structurally simpler controllers^9-10. However, they cannot obtain optimal ones. Reachability graph methods are used to obtain the live system behavior^11-14. Without confining to a certain class of FMS, they can provide an optimal deadlock controller by adopting the theory of regions¹⁵. 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.

Uzam¹² follows the theory of regions¹⁵ 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.¹³ propose a unique interpretation of the theory of regions and define M_F (forbidden marking), M_D (dangerous marking), M_L (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.¹⁶ adopt a combined algorithm based on siphon control and the theory of regions¹⁵. 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 regions¹⁷. Less computation is required to obtain a controller. However, as indicated by Li et al¹⁸, 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 iterations¹⁹. 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 method¹³ and redundant control places^12-13. The experimental results indicate that it is the most efficient policy amongall known ones^{12-13, 16}that 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 nets²

A Petri net (PN) is a 5-tuple N = (P, T, F, W, M₀)where P is a finite set of places; T is a finite set of transitions, with P T ≠ $$\varnothing$$ and P T =$$\varnothing$$; F $$\subseteq$$(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 M₀: P → Nis 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, M₀).

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 p•t, 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 M_ncan be reached from M₀by firing a sequence of transitions σ, this process is denoted by M [σ >M_n and satisfies the state equationM_n = M + [N]$$\overrightarrow{\sigma }$$. Here, $$\overrightarrow{\sigma }$$is a vector of non-negative integers, called a firing vector, and $$\overrightarrow{\sigma }(t)$$ indicates the algebraic sum of all occurrences of t in . The set of all reachable markings for a PN given M₀is denoted by R(N,M₀). Additionally, a definition of linearized reachability set (using the state equation) is defined as R(N,M₀)={M: M = M₀ +[N](•$$\overrightarrow{\sigma }$$)}. This definition is suitable for the incorporation of the state equation into a set of linear constraints. The markings in R(N,M₀) - R(N,M₀) are called spurious ones (with respect to the state equation)²⁰. 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,M₀), 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,M₀) 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,M₀) reachable from M₀, it is finally possible to fire t, tT through some firing sequence.(N, M₀)is said to be reversible, if MR(N,M₀), M₀R(N,M).Thus, in a reversible net it is always possible to go back to initial marking (state) M₀.A marking Mis said to be a home state, if for each marking MR(N,M₀), Mis reachable from M.Reversibility is a special case of the home state property, i.e. if the home state M= M₀, then the net is reversible.

2.2. Theory of regions and synthesis problem¹³

The theory of regions is proposed for the synthesis of pure nets given a finite TS¹⁵, which can be adopted to synthesize the liveness-enforcing net supervisor (LENS) for a plant model^12-13. For convenience, our method follows the interpretation of the theory of regions in¹³.

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, M₀), having T as its set of transitions and characterized by its incidence matrix [N](p, t) and its initial marking M₀, such that its reachability graph is G and the marking of node v is M₀. In the following, M denotes both a reachable marking and its corresponding node in G.

Consider any marking M in net (N, M₀). Because (N, M₀) is pure, Mcan be fully characterized by its corresponding incidence vector [N](p, )$${\overrightarrow{\Gamma }}_M$$ where $${\overrightarrow{\Gamma }}_M$$is the firing vector of path$${\Gamma }_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, )$${\overrightarrow{\Gamma }}_{M\to M^{\prime }}$$, (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:

$${\displaystyle \sum _{t\in T}[N](p,t)\overrightarrow{\gamma }(t)=0,\forall \gamma \in C}$$E1

where is an oriented cycle of G, $$\stackrel{\rightharpoonup }{\gamma }(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 M₀ to M. Applying (1) along the path leads to M(p) = M₀(p) + [N](p,)$${\overrightarrow{\Gamma }}_M$$. There are several paths from M₀ to M. Under the cycle equations, the product [N](p,)$${\overrightarrow{\Gamma }}_M$$ is the same for all these paths. As a result, $${\Gamma }_M$$can be arbitrarily chosen. The reachability of any marking M in G implies that

$$M(p)=M_0(p)+[N](p,\cdot ){\overrightarrow{\Gamma }}_M\ge 0,\forall M\in G$$E2

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

$$M_0(p)+[N](p,\cdot ){\overrightarrow{\Gamma }}_M+[N](p,t)\le -1$$E3

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)¹³. 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 M_D as follows.

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

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

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 (M_L), quasi-dead markings (M_Q), and dead markings (M_D).

Definition 3: The set of quasi-dead markings M_Q = {MR(N, M₀)| 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 Z_Q.

Definition 5: A zone consisting of all quasi-dead and dead markings, i.e., Z_I = Z_D Z_Q, 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., Z_L = R(N, M₀) - Z_I.

Ramadge and Wonham show that a system has the maximally permissive behavior if the system behavior equals Z_L²¹. In other words, one must remove all the markings in illegal zone (i.e. quasi-dead and dead markings) from R(N, M₀) 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 regions¹³. 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 M_L, t T, and MM_D, MM_L, 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., M_D = {MM_D | (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 (M_Q) and ending in a deadlock marking in M_D 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'M_D –M'_D.

Definition 10: Type II CMTSI : = {(M, t)|MM_L, t T, and MM_Q, MM_L, MM_D, 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. M_D = {MM_D | (M, t) , MM_Q 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 (M_D) 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 Z_Q but directly to Z_D). 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 {M_i, t_m} and {M_j, t_n} as shown in Figure 4. According to the state equation, M_i + [N](•t_m) = M_j + [N](•t_n) = M. Arranging the above equation, M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_i}$$) + [N](•t_m) = M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_j}$$) + [N](•t_n). According to (4), realizing either CMTSI, e.g., {M_i, t_m}, leads to M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_i}$$) + [N](•t_m) -1, which in turn implies M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_j}$$) + [N](•t_n) -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 MM_D, 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 {M_p, t_r} and {M_q, t_s}. M_p and M_q reaches a quasi-dead markings M' via t_r and t_s’s firing, respectively as shown in Figure 5.

According to the state equation, M_p + [N](•t_r) + [N](•$$\overrightarrow{\sigma }*$$) = M_q + [N](•t_s) + [N](•$$\overrightarrow{\sigma }*$$) M. Arranging the above equation, one can realize that M_p + [N](•t_r) =M_q + [N](•t_s). According to (4), realizing either CMTSI, e.g., {M_p, t_r}, leads to M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_p}$$) + [N](•t_r) -1, which in turn implies M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_q}$$) + [N](•t_s) -1 and vice versa. Hence, only one CMTSI needs to be controlled.

Theorem 3: A dead marking MM_D, is associated with two CMTSIs whose markings can reach two different quasi-dead markings M_p and M_q via two different single transitions’ firing. Both need to be controlled if [N](•$${\overrightarrow{\sigma }}_r{}^{*}$$) [N](•$${\overrightarrow{\sigma }}_s{}^{*}$$).

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

According to the state equation, M_p + [N](•t_r) + [N](•$${\overrightarrow{\sigma }}_r{}^{*}$$) = M_q + [N](•t_s) + [N](•$${\overrightarrow{\sigma }}_s{}^{*}$$) = M"_D. Arranging the above equation, M_p + [N](•$${\overrightarrow{\sigma }}_r{}^{*}$$) = M_q + [N](•$${\overrightarrow{\sigma }}_s{}^{*}$$). Since [N](•$${\overrightarrow{\sigma }}_r{}^{*}$$) [N](•$${\overrightarrow{\sigma }}_s{}^{*}$$), M_pis not equal to M_q. And also according to the definition of the event separation condition equation, the first set of CMTSI {M_p, t_r} leads to the first event separation condition equation is M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_p}$$) + [N](•t_r) -1; and the second set of CMTSI {M_q, t_s} leads to the another event separation condition equation is M₀ + [N](•$${\overrightarrow{\sigma }}_{M_0\to M_q}$$) + [N](•t_s) -1. Hence, one can infer that M_p and M_q are two different quasi-dead markings if [N](•$${\overrightarrow{\sigma }}_r{}^{*}$$) [N](•$${\overrightarrow{\sigma }}_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 MM_L can be led to a quasi-dead markingM_q via a single transition firing. M_qmust eventually evolve to a dead one M_d (i.e. M_dM_D) after a sequence _n = t₁t₂…t_n fires. Denote the set of all the markings on the path from M_q to M_d as M_q-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 M_P= M_q for the case shown in Figure 7.

Figure 7.

Two CMTSIs connected to two quasi-dead markings M_p and M_q with _r^* = _s^* = ^*(M_D).

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.²² (b) Its reachability graph.

Here, Figure 8(a) taken from existing literatures²² 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. M₂) and M"_D (i.e. M₁₅) and four quasi-dead markings (i.e. M₁₁, M₁₂, M₁₃ and M₁₄). Additionally, the markings M₀, M₁, M₃-M₁₀ 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 {M₀, t₂} belongs to type I CMTSI and {M₇, t₁} 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 on^12-13, the maximally permissive behavior means all of legal markings (M_L) and the number of reachability condition equations equals |M_L|. 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.¹³

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 MTSI¹³.

Figure 9.

The Proposed Deadlock Prevention Flowchart.

4. Experimentalresults

Two FMS examples are used to evaluate our deadlock prevention policy^12-23.

Figure 10.

An FMS PN Model¹².

Example I: An FMS is shown in Figure 1012. This PN is a system of simple sequential processes with resources (S³PR), denoted by (N₁, M₀). To do our deadlock prevention policy, R(N₁, M₀) of the PN system can be constructed as shown in Figure 11.

Two dead markings (i.e. M₇ and M₁₂) can then be identified. Next, '₁ = {(M₃, t₅)} and '₂ = {(M₁₅, t₁)} are obtained. The event separation condition equations can be obtained through them as follows.

M₇(p_c) = M₀(p_c) + 2[N](p_c, t₁)+ [N](p_c, t₂) + [N](p_c, t₅) -1 (5)

M₁₂(p_c) = M₀(p_c) + [N](p_c, t₁)+2[N](p_c, t₅) +[N](p_c, t₆) -1 (6)

Figure 11.

R(N, M₀) of Example I.

Two cycle equations are as follows.

[N](p_c, t₁)+[N](p_c, t₂) + [N](p_c, t₃)+ [N](p_c, t₄) = 0 (7)

[N](p_c, t₅)+[N](p_c, t₆) + [N](p_c, t₇) + [N](p_c, t₈) = 0 (8)

After listing all reachability conditions, all legal markings can be determined. In detail, M₀-M₆, M₈, and M₁₃-M₁₉ are legal. Hence, the following reachability conditions are obtained.

M₀(p_c) 0 (9)

M₁(p_c) = M₀(p_c) + [N](p_c, t₁) 0 (10)

M₂(p_c) = M₀(p_c) + [N](p_c, t₁) + [N](p_c, t₂) 0 (11)

M₃(p_c) = M₀(p_c) + 2[N](p_c, t₁)+ [N](p_c, t₂) 0 (12)

M₄(p_c) = M₀(p_c) + 2[N](p_c, t₁)+ [N](p_c, t₂) + [N](p_c, t₃) 0 (13)

M₅(p_c) = M₀(p_c) + 2[N](p_c, t₁)+ 2[N](p_c, t₂) + [N](p_c, t₃) 0 (14)

M₆(p_c) = M₀(p_c) + 3[N](p_c, t₁)+ 2[N](p_c, t₂) + [N](p_c, t₃) 0 (15)

M₈(p_c) = M₀(p_c) + [N](p_c, t₁)+ [N](p_c, t₂) + [N](p_c, t₃) 0 (16)

M₁₃(p_c) = M₀(p_c)+ [N](p_c, t₅) 0 (17)

M₁₄(p_c) = M₀(p_c) + [N](p_c, t₅) + [N](p_c, t₆) 0 (18)

M₁₅(p_c) = M₀(p_c) + 2[N](p_c, t₅) + [N](p_c, t₆) 0 (19)

M₁₆(p_c) = M₀(p_c) + 2[N](p_c, t₅) + [N](p_c, t₆) + [N](p_c, t₇) 0 (20)

M₁₇(p_c) = M₀(p_c) + 2[N](p_c, t₅) + 2[N](p_c, t₆) + [N](p_c, t₇) 0 (21)

M₁₈(p_c) = M₀(p_c) + 3[N](p_c, t₅) + 2[N](p_c, t₆) + [N](p_c, t₇) 0 (22)

M₁₉(p_c) = M₀(p_c) + [N](p_c, t₅) + [N](p_c, t₆) + [N](p_c, t₇) 0 (23)

Furthermore, two optimal control places C_P1 and C_P2 can be obtained when (5) and (7)-(23) are solved. Their detailed information is: M₀(C_P1) = 1, t₁= t₅= -1, t₂= t₆= 1, t₃= t₄= t₇= t₈ = 0; and M₀(C_P2)=1, t₂= t₅ = -1, t₃ = t₆= 1, t₁= t₄= t₇= t₈ = 0. By the same way, using (6) and (7)-(23),one can find two optimalcontrol places, C_p3 and C_p4. M₀(C_P3) = 1, t₁= t₆= -1, t₂= t₇ = 1, t₃ = t₄= t₅= t₈ = 0; and M₀(C_P4) = 1, t₁ = t₅= -1, t₂ = t₆ = 1, t₃= t₄= t₇ = t₈= 0. Notably, C_P1 and C_P4 are the same. Therefore, a redundant control place (C_P4) can be removed. As a result, the system net can be controlled with the three control places C_P1, C_P2 and C_P3. The optimally controlled system net(N_1H, M₀) 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 literatures^{12, 24}.

Additional Control Places	M0(Cpi)	(Cp)	(Cp)
Cp1	1	t2, t6	t1, t5
Cp2	1	t3, t6	t2, t5
Cp3	1	t2, t7	t1, t6

Table 1.

Control Places of the Net (N_1H, M₀)

Example II: This example is taken from²³ and is used in^{12, 16, 24}. Here, the PN model of the system, denoted as (N₂, M₀), is shown in Figure 12.

Figure 12.

The Petri nets model of example II.

To prevent deadlock, 282 reachable markings (M₁ to M₂₈₂) are identified according to the software INA²⁵. 16 dead markings M₉, M₁₉, M₇₀, M₇₁, M₇₆, M₇₇, M₇₈, M₈₃, M₈₄, M₉₄, M₉₉, M₁₀₀, M₁₀₅, M₁₀₆, M₁₁₂, and M₁₁₃ are then located. Next, 61 quasi-dead markings M₆, M₇, M₈, M₁₄, M₁₅, M₁₆, M₁₇, M₁₈, M₂₅, M₄₈, M₆₆, M₆₇, M₆₈, M₆₉, M₇₂, M₇₃, M₇₄, M₇₅, M₇₉, M₈₀, M₈₁, M₈₂, M₈₇, M₁₀₁, M₁₀₂, M₁₀₃, M₁₀₄, M₁₀₈, M₁₀₉, M₁₁₀, M₁₁₁, M₁₂₄, M₁₃₀, M₁₃₅, M₁₃₆, M₁₄₁, M₁₄₂, M₁₄₃, M₁₅₀, M₁₆₂, M₁₉₈, M₂₀₃, M₂₀₄, M₂₁₀, M₂₅₀, M₂₅₁, M₂₅₇, M₂₅₈, M₂₅₉, M₂₆₀, M₂₆₁, M₂₆₂, M₂₆₃, M₂₆₅, M₂₆₉, M₂₇₀, M₂₇₂, M₂₇₃, M₂₇₄, M₂₇₇, and M₂₇₈ 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 {(M₅₆, t₉)} in M₇₇ is a redundant one.

M(D	'C	M(D	C
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(D	Event Separation Condition Equations
M9	M0 + 3t1 + t2 + t3 + 2t9 + t10 -1
M70	M0 + 3t1 + t2 + 2t3 + 2t4+ t6 + 2t9+ t10 -1
M0 + 3t1 + 2t2 + t3 + t4 + t5 + t6 + 2t9 + t10 -1
M71	M0 + 3t1 + t2 + 2t3 + t4 + t5 + t6 + 2t9 + t10 -1
M0 + 3t1 + 2t2 + t3 + 2t5 + t6 + 2t9 + t10 -1
M78	M0 + 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
M94	M0 + 2t1 + t3 + 3t9 + 2t10 + t11 + t12 -1
M99	M0 + 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 M₉) to illustrate how to prevent legal markings from leading to dead one M₉ by using a CMTSI. To do so, '_C1 = {(M₆₅, t₁)} can be located due to M₉. The event separation condition equation can then be identified as follows.

M₉(C_P1) = M₀(C_P1) + 3t₁ + t₂ + t₃ + 2t₉ + t₁₀ -1 (24)

Next, three different cycle equations are:

t₁ + t₂ + t₅ + t₆ + t₇ + t₈ = 0 (25)

t₁ + t₃ + t₄ + t₆ + t₇ + t₈ = 0 (26)

t₉ + t₁₀ + t₁₁ + t₁₂ + t₁₃ + t₁₄ = 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 C_P1 can be computed, i.e., M₀ (C_P1) = 2, C_P1= {t₆, t₁₃}, and C_P1 = {t₁, t₁₁}. Similarly, other control places are obtained as shown in Tables 5-6.

M(D	Event Separation Condition Equations
M19	M0 + 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
M76	M0 + 2t1 + t2 + t3 + 2t9 + t10 + t11 -1
M77	M0 + 3t1 +t2 + 2t3 + t4+t6+t9+t10+t11 -1
M0 + 3t1 + 2t2 + t3+t5 + t6+t9+t10+t11 -1
M83	M0 + t1 + t2 + 2t9 + t10 + t11 -1
M84	M0 + 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
M105	M0 + t1 + t3 + 3t9 + 2t10 + 2t11 + t12 -1
M106	M0 + 2t1 + 2t3 + t4 + t6 + 3t9 + 2t10+ 2t11 + t12 -1
M0 + 2t1 + t2 + t3 + t5+ t6 + 3t9 + 2t10 + 2t11+ t12 -1
M112	M0 + 3t9 + 2t10 + 2t11+ t12 -1
M113	M0+ 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.

M(D	'C	M0(Cpi)	(Cpi)	(Cpi)
M9	{(M65, t1)}	2	t6, t13	t1, t11
M70	{(M43, t9)}	3	t6, t11	t2, t4, t9
3	t5, t7, t11	t2, t6, t9
3	t7, t11	t4, t5, t9
M71	{(M51, t9)}	3	t7, t11	t4, t5, t9
M78	{(M171, t9)}	3	t7, t11	t4, t5, t9
M94	{(M93, t1)}	2	t6, t13	t1, t11
M99	{(M98, t1)}	4	t7, t11	t1, t9
M100	{(M98, t4)}	3	t7, t11	t4, 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 in¹². It hints that 59 sets of inequalities are needed in ¹², while only 18 sets of inequalities suffice using our algorithm. Hence, our policy is more efficient than that in ¹².

Li et al. solve this problem by using elementary siphons controlled policy (ESCP) and the theory of region ¹⁶. A two-stage deadlock prevention method is used. First, ESCP is used to replace a siphon control method⁵. 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. S₁ = {p₂, p₅, p₁₃, p₁₅, p₁₈}, S₂= {p₅, p₁₃, p₁₄, p_15,p₁₈} and S₃ = {p₂, p₇, p₁₁, p₁₃, p₁₆p₁₉}) can be identified. As a result, three control places V_S1V_S3 as shown in Table 8 are needed to handle three elementary siphons. Then a partially controlled PN system, denoted as (N_2L1, M₀), can be obtained after the first stage.

M(D	C	M0(Cpi)	(Cpi)	(Cpi)
M19	{(M56, t1)}	2	t6, t13	t1, t11
4	t7, t11	t1, t9
{(M56, t9)}	3	t5, t7, t11	t2, t6, t9
4	t7, t11	t1, t9
M76	{(M65, t11)}	1	t5, t13	t2, t11
M77	{(M56, t11)}	1	t5, t13	t2, t11
M83	{(M128, t11)}	1	t5, t13	t2, t11
M84	{(M60, t9)}	3	t5, t7, t11	t2, t6, t9
{(M60, t11)}	1	t5, t13	t2, t11
M105	{(M93, t11)}	1	t5, t13	t2, t11
M106	{(M98, t11)}	1	t5, t13	t2, t11
M112	{(M122, t11)}	1	t5, t13	t2, t11
M113	{(M96, t11)}	1	t5, t13	t2, t11

Table 6.

Control Places from TYPE II CMTSI.

Additional Control Places	M0(Cpi)	(Cpi)	(Cpi)
Cp1	1	t5, t13	t2, t11
Cp2	2	t6, t13	t1, t11
Cp3	3	t6, t11	t2, t4,t9
Cp4	3	t5, t7, t11	t2, t6,t9
Cp5	3	t7, t11	t4, t5,t9
Cp6	4	t7, t11	t1, t9

Table 7.

Control Places for the Net (N_2H, M₀).

However, (N_2L1, M₀) has a dead marking. Figure 13 shows a partial reachability graph and the deadlock marking M₅₇ is included. M₅₇ is one of the 210 reachable markings (i.e. the reachable markings M₁-M₂₁₀ as denoted in¹⁶. In¹⁶, 210 reachable markings are divided into two categories: legal and illegal zones. The illegal zone consists of quasi-dead markings (i.e. M₅₄, M₅₅, M₅₆and M₆₀) and a dead marking (i.e. M₅₇). Obviously, some legal markings (i.e. M₄₃, M₄₄, M₄₇, M₄₈, M₄₉, M₅₃, M₅₉ and M₇₄) can enter the illegal zone (i.e. Z_I = Z_QZ_D). One can realize that they use the theory of regions to prevent these legal markings from entering Z_I. Therefore, they must resolve 8 MTSIs (i.e. {(M₄₃, t₉)}, {(M₄₄, t₉)}, {(M₄₇, t₉)}, {(M₄₈, t₉)}, {(M₄₉, t₉)}, {(M₅₃, t₄)}, {(M₅₉, t₁)}, {(M₇₄, t₂)}) 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 policy¹⁶ 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 (N_2L1, M₀). One can realize that M₅₇ is the only deadlock marking in R(N_2L1, M₀). Based on our method, only the dead marking M₅₇ needed to be controlled. Here, only one = {(M₄₄, t₉)} 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 ¹⁶. Hence, the proposed concept of CMTSIs can be used in their approach¹⁶ to improve its computational efficiency significantly as well.

Figure 13.

A Partial Reachability Graph of the Net (N_2L1, M₀)¹⁶.

Additional Control Places	M0(Cpi)	(Cpi)	(Cpi)
Vs1	1	t5, t13	t2, t11
Vs2	2	t4, t5, t13	t1, t11
Vs3	3	t7, t11	t4, t5,t9

Table 8.

Additional Control Places for the Net (N_2L1, M₀)

Additional Control Places	M0(Cpi)	(Cpi)	(Cpi)
Cp1	3	t6, t11	t2, t4,t9
Cp2	3	t5, t7, t11	t2, t6,t9
Cp3	4	t2, t4, t7, t11	t1,t6, t9

Table 9.

Control Places for (N_2L1, M₀) by Two-Stage Method.

5. Comparison with existing methods

One can attempt to make a comparison with the previous methods^{12, 16, 24} in terms of efficiency. The first one proposed by Uzam¹², 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 Places	MTSI; U, L, P	Control Places; U, L, P	Reachable; Markings
I	11	3	6, 6, 2	3, 3, 3	15
II	19	6	59, ,18	9, , 6	205
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 in^16,24 in a system with large reachability graphs, one can use eight different markings of p₁, p₈, p₁₅, p₁₈, and p₁₉: [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 (p₁₅), M (p₁₈), and M (p₁₉) vary; |R|, |M_L|, |R_D|^U, |R_D|^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 r_a = ||^P /||^U in Table 11, and r_b = |^P /||^L in Table 12. Notably, Algorithm G¹³ can be regarded as Algorithm U in Table 11 since the number of MTSIs and ESSPs are the same. In table 11, here, N_sep represents the number of MTSIs, and the N_sep/U,N_sep/L and N_sep/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 (p₁₅) = M (p₁₈) = M (p₁₉) = 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.

cases	|R|	|ML|	|RD|^U	|(|^U	|(|^P	ra
1	282	205	16	59	18	30.5%
2	600	484	27	95	28	29.5%
3	972	870	26	103	26	25.2%
4	570	421	16	107	19	17.8%
5	4011	3711	42	288	42	14.6%
6	27152	26316	84	886	84	9.5%
7	124110	122235	145	2115	145	6.9%
8	440850	437190	228	4311	228	5.3%

Table 11.

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

case	|R|	|ML|	|RD|^L	|(|^L	|(|^P	rb
1	282	205	1	8	1	12.5%
2	600	484	1	8	1	12.5%
3	972	870	6	10	6	60.0%
4	570	421	1	8	1	12.5%
5	4011	3711	9	15	9	60.0%
6	27152	26316	28	48	28	58.3%
7	124110	122235	60	105	60	57.1%
8	440850	437190	108	192	108	56.3%

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 (p₁₅) = M (p₁₈) = M (p₁₉) = 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 in^{12, 16}. In conclusion, Algorithm Pis more efficient in large reachability graph cases than those in^12-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 policies^{12-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.

Acknowledgement

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.