Sage Journals: Discover world-class research

Abstract

Most existing deadlock prevention policies deal with deadlock problems arising in flexible manufacturing systems modeled with Petri nets by adding control places. Based on the reachability graph analysis, this article proposes a novel deadlock control policy that recovers the system from deadlock and livelock states to legal states and reaches the same number of states as the original plant model by adding control transitions. In order to reduce the structural complexity of the supervisor, a set covering approach is developed to minimize the number of control transitions. Finally, two flexible manufacturing system examples are presented to illustrate the proposed approach.

Keywords

Petri net flexible manufacturing system deadlock control deadlock prevention supervisor control transition

Introduction

Flexible manufacturing systems (FMSs) are widely used to produce various workpieces using machines, robots, and automated guided vehicles, which are recognized as shared resources. Deadlocks¹ may occur due to the competition for the limited shared resources among concurrently executed processes, and they greatly decrease the efficiency of the system. Therefore, it is necessary to analyze and control deadlocks in FMSs.

Petri nets^2,3 are suitable to model and analyze FMSs due to their compact and graphical representation. Based on Petri nets, a lot of policies to deal with deadlock problems^4–19 have been developed. Generally, there are mainly two Petri net analysis techniques used to deal with deadlock prevention: structure analysis^7,8,19–25 and reachability graph analysis.^15,26–30 The former always derives a deadlock prevention policy based on special structural objects of a Petri net such as siphons or resource-transition circuits. In general, the derived supervisor is simple but suboptimal. The latter can obtain a very highly or even maximally permissive supervisor. However, its computation is always expensive.

Uzam and Zhou¹⁵ propose an iterative synthesis approach for deadlock prevention in FMSs. At each iteration, a first-met bad marking (FBM) is singled out and a control place is designed to prevent this FBM from being reached using a well-established invariant-based method.³¹ This process is followed until the net becomes live. Although this method is easy to use, it cannot guarantee the optimality of the supervisor.

Chen et al.⁵ present an efficient method to design optimal supervisor such that all FBMs are forbidden and all legal markings are reachable. To overcome the inefficiency of state enumeration by the traditional methods, binary decision diagrams (BDD) are provided for the computation of the reachability graph.

Huang et al.³² propose an approach by adding control transitions to the plant net, which can convert the dead markings into live ones. The approach has more permissive markings than the existing place–based ones. However, there is no formalized algorithm to compute the control transitions and the minimum of control transitions that are needed to add is not considered.

Motivated by the work in Huang et al.,³² this article proposes a novel deadlock control policy to design control transitions based on the reachability graph analysis and adds the control transitions to the plant net which can recover all deadlock and livelock markings to legal ones. A set covering technique is developed to derive the minimal set of control transitions. Finally, the controlled system becomes live by adding the minimal set of control transitions to the plant net.

The remainder of this article is organized as follows. Section “Preliminaries” briefly reviews the preliminaries used throughout this article. Section “Computation of control transitions” discusses the computation of the minimal set of control transitions using a set covering technique. Section “Transition-based deadlock control policy” presents a deadlock control policy that is shaped into an algorithm. An explanatory example is illustrated in section “An illustrative example.” Section “Experimental studies” provides some experimental results. Finally, section “Conclusion” concludes this article.

Preliminaries

Basics of Petri nets

A Petri net^2,3 is a four tuple $N = (P, T, F, W)$ , where P and T are finite, nonempty, and disjoint sets. P is the set of places, and T is the set of transitions with $P \cup T \neq \emptyset$ and $P \cap T = \emptyset$ . $F \subseteq (P \times T) \cup (T \times P)$ is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. $W : (P \times T) \cup (T \times P) \to ℕ$ is a mapping that assigns a weight to an arc: $W (x, y) > 0$ if $(x, y) \in F$ , and $W (x, y) = 0$ otherwise, where $x, y \in P \cup T$ and $ℕ = {0, 1, 2, \dots}$ is a set of non-negative integers.

Given a node $x \in P \cup T$ , the preset of x is defined as ${}^{•}x = {y \in P \cup T | (y, x) \in F}$ , and the post-set of x is defined as $x^{•} = {y \in P \cup T | (x, y) \in F}$ .

A marking M of a Petri net N is a mapping from P to $ℕ$ . The number of tokens in place p at M is denoted by $M (p)$ . Markings are usually represented using a multiset or formal sum notation for economy of space. As a result, a marking M denoted by $\sum_{p \in P} M (p) p$ . $(N, M_{0})$ is called a net system or a marked Petri net, and $M_{0}$ is called an initial marking of N.

A transition $t \in T$ is enabled at a marking M if $\forall p \in^{•} t$ , $M (p) \geq W (p, t)$ . This fact is denoted as $M [t 〉$ . Firing t yields a new marking $M'$ , which is denoted as $M [t 〉 M'$ . Marking $M'$ is said to be immediately reachable from M. Marking $M ″$ is said to be reachable from M if there exist a sequence of transitions $σ = t_{0} t_{1}, \dots, t_{n}$ and markings $M_{1}, M_{2}, \dots,$ and $M_{n}$ such that $M [t_{0} 〉 M_{1} [t_{1} 〉 M_{2}, \dots, M_{n} [t_{n} 〉 M ″$ holds. The set of markings reachable from $M_{0}$ is called the reachability set of Petri net $(N, M_{0})$ and denoted as $R (N, M_{0})$ . $[N]$ is called the incidence matrix of N. It is a $| P | \times | T |$ integer matrix with $[N] (p, t) = W (t, p) - W (p, t)$ .

A Petri net N is bounded if $\exists k \in ℕ^{+}$ , $\forall M \in R (N, M_{0})$ , $\forall p \in P$ , $M (p) ⩽ k$ , where $ℕ^{+}$ denotes the set of positive integers. A Petri net N is pure (self-loop free) if $\forall x, y \in P \cup T$ , $W (x, y) > 0$ implies $W (y, x) = 0$ .

For a transition $t \in T$ , its incidence vector, a column in N is denoted by $[N] (\cdot, t)$ . Let M and $M'$ be two markings in $R (N, M_{0})$ with $M [t 〉 M'$ . It is trivial that $M' = M + [N] (\cdot, t)$ , and the incidence vector of t can be represented by $N_{t} = [N] (\cdot, t) = [N]^{+} (\cdot, t) - [N]^{-} (\cdot, t) = M' - M$ . Accordingly, the enabling condition of t at M can be written as $M \geq [N]^{-} (\cdot, t)$ .

Given a Petri net $(N, M_{0})$ , $t \in T$ is live at $M_{0}$ if $\forall M \in R (N, M_{0})$ , $\exists M' \in R (N, M)$ , $M' [t 〉$ . $(N, M_{0})$ is live if $\forall t \in T$ , t is live at $M_{0}$ . $(N, M_{0})$ is dead at $M_{0}$ if $∄ t \in T$ , $M_{0} [t 〉$ . $(N, M_{0})$ is deadlock free if $\forall M \in R (N, M_{0})$ , $\exists t \in T$ , $M [t 〉$ .

Reachability graph

Let $G (N, M_{0})$ be the reachability graph of a bounded Petri net N. For deadlock control purpose, markings in the reachability graph can be divided into four groups: good, dangerous, bad, and deadlock ones.¹⁵ A deadlock one has no successor which indicates a dead state. A bad one has successors but cannot reach the initial marking. A good one can reach the initial marking, and its successors also can reach the initial one. A dangerous one is the one that can reach the initial one, but at least one of its successors cannot reach the initial one.

For a Petri net $(N, M_{0})$ , the set of legal markings is formally defined as $M_{L} = {M | M \in R (N, M_{0}) \land M_{0} \in R (N, M)}$ . The set of deadlock markings is defined as $M_{D} = {M | M \in R (N, M_{0}) \land ∄ t \in T : M [t 〉}$ .

Computation of control transitions

This section develops an approach to obtain control transitions based on the reachability graph analysis.

Definition 1

Let $M_{D}$ be the set of deadlock markings and $M' \in M_{D}$ be a deadlock marking. A marking is said to be a livelock marking if it has successors, but cannot reach the initial marking or a deadlock marking. The set of livelock markings is defined as $ℳ_{L L} = {M | M \in R (N, M_{0}) \land M \notin ℳ_{D} \land M_{0} \notin R (N, M) \land M^{'} \notin R (N, M)}$ .

Deadlocks arise due to the existence of deadlock or livelock markings in $G (N, M_{0})$ of N. The control goal is to recover the deadlock and livelock markings to legal ones by adding control transitions to the plant net without introducing extra marking to the controlled system.

Let $[N]$ be the incidence matrix of a pure plant net N. The incidence matrix corresponding to control transitions is represented by $[N_{c}]$ that describes the arcs connecting control transitions and the places in the plant net. Therefore, the incidence matrix of the controlled system $[N_{s}]$ can be represented by $[N_{s}] = [N N_{c}]$ .

For a pure Petri net, its incidence matrix can completely determine its structure. Therefore, the critical question is to define the incidence vectors of added control transitions. In this article, we introduce the projection functions as follows.

Let X be a vector. $P^{+} (X) : X \to X^{+}$ , where $X^{+} (i) = 0$ , if $X (i) < 0$ ; otherwise, $X^{+} (i) = X (i)$ . $P^{-} (X) : X \to X^{-}$ , where $X^{-} (i) = 0$ , if $X (i) > 0$ ; otherwise, $X^{-} (i) = X (i)$ .

To recover the deadlock and livelock markings to legal ones and reach the same number of markings as the plant net, the added control transitions should be enabled at deadlock or livelock markings but disabled at other markings. The firing of control transitions would yield the corresponding legal markings in $M_{L}$ but does not introduce any new markings to the controlled system. Therefore, the definition of the set of control transitions is presented as follows.

Definition 2

Let $(N, M_{0})$ be a pure Petri net, $M_{L}$ , $M_{LL}$ , and $M_{D}$ be the sets of legal, livelock, and deadlock markings in $R (N, M_{0})$ , respectively. Given a deadlock or livelock marking $M_{D} \in M_{D} \cup M_{LL}$ . The set of control transitions that can recover $M_{D}$ to legal markings in $M_{L}$ can be represented by the set of their incidence vectors $T_{C} (M_{D}) = {N_{t} | N_{t} = M - M_{D} = N_{t}^{+} - N_{t}^{-} \land M_{D} [t 〉 M \land M \in ℳ_{L} \land ∄ M^{'} \in R (N, M_{0}) \ {ℳ_{D} \cup ℳ_{L L}} : M^{'} [t 〉}$ , where $N_{t}^{+} = P^{+} (N_{t})$ and $N_{t}^{-} = P^{-} (N_{t})$ are the input incidence and output incidence vector of control transition t, respectively.

To obtain a live controlled system, all the deadlock and livelock markings in $M_{D} \cup M_{LL}$ need to be recovered to legal ones. According to Definition 2, the set of control transitions for a deadlock or livelock marking $M_{D} \in M_{D} \cup M_{LL}$ can be obtained, where firing any control transition in $T_{C} (M_{D})$ can recover $M_{D}$ to a legal one. Then, all the sets of control transitions that can recover all deadlock or livelock markings to legal ones can be derived. In order to show the method of computing of control transitions clearly, the following new notations are introduced: $T_{C} = {T_{C} (M_{D}) | M_{D} \in M_{D} \cup M_{LL}}$ , $T_{C} = \cup_{M_{D} \in M_{D} \cup M_{LL}} T_{C} (M_{D})$ , where $T_{C}$ is the set of all sets of control transitions for all deadlock and livelock markings, and $T_{C}$ is the set of all the control transitions.

In what follows, an algorithm to compute the set of all sets of control transitions for all deadlock and livelock markings $T_{C}$ is presented. First, the sets of legal, deadlock, and livelock markings are generated based on the reachability graph analysis. Then, for each deadlock or livelock marking $M_{D_{i}} \in M_{D} \cup M_{LL}$ , the set of control transitions $T_{C} (M_{D_{i}})$ that can recover $M_{D_{i}}$ to legal markings can be obtained. And adding any control transition in $T_{C} (M_{D_{i}})$ can recover $M_{D_{i}}$ to a legal marking. Finally, the set of all sets of control transitions for all deadlock and livelock markings $T_{C}$ can be generated.

Algorithm 2 presents the method to calculate the set of all control transitions $T_{C}$ . There is no need to add all control transitions in $T_{C}$ since multiple deadlock and livelock markings may be recovered to legal ones by the same control transition. In this case, a set covering problem (SCP) is formulated to model the optimal selection of the control transitions to be added, that is to say, to minimize the number of control transitions, which reduces the size of the obtained control subnet.

Algorithm 1.

Computation of the set of all sets of control transitions for all deadlock and livelock markings $T_{C}$ .

Input: A pure and bounded Petri net model

(N, M_{0})

Output: The set of all the sets of control transitions for all deadlock and livelock markings

T_{C}

1. Compute the reachability graph of

(N, M_{0})

2. Compute the set of legal makings

M_{L}

R (N, M_{0})

3. Compute the set of deadlock makings

M_{D}

R (N, M_{0})

4. Compute the set of livelock makings

M_{LL}

R (N, M_{0})

T_{C} : = {\emptyset}

6. for {each

M_{D_{i}} \in M_{D} \cup M_{LL}

} do

T_{C} (M_{D_{i}}) : = \emptyset

. /*

T_{C} (M_{D_{i}})

is used to denote the set of control transitions that can recover

M_{D_{i}}

to legal markings.

for {each

M_{L_{j}} \in M_{L}

} do

T_{C_{ij}} : = M_{L_{j}} - M_{D_{i}}

. /*

T_{C_{ij}}

is used to denote the control transition that can recover

M_{D_{i}}

M_{L_{j}}

. */

T_{C_{ij}}^{+} : = P^{+} (T_{C_{ij}})

. /*

T_{C_{ij}}^{+}

is used to denote the input incidence vector of

T_{C_{ij}}

. */

T_{C_{ij}}^{-} : = P^{-} (T_{C_{ij}})

. /*

T_{C_{ij}}^{-}

is used to denote the output incidence vector of

T_{C_{ij}}

. */

for {each

M \in R (N, M_{0}) \ {M_{D} \cup M_{LL}}

} do

flag : = 0

if {

M \geq T_{C_{ij}}^{-}

} then

flag : = 1

, break.

end if

end for

if {

flag = = 0

} then

T_{C} (M_{D_{i}}) : = T_{C} (M_{D_{i}}) \cup {T_{C_{ij}}}

end if

end for

T_{C} : = T_{C} \cup {T_{C} (M_{D_{i}})}

end for

7. Output

T_{C}

8. End.

Algorithm 2.

Computation the set of all control transitions $T_{C}$ .

Input: The set of all sets of control transitions for all deadlock and livelock markings

T_{C}

Output: The set of all control transitions

T_{C}

T_{C} : = \emptyset

2. for {each

T_{C} (M_{D_{i}}) \in T_{C}

} do/*

T_{C} (M_{D_{i}})

is used to denote the set of control transitions that can recover

M_{D_{i}}

to legal markings. */

T_{C} : = T_{C} \cup T_{C} (M_{D_{i}})

end for

3. Output

T_{C}

4. End.

The following SCP^33,34 can be employed to find a minimum cardinality of control transitions.

Let $T_{C}$ be the set of all sets of control transitions for all deadlock and livelock markings, $T_{C} (M_{D_{i}})$ be the set of control transitions for a deadlock or livelock marking $M_{D_{i}}$ , and $T_{C}$ be the set of all the control transitions, where $m = | T_{C} |$ and $n = | T_{C} |$ . Let $A = (a_{ij})$ be a binary $m \times n$ matrix, such that $a_{ij} = 1$ if $T_{j} \in T_{C} (M_{D_{i}})$ , and $a_{ij} = 0$ otherwise.

SCP:

{\begin{matrix} \min \sum_{j = 1}^{n} x_{j} \\ subjected to \\ \sum_{j = 1}^{n} a_{ij} x_{j} \geq 1, i = 1, \dots, m \\ x_{j} \in {0, 1}, j = 1, \dots, n \end{matrix}

(1)

The objective function represents the minimal number of control transitions. Solving this SCP, an optimal solution $x^{*}$ and the corresponding minimal set of control transitions $T_{C}^{*} = {T_{j} \in T_{C} | x_{j}^{*} = 1}$ are obtained.

Transition-based deadlock control policy

This section presents a deadlock control policy by which a live controlled system with a minimal set of control transitions can be obtained.

Theorem 1

$(N_{1}, M_{0})$ resulting from Algorithm 3 is a live controlled system for the Petri net model $(N, M_{0})$ .

Algorithm 3.

Transition-based deadlock control policy.

Input: A pure and bounded Petri net model

(N, M_{0})

Output: A live controlled system

(N_{1}, M_{0})

with a minimal set of control transitions.

1. Compute the set of all sets of control transitions for all deadlock and livelock markings

T_{C}

by Algorithm 1.

2. Compute set of all control transitions

T_{C}

by Algorithm 2.

3. Solve the SCP proposed in section “Computation of Control Transitions,” and obtain the corresponding minimal set of control transitions

T_{C}^{*}

4. Add all the control transitions in

T_{C}^{*}

to the plant net.

5. Output

(N_{1}, M_{0})

6. End.

Proof

Each control transition in $T_{C}^{*}$ satisfies Definition 2 and can recover at least one deadlock or livelock marking to a legal one. By solving the SCP proposed in section “Computation of Control Transitions,” the obtained minimal set of control transitions can recover all the deadlock and livelock markings to legal ones. Therefore, by adding the minimal set of control transitions, all deadlock and livelock markings can reach the initial marking. Then, all bad and deadlock markings can reach the initial marking, that is to say, all reachable markings of the controlled system can reach the initial marking, which implies that the controlled system is live.

An illustrative example

In this section, an FMS example is used to illustrate the proposed deadlock control policy that can obtain a live controlled system with a minimal set of control transitions.

The Petri net model of an FMS shown in Figure 1 is considered to illustrate the proposed deadlock control policy. It is a pure and bounded Petri net. In the net, there are 13 places and 10 transitions. Figure 2 shows that the net has 32 reachable markings, 28 of which are legal markings depicted in solid lines and 4 of which are deadlock one depicted in dashed lines. The set of deadlock markings is $ℳ_{D} = {M_{D_{1}} = 2 p_{0} + p_{5} + p_{6} + p_{8} + p_{9}, M_{D_{2}} = p_{0} + p_{2} + p_{6} + p_{8} + p_{9}, M_{D_{3}} = p_{2} + p_{3} + p_{8} + p_{9}, M_{D_{4}} = p_{0} + p_{3} + p_{5} + p_{8} + p_{9}}$ . The set of livelock markings is $M_{LL} = \emptyset$ . Thus, only deadlock markings are considered to derive the control transitions.

Figure 1.

A Petri net model $(N, M_{0})$ .

Figure 2.

Reachability graph of the Petri net in Figure 1.

First, by Algorithm 1, the sets of control transitions of all deadlock and livelock markings are obtained. The sets of control transitions, denoted by $T_{C} (M_{D_{i}})$ that can recover $M_{D} \in M_{D} \cup M_{LL}$ with $i \in {1, 2, 3, 4}$ to legal ones, are, respectively, shown in Tables 1 –4, where the first column is the index number i, second and third columns represent pre-places $({{}^{•}t}_{c_{i}})$ and post-places $(t_{c_{i}}^{•})$ of control transition $t_{c_{i}}$ , respectively. It is easy to see that there are 14 control transitions in $T_{C} (M_{D_{i}})$ , where firing any control transition in $T_{C} (M_{D_{i}})$ can recover $M_{D_{i}}$ to a legal one.

Table 1.

Control transitions in $T_{C} (M_{D_{1}})$ .

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${p_{8}, p_{9}}$	${2 p_{7}, p_{11}, p_{12}}$
2	${p_{0}, p_{8}, p_{9}}$	${p_{1}, 2 p_{7}, p_{11}}$
3	${p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, 2 p_{7}, p_{11}, p_{12}}$
4	${2 p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{1}, p_{2}, 2 p_{7}, p_{11}}$
5	${2 p_{0}, p_{5}, p_{6}, p_{8}, p_{9}}$	${p_{2}, p_{3}, 2 p_{7}, p_{11}, p_{12}}$
6	${2 p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{4}, 2 p_{7}, p_{11}}$
7	${p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, 2 p_{7}, p_{11}, p_{12}}$
8	${2 p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{1}, p_{3}, 2 p_{7}, p_{11}}$
9	${p_{0}, p_{8}, p_{9}}$	${p_{4}, 2 p_{7}, p_{11}}$
10	${p_{8}, p_{9}}$	${p_{7}, p_{10}, p_{11}}$
11	${p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{7}, p_{10}, p_{11}}$
12	${2 p_{0}, p_{5}, p_{6}, p_{8}, p_{9}}$	${p_{2}, p_{3}, p_{7}, p_{10}, p_{11}}$
13	${p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{7}, p_{10}, p_{11}}$
14	${2 p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{4}, 2 p_{7}, p_{11}}$

Table 2.

Control transitions in $T_{C} (M_{D_{2}})$ .

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${p_{2}, p_{8}, p_{9}}$	${p_{0}, p_{5}, 2 p_{7}, p_{11}, p_{12}}$
2	${p_{2}, p_{8}, p_{9}}$	${p_{1}, p_{5}, 2 p_{7}, p_{11}}$
3	${p_{8}, p_{9}}$	${2 p_{7}, p_{11}, p_{12}}$
4	${p_{0}, p_{8}, p_{9}}$	${p_{1}, 2 p_{7}, p_{11}}$
5	${p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, 2 p_{7}, p_{11}, p_{12}}$
6	${p_{0}, p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{4}, p_{5}, 2 p_{7}, p_{11}}$
7	${p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{5}, 2 p_{7}, p_{11}, p_{12}}$
8	${p_{0}, p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{1}, p_{3}, p_{5}, 2 p_{7}, p_{11}}$
9	${p_{2}, p_{8}, p_{9}}$	${p_{4}, p_{5}, 2 p_{7}, p_{11}}$
10	${p_{2}, p_{8}, p_{9}}$	${p_{0}, p_{5}, p_{7}, p_{10}, p_{11}}$
11	${p_{8}, p_{9}}$	${p_{7}, p_{10}, p_{11}}$
12	${p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{7}, p_{10}, p_{11}}$
13	${p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{5}, p_{7}, p_{10}, p_{11}}$
14	${p_{0}, p_{8}, p_{9}}$	${p_{4}, 2 p_{7}, p_{11}}$

Table 3.

Control transitions in $T_{C} (M_{D_{3}})$ .

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${p_{2}, p_{3}, p_{8}, p_{9}}$	${2 p_{0}, p_{5}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
2	${p_{2}, p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{1}, p_{5}, p_{6}, 2 p_{7}, p_{11}}$
3	${p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
4	${p_{3}, p_{8}, p_{9}}$	${p_{1}, p_{6}, 2 p_{7}, p_{11}}$
5	${p_{8}, p_{9}}$	${2 p_{7}, p_{11}, p_{12}}$
6	${p_{2}, p_{8}, p_{9}}$	${p_{4}, p_{5}, 2 p_{7}, p_{11}}$
7	${p_{2}, p_{8}, p_{9}}$	${p_{0}, p_{5}, 2 p_{7}, p_{11}, p_{12}}$
8	${p_{2}, p_{8}, p_{9}}$	${p_{1}, p_{5}, 2 p_{7}, p_{11}}$
9	${p_{2}, p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{4}, p_{5}, p_{6}, 2 p_{7}, p_{11}}$
10	${p_{2}, p_{3}, p_{8}, p_{9}}$	${2 p_{0}, p_{5}, p_{6}, p_{7}, p_{10}, p_{11}}$
11	${p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{6}, p_{7}, p_{10}, p_{11}}$
12	${p_{8}, p_{9}}$	${p_{7}, p_{10}, p_{11}}$
13	${p_{2}, p_{8}, p_{9}}$	${p_{0}, p_{5}, p_{7}, p_{10}, p_{11}}$
14	${p_{3}, p_{8}, p_{9}}$	${p_{4}, p_{6}, 2 p_{7}, p_{11}}$

Table 4.

Control transitions in $T_{C} (M_{D_{4}})$ .

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
2	${p_{3}, p_{8}, p_{9}}$	${p_{1}, p_{6}, 2 p_{7}, p_{11}}$
3	${p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
4	${p_{0}, p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{1}, p_{2}, p_{6}, 2 p_{7}, p_{11}}$
5	${p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, 2 p_{7}, p_{11}, p_{12}}$
6	${p_{0}, p_{8}, p_{9}}$	${p_{4}, 2 p_{7}, p_{11}}$
7	${p_{8}, p_{9}}$	${2 p_{7}, p_{11}, p_{12}}$
8	${p_{0}, p_{8}, p_{9}}$	${p_{1}, 2 p_{7}, p_{11}}$
9	${p_{3}, p_{8}, p_{9}}$	${p_{4}, p_{6}, 2 p_{7}, p_{11}}$
10	${p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{6}, p_{7}, p_{10}, p_{11}}$
11	${p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{6}, p_{7}, p_{10}, p_{11}}$
12	${p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{7}, p_{10}, p_{11}}$
13	${p_{8}, p_{9}}$	${p_{7}, p_{10}, p_{11}}$
14	${p_{0}, p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{4}, p_{6}, 2 p_{7}, p_{11}}$

Second, by Algorithm 2, the set of all control transitions is obtained. Table 5 shows the set of all the control transitions $T_{C}$ , where the first column is the index number i, second and third columns represent pre-places $(^{•} t_{c_{i}})$ and post-places $(t_{c_{i}}^{•})$ of control transition $t_{c_{i}}$ , respectively. It is shown that there are 34 control transitions in $T_{C}$ .

Table 5.

Control transitions in $T_{C}$ .

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${p_{8}, p_{9}}$	${2 p_{7}, p_{11}, p_{12}}$
2	${p_{0}, p_{8}, p_{9}}$	${p_{1}, 2 p_{7}, p_{11}}$
3	${p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, 2 p_{7}, p_{11}, p_{12}}$
4	${2 p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{1}, p_{2}, 2 p_{7}, p_{11}}$
5	${2 p_{0}, p_{5}, p_{6}, p_{8}, p_{9}}$	${p_{2}, p_{3}, 2 p_{7}, p_{11}, p_{12}}$
6	${2 p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{4}, 2 p_{7}, p_{11}}$
7	${p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, 2 p_{7}, p_{11}, p_{12}}$
8	${2 p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{1}, p_{3}, 2 p_{7}, p_{11}}$
9	${p_{0}, p_{8}, p_{9}}$	${p_{4}, 2 p_{7}, p_{11}}$
10	${p_{8}, p_{9}}$	${p_{7}, p_{10}, p_{11}}$
11	${p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{7}, p_{10}, p_{11}}$
12	${2 p_{0}, p_{5}, p_{6}, p_{8}, p_{9}}$	${p_{2}, p_{3}, p_{7}, p_{10}, p_{11}}$
13	${p_{0}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{7}, p_{10}, p_{11}}$
14	${2 p_{0}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{4}, 2 p_{7}, p_{11}}$
15	${p_{2}, p_{8}, p_{9}}$	${p_{0}, p_{5}, 2 p_{7}, p_{11}, p_{12}}$
16	${p_{2}, p_{8}, p_{9}}$	${p_{1}, p_{5}, 2 p_{7}, p_{11}}$
17	${p_{0}, p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{4}, p_{5}, 2 p_{7}, p_{11}}$
18	${p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{5}, 2 p_{7}, p_{11}, p_{12}}$
19	${p_{0}, p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{1}, p_{3}, p_{5}, 2 p_{7}, p_{11}}$
20	${p_{2}, p_{8}, p_{9}}$	${p_{4}, p_{5}, 2 p_{7}, p_{11}}$
21	${p_{2}, p_{8}, p_{9}}$	${p_{0}, p_{5}, p_{7}, p_{10}, p_{11}}$
22	${p_{2}, p_{6}, p_{8}, p_{9}}$	${p_{3}, p_{5}, p_{7}, p_{10}, p_{11}}$
23	${p_{2}, p_{3}, p_{8}, p_{9}}$	${2 p_{0}, p_{5}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
24	${p_{2}, p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{1}, p_{5}, p_{6}, 2 p_{7}, p_{11}}$
25	${p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
26	${p_{3}, p_{8}, p_{9}}$	${p_{1}, p_{6}, 2 p_{7}, p_{11}}$
27	${p_{2}, p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{4}, p_{5}, p_{6}, 2 p_{7}, p_{11}}$
28	${p_{2}, p_{3}, p_{8}, p_{9}}$	${2 p_{0}, p_{5}, p_{6}, p_{7}, p_{10}, p_{11}}$
29	${p_{3}, p_{8}, p_{9}}$	${p_{0}, p_{6}, p_{7}, p_{10}, p_{11}}$
30	${p_{3}, p_{8}, p_{9}}$	${p_{4}, p_{6}, 2 p_{7}, p_{11}}$
31	${p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{6}, 2 p_{7}, p_{11}, p_{12}}$
32	${p_{0}, p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{1}, p_{2}, p_{6}, 2 p_{7}, p_{11}}$
33	${p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{6}, p_{7}, p_{10}, p_{11}}$
34	${p_{0}, p_{3}, p_{5}, p_{8}, p_{9}}$	${p_{2}, p_{4}, p_{6}, 2 p_{7}, p_{11}}$

There is no need to add all control transitions in $T_{C}$ to the plant net since multiple deadlock and livelock markings may be recovered to legal ones by the same control transition.

Third, the minimal set of control transitions $T_{C}^{*}$ can be derived by the following SCP

\min x_{1} + x_{2} + \dots + x_{34}

subject to

x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} \geq 1

x_{1} + x_{2} + x_{7} + x_{9} + x_{10} + x_{13} + x_{15} + x_{16} + x_{17} + x_{18} + x_{19} + x_{20} + x_{21} + x_{22} \geq 1

x_{1} + x_{10} + x_{15} + x_{16} + x_{20} + x_{21} + x_{23} + x_{24} + x_{25} + x_{26} + x_{27} + x_{28} + x_{29} + x_{30} \geq 1

\begin{array}{l} x_{1} + x_{2} + x_{3} + x_{9} + x_{10} + x_{11} + x_{25} + x_{26} + x_{29} + x_{30} + x_{31} + x_{32} + x_{33} + x_{34} \geq 1 \\ x_{j} \in {0, 1}, \forall j \in {1, 2 \dots, 34} \end{array}

Solving the above integer linear programming problem gives $\min = 1$ , where $x_{1} = 1$ and the others are zero. The corresponding minimal set of control transitions is $T_{C}^{*} = {t_{c_{1}}}$ , where there is totally only one control transition need to be added, as shown in Table 6, where the first column is the selected control transition number i in $T_{C}$ , second and third columns indicate pre-places $({{}^{•}t}_{c_{i}})$ and post-places $(t_{c_{i}}^{•})$ of control transition $t_{c_{i}}$ , respectively. Adding the control transition $t_{c_{1}}$ to the plant net, as shown in Figure 3, the resulting net is live with 32 reachable markings, all of which are legal ones, as shown in Figure 4, where the introduced arcs from deadlock markings to legal markings are depicted in dashed lines. It is easy to verify that this deadlock control policy maintains all the reachable markings of the plant net without introducing extra markings to the controlled system, that is to say, the controlled system remains to be able to reach the same number of markings as the plant net. It is sure to have more permissive markings than the existing deadlock prevention polices that prohibit the illegal markings.

Table 6.

Minimal set of control transitions of the net shown in Figure 1.

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${p_{8}, p_{9}}$	${2 p_{7}, p_{11}, p_{12}}$

Figure 3.

A controlled system of the net shown in Figure 1.

Figure 4.

Reachability graph of the controlled system shown in Figure 3.

Note that the solution of the above integer linear programming problem is not unique. Resolving it, another solution that $\min = 1$ is obtained, where $x_{10} = 1$ and the others are zero. The corresponding minimal set of control transitions is $T_{C}^{*} = {t_{c_{10}}}$ , where there is totally only one control transition needed to be added, as shown in Table 7, where the first column is the selected control transition number i in $T_{C}$ , the second and third columns indicate pre-places $(^{•} t_{c_{i}})$ and post-places $(t_{c_{i}}^{•})$ of control transition $t_{c_{i}}$ , respectively. Adding $t_{c_{10}}$ to the plant net, as shown in Figure 5, the resulting net is live with also 32 legal markings, the reachability graph of which is shown in Figure 6, where the introduced arcs from deadlock markings to legal markings are also depicted in dashed lines. This represents that the control transition $t_{c_{10}}$ can lead to a live controlled system that can reach the same number of markings as the plant net, which has the same control result as the control transition $t_{c_{1}}$ .

Table 7.

Another minimal set of control transitions of the net shown in Figure 1.

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
10	${p_{8}, p_{9}}$	${p_{7}, p_{10}, p_{11}}$

Figure 5.

Another controlled system of the net shown in Figure 1.

Figure 6.

Reachability graph of the controlled system shown in Figure 5.

Experimental studies

This section provides some experimental results of the proposed deadlock control policy.

The Petri net model of an FMS is shown in Figure 7. It is an S³PR taken from Ezpeleta et al.⁷ There are 15 places and 11 transitions. It has 261 reachable markings, 232, 3, and 1 of which are legal, livelock, and deadlock, respectively. Using the proposed method, the minimal set of control transitions that can recover all deadlock and livelock markings to legal ones are derived, which is shown in Table 8, where the first column is the index number i, second and third columns indicate pre-places $(^{•} t_{c_{i}})$ and post-places $(t_{c_{i}}^{•})$ of control transition $t_{c_{i}}$ , respectively. Adding the minimal set of control transitions to the plant net, the resulting net is shown in Figure 8, which is live with 261 reachable markings. Table 9 shows the performance comparison of some deadlock control policies in the literature for this example. It is obvious that the proposed method leads to a supervisor with more permissive behavior compared with other policies. A total of 261 markings are retained to the live controlled system.

Figure 7.

A Petri net model $(N, M_{0})$ of an FMS.

Table 8.

Minimal set of control transitions of the net shown in Figure 7.

i	${{}^{•}t}_{c_{i}}$	$t_{c_{i}}^{•}$
1	${2 p_{3}, p_{5}, 2 p_{8}}$	${p_{1}, 2 p_{6}, p_{9}, p_{10}, p_{12}, p_{13}}$
2	${p_{4}, 2 p_{8}}$	${3 p_{10}, p_{13}, 2 p_{14}}$

Figure 8.

Controlled system of the net shown in Figure 7.

Table 9.

Performance comparison of some deadlock policies for the net in Figure 7.

Control policies	Control places	Control transitions	Reachable markings
Ezpeleta et al.⁷	3	–	155
Li et al.¹⁹	3	–	155
Uzam and Zhou²⁸	3	–	232
Proposed method	–	2	261

Conclusion

This article presents a novel deadlock control policy to derive a live controlled system by adding control transitions instead of control places to the plant net. The application scope of the proposed method is limited to pure and bounded Petri net models of FMSs. This transition-based method is novel and much different from the existing place–based deadlock prevention policies. The proposed policy is sure to have more permissive markings than the existing place–based policies, although it is still NP-hard since the reachability graph analysis is needed. Future work will focus on how to reduce the computational burden of the proposed policy.

Footnotes

Academic Editor: ZhiWu Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China under grant no. 61374068, the Fundamental Research Funds for the Central Universities under grant no. XJS15039, and the Scientific and Technological Research Council of Turkey under grant no. TÜBİTAK-112M229.

References

Zhou

MC.

Deadlock control of automated manufacturing systems based on Petri nets—a literature review. IEEE T Syst Man Cy C 2012; 42: 437–462.

Murata

Petri nets: properties, analysis and applications. P IEEE 1989; 77: 541–580.

Zhou

MC.

Deadlock resolution in automated manufacturing systems: a novel Petri net approach. London: Springer-Verlag, 2009.

Barkaoui

Pradat-Peyre

JF.

On liveness and controlled siphons in Petri nets. Lect Notes Comput Sc 1996; 1091: 57–72.

Chen

Khalgui

. Design of a maximally permissive liveness—enforcing Petri net supervisor for flexible manufacturing systems. IEEE T Autom Sci Eng 2011; 8: 374–393.

Chen

Barkaoui

. On the enforcement of a class of nonlinear constraints on Petri nets. Automatica 2015; 55: 116–124.

Ezpeleta

Colom

Martinez

A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE T Robotic Autom 1995; 11: 173–184.

Zhou

MC.

Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 38–51.

Zhou

MC.

Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Ind Inform 2006; 2: 313–325.

10.

Wang

AR.

Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Syst Man Cy C 2007; 37: 517–526.

11.

Zhou

NQ.

A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE T Syst Man Cy C 2008; 38: 173–188.

12.

Huang

Jeng

Xie

. Siphon-based deadlock prevention policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2006; 36: 1248–1256.

13.

Hrúz

Zhou

MC.

Modeling and control of discrete-event dynamic systems: with Petri nets and other tools. London: Springer-Verlag, 2007.

14.

Giua

Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints. IEEE T Automat Contr 2015; 60: 1774–1785.

15.

Uzam

Zhou

MC.

An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. Int J Prod Res 2006; 44: 1987–2030.

16.

Zhou

ZW.

Resource-oriented Petri net for deadlock avoidance in flexible assembly systems. IEEE T Syst Man Cy A 2008; 38: 56–69.

17.

Zhou

ZW.

Short-term scheduling of crude-oil operations: enhancement of crude-oil operations scheduling using a Petri net-based control-theoretic approach. IEEE Robot Autom Mag 2015; 22: 64–76.

18.

Giua

Decentralized supervision of Petri nets with a coordinator. IEEE T Syst Man Cy A 2015; 45: 955–966.

19.

Zhou

Uzam

Deadlock control policy for a class of Petri nets without complete siphon enumeration. IET Control Theory A 2007; 1: 1594–1605.

20.

Chu

Xie

XL.

Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE T Robotic Autom 1997; 13: 793–804.

21.

Zhou

MC.

Control of elementary and dependent siphons in Petri nets and their application. IEEE T Syst Man Cy A 2008; 38: 133–148.

22.

Liu

Zhou

MC.

Liveness of an extended S³PR. Automatica 2010; 46: 1008–1018.

23.

Huang

Jeng

Xie

. Deadlock prevention policy based on Petri nets and siphons. Int J Prod Res 2001; 39: 283–305.

24.

Kumaran

Chang

Cho

. A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems. Int J Prod Res 1994; 32: 2361–2379.

25.

Xing

Zhou

Wang

. Resource-transition circuits and siphons for deadlock control of automated manufacturing systems. IEEE T Syst Man Cy A 2011; 41: 74–84.

26.

Uzam

An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. Int J Adv Manuf Tech 2002; 19: 192–208.

27.

Ghaffari

Rezg

Xie

XL.

Design of a live and maximally permissive Petri net controller using the theory of regions. IEEE T Robotic Autom 2003; 19: 137–142.

28.

Uzam

Zhou

MC.

An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2007; 37: 362–371.

29.

Chen

ZW.

Design of a maximally permissive liveness- enforcing Petri net supervisor for flexible manufacturing systems. Automatica 2011; 47: 1028–1034.

30.

Chen

Zhou

MC.

Optimal supervisory control of flexible manufacturing systems by Petri nets: a set classification approach. IEEE T Autom Sci Eng 2014; 11: 549–563.

31.

Yamalidou

Moody

Lemmon

. Feedback control of Petri nets based on place invariants. Automatica 1996; 32: 15–28.

32.

Huang

Pan

PJ.

Transition-based deadlock detection and recovery policy for FMSs using graph technique. ACM T Embed Comput S 2013; 12: 11.

33.

Caprara

Fischetti

Toth

A heuristic method for the set covering problem. Oper Res 1999; 47: 730–743.

34.

Piroddi

Cordone

Fumagalli

Selective siphon control for deadlock prevention in Petri nets. IEEE T Syst Man Cy A 2008; 38: 1337–1348.

Transition-based deadlock control policy using reachability graph for flexible manufacturing systems

Abstract

Keywords

Introduction

Preliminaries

Basics of Petri nets

Reachability graph

Computation of control transitions

Definition 1

Definition 2

Transition-based deadlock control policy

Theorem 1

Proof

An illustrative example

Experimental studies

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References