# Enhancement of Selective Siphon Control Method for Deadlock Prevention in FMSs

Authors: Yen-Liang Pan; Cheng-Fu Yang; Mu-Der Jeng
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

One novel control policy named selective siphon control policy is proposed to solve for deadlock problems of flexible manufacturing systems (FMSs). The new policy not only solves the deadlock problem successfully but also obtains maximally permissive controllers. According to our awareness, the policy is the first one to achieve the goal of obtaining maximally permissive controllers for all S3PR (one system of simple sequential processes with resources, S3PR) models in existing literature. However, one main problem is still needed to solve in their algorithm. The problem is that the proposed policy cannot check the exact number of maximally permissive states of a deadlock net in advance. After all iterating steps, the final maximally permissive states can then be known. Additionally, all legal markings are still to be checked again and again until all critical markings vanished. In this paper, one computationally improved methodology is proposed to solve the two problems. According to the experimental results, the computational efficiency can be enhanced based on the proposed methodology in this paper.


---

## Body

## 1. Introduction

Generally, deadlock prevention of FMS includes structural analysis and reachability graphs [1–11]. In structural analysis, the concept of siphon [1–4, 12–14] is usually adopted, because it just requires a few number of control places. Unfortunately, those algorithms cannot obtain maximally permissive controllers.For improving above disadvantage of conventional siphon control, Piroddi et al. [15, 16] proposed a novel control policy named selective siphon control for solving deadlock problem. The control policy solves deadlock problems of FMSs successfully. It also makes FMSs optimal. It was a new mile stone in solving deadlock domain. The policy is combined by three main stages. They are reachability analysis, structure analysis, and siphon control method for deadlock prevention. However, in our viewpoint, the selective siphon control policy cannot explicitly calculate what the number of maximally permissive markings is in the first two stages. In other words, the policy merely uses the previous paper to make sure what the number of maximally permissive markings is. Otherwise, they just obtained what the number of maximally permissive markings is after all iterating steps are executed.On the other hand, under their policy, all reachable markings are needed to check again and again until all critical markings are vanished. This is time consuming since all legal markings are needed to check in each iterative step.In this paper, one computationally improved methodology is proposed to solve above two problems. First of all, we use the developed algorithm [9] to check the number of maximally permissive markings. Besides, we also prove that the number of quasi-dead and dead markings is equal to critical ones. Furthermore, the selective siphon control is only used for these critical markings so that all critical markings vanished. Most importantly, the computational efficiency is enhanced.


## 2. Preliminaries

### 2.1. Petri Nets [17]

In this paper, we adopt Petri nets theory to model FMS. Due to limitation of paper space, however, we don’t show detailed information of Petri nets theory here. The readers can refer to [17] or our previous works [9, 18].


### 2.2. Critical Markings and Selective Siphons Control Method [15]

Piroddi et al. [15] proposed critical markings and selective siphons control method. The spirit of the method is that once all selective siphons are controlled, all critical markings are accordingly vanished. In this paper, the selective siphon control approach is merged into our previous policy to further reduce the number of CMTSIs.In the following, uncontrolled siphons, critical markings, and selected siphons are defined.Definition 1 (see [15] uncontrolled siphons and critical markings).
LetΠ
=
{
S
1
,
…
,
S
n
} the set of minimal siphons of PN.(i)
The setΠ
u
=
{
S
j
∈
Π
∣
E
S
j
≠
⌀
}, where E
S
j
=
{
M
∈
R
(
N
,
M
0
)
∣
λ
T
S
j
M
=
0
}, is theset of uncontrolled siphons.
(ii)
The setΠ
M
=
{
S
j
∈
Π
u
∣
λ
T
S
j
M
=
0
} denotes the set of empty siphons in the marking M.
(iii)
For anyΠ
*
⊆
Π
u, E
Π
*
=
∪
S
j
∈
Π
*
E
S
j is the set of markings where at least one siphon in Π
* is empty.
(iv)
The setE
Π
u denotes theset of critical markings.
(v)
Acovering set of uncontrolled siphons (CSUS) is a subset of siphons Π
c
⊆
Π
u, such that E
Π
c
=
E
Π
u.Table1 presents the relation between uncontrolled siphons and critical markings. Based the table, two uncontrolled siphons (i.e., S
x and S
y) are called the selective siphon since they cover all critical markings (i.e., M
1
–
M
6).Table 1
The relation between critical markings and uncontrolled siphons.
S
x
S
y
S
z
M
1
v
M
2
v
v
M
3
v
v
M
4
v
v
M
5
v
M
6
v


### 2.3. Synthesis Problem [9, 18]

In our previous works [9, 18], M
D and M
Q represent the set ofdead markings and quasi-dead markings, respectively. Besides, Z
D and Z
Q are also proposed to represent the set ofdead markings and quasi-dead markings, respectively. For the detailed definitions please refer to [9, 18]. In [20], besides, Z
L has been showed that it is the maximally permissive number of one FMS. Therefore, above definitions will be used to check the number of maximally permissive markings in reachability graph stage.


## 2.1. Petri Nets [17]

In this paper, we adopt Petri nets theory to model FMS. Due to limitation of paper space, however, we don’t show detailed information of Petri nets theory here. The readers can refer to [17] or our previous works [9, 18].


## 2.2. Critical Markings and Selective Siphons Control Method [15]

Piroddi et al. [15] proposed critical markings and selective siphons control method. The spirit of the method is that once all selective siphons are controlled, all critical markings are accordingly vanished. In this paper, the selective siphon control approach is merged into our previous policy to further reduce the number of CMTSIs.In the following, uncontrolled siphons, critical markings, and selected siphons are defined.Definition 1 (see [15] uncontrolled siphons and critical markings).
LetΠ
=
{
S
1
,
…
,
S
n
} the set of minimal siphons of PN.(i)
The setΠ
u
=
{
S
j
∈
Π
∣
E
S
j
≠
⌀
}, where E
S
j
=
{
M
∈
R
(
N
,
M
0
)
∣
λ
T
S
j
M
=
0
}, is theset of uncontrolled siphons.
(ii)
The setΠ
M
=
{
S
j
∈
Π
u
∣
λ
T
S
j
M
=
0
} denotes the set of empty siphons in the marking M.
(iii)
For anyΠ
*
⊆
Π
u, E
Π
*
=
∪
S
j
∈
Π
*
E
S
j is the set of markings where at least one siphon in Π
* is empty.
(iv)
The setE
Π
u denotes theset of critical markings.
(v)
Acovering set of uncontrolled siphons (CSUS) is a subset of siphons Π
c
⊆
Π
u, such that E
Π
c
=
E
Π
u.Table1 presents the relation between uncontrolled siphons and critical markings. Based the table, two uncontrolled siphons (i.e., S
x and S
y) are called the selective siphon since they cover all critical markings (i.e., M
1
–
M
6).Table 1
The relation between critical markings and uncontrolled siphons.
S
x
S
y
S
z
M
1
v
M
2
v
v
M
3
v
v
M
4
v
v
M
5
v
M
6
v


## 2.3. Synthesis Problem [9, 18]

In our previous works [9, 18], M
D and M
Q represent the set ofdead markings and quasi-dead markings, respectively. Besides, Z
D and Z
Q are also proposed to represent the set ofdead markings and quasi-dead markings, respectively. For the detailed definitions please refer to [9, 18]. In [20], besides, Z
L has been showed that it is the maximally permissive number of one FMS. Therefore, above definitions will be used to check the number of maximally permissive markings in reachability graph stage.


## 3. The Proposed Methodology

In this paper, one computationally improved methodology is present to enhance the computational efficiency of conventional selective siphon control technology. The methodology shown in Figure1 consists of reachability graph stage, siphon identification stage, siphon control stage, and so forth.Figure 1
Flow chart of the proposed deadlock prevention.


## 4. Experimental Results

Two classical flexible manufacturing systems are used to check the proposed deadlock prevention. They are taken from [6] and [19], respectively.Example 1.
An FMS is shown in Figure2 [6]. To do our deadlock prevention policy, R
(
N
1
,
M
0
) of the PN system can be modeled as shown in Figure 3.Figure 2
A classical FMS PN model [6].Figure 3
The reachability graph of Example1.First of all, in the “reachability graph (RG) stage,” 20 reachable markings (i.e.,M
0
–
M
19) are located by INA [21]. Then 2 dead markings (i.e., M
7 and M
12) can be identified based on or our previous works [9, 18]. In addition, three M
Q (i.e., M
9, M
10, and M
11) can also be identified. All detailed information of the M
D and M
Q is listed in Table 2.Table 2
The property of dead and quasi-dead markings.
Marking number
Information of marking
Classification
M
7
[1, 1, 1, 0, 2, 1, 0, 0, 0, 0, 0]
M
D
M
12
[2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0]
M
D
M
9
[2, 0, 1, 0, 2, 1, 0, 0, 1, 0, 0]
M
Q
M
1
0
[2, 1, 0, 0, 2, 1, 0, 0, 0, 1, 0]
M
Q
M
1
1
[2, 1, 0, 0, 2, 0, 1, 0, 0, 0, 1]
M
QTherefore, the total number ofM
L can then be determined (i.e., 20 − (2 + 3) = 15). In other words, the number of maximally permissive markings is 15.In siphon identification stage, firstly, three sets of strict minimal siphonsS
1
=
{
p
3
,
p
8
,
p
9
,
p
1
0
}, S
2
=
{
p
4
,
p
7
,
p
1
0
,
p
1
1
}, and S
3
=
{
p
4
,
p
8
,
p
9
,
p
1
0
,
p
1
1
} in this example are calculated. Additionally, according to definitions in [15], S
1 and S
2 are the two sets of selective siphons since S
3 is included in (S
1
∪
S
2). The detailed information for identifying selective siphons is shown in Table 3.Table 3
The detailed information of selective siphons in Example1.
Critical marking
Minimal siphon
S
1
S
2
S
3
M
7
v
v
M
12
v
v
M
9
v
M
10
M
11
vIn siphon control stage, two control places are then obtained by siphon control method [3] since two sets of selective siphons are identified. The detailed information is shown in Table 4. Please notice that this paper just focuses on enhancement of computational efficiency. Therefore, for the detailed information about how to compute control places please refer to [3, 4]. Additionally, also note that from Table 3 it is obvious that one critical marking M
10 is still not covered by any strict minimal siphon. Accordingly, in the following, new strict minimal siphons are needed to calculate again after the two control places are added in Example 1.Table 4
The first additional control places in Example1.
Control places
M
0(C
p
i)
●(C
p
i)
(C
p
i)●
C
p
1
1
t
2
,
t
7
t
1
,
t
6
C
p
2
1
t
3
,
t
6
t
2
,
t
5In second iteration, new four sets of strict minimal siphons are identified. They areS
4
=
{
p
4
,
p
8
,
p
9
,
p
1
1
,
p
12
,
p
13
}, S
5
=
{
p
4
,
p
7
,
p
11
,
p
1
2
,
p
13
}, S
6
=
{
p
3
,
p
8
,
p
9
,
p
1
2
,
p
13
}, and S
7
=
{
p
3
,
p
7
,
p
12
,
p
1
3
}. We use them to check if they are empty or not in M
10. All readers will have one question; that is, the number of places in M
10 should be extended since two control places are added into this model. The answer seems yes, but the firing sequence will not be changed. Therefore, the number of places of the new marking M
10 (we use M
10
′ to replace the new marking M
10) should be 13. Further, from initial stage, the firing sequence from initial marking M
0 to marking M
10 is t
1
t
5 or t
5
t
1. So, the firing sequence from M
0
′ (new M
0) M
10
′ is still t
1
t
5 or t
5
t
1. M
10
′ can be calculated by state equation M
10
′
=
M
0
′
+
N
ρ
⃑. Among them, M
0
′ = [3, 0, 0, 0, 3, 0, 0, 0, 1, 1, 1, 1, 1]′, N is shown in Table 5, and ρ
⃑ is [1, 0, 0, 0, 1, 0, 0, 0]′. Finally, M
10
′ therefore is [2, 1, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0]′. From above four strict minimal siphons and M
10
′, it is obvious that S
4, S
5, S
6, and S
7 could be selective siphons since they are all empty in M
10
′ (Table 6). We just choose S
7 to be the selective siphon because it has fewest element among these strict minimal siphons. And, one control place can then be calculated based on the selective siphon S
7. Its detailed information is shown in Table 7.Table 5
The new incidence matrix of Example1.
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
p
1
−1
0
0
1
0
0
0
0
p
2
1
−1
0
0
0
0
0
0
p
3
0
1
−1
0
0
0
0
0
p
4
0
0
1
−1
0
0
0
0
p
5
0
0
0
0
−1
0
0
1
p
6
0
0
0
0
1
−1
0
0
p
7
0
0
0
0
0
1
−1
0
p
8
0
0
0
0
0
0
1
−1
p
9
−1
1
0
0
0
0
−1
1
p
10
0
−1
1
0
0
−1
1
0
p
11
0
0
−1
1
−1
1
0
0
p
1
2
(
C
p
1
)
−1
1
0
0
0
−1
1
0
p
1
3
(
C
p
2
)
0
−1
1
0
−1
1
0
0Table 6
The relation between minimal siphons and critical markings in the second iteration of Example1.
Critical marking
Minimal siphon
S
4
S
5
S
6
S
7
M
10
v
v
v
vTable 7
The second additional control place in Example1.
Control places
M
0(C
p
i)
●(C
p
i)
(C
p
i)●
C
p
1
1
t
2,t
6
t
1,t
5When the three control places are added into Example1, the model is deadlock-free. The reachability graph is shown in Figure 4. In fact, we do not need to run the reachability again. The reachability graph is needed in the first time to identify all markings as dead markings, quasi-dead ones, and legal ones.Figure 4
The new reachability graph of Example1 after three control places are added.Example 2.
Another classical FMS is shown in Figure5 [19]. In the first iteration, first of all, the reachability graph analysis is executed, and 210 markings in total are obtained in this stage. Similarly, there are 16 dead and 61 quasi-dead markings in initial reachability graph. The 16 dead markings are M
9, M
19, M
70, M
71, M
76, M
77, M
78, M
83, M
84, M
94, M
99, M
100, M
105, M
106, M
112, and M
113 which are then located. And, the 61 quasi-dead markings are M
6, M
7, M
8, M
14, M
15, M
16, M
17, M
18, M
25, M
48, M
66, M
67, M
68, M
69, M
72, M
73, M
74, M
75, M
79, M
80, M
81, M
82, M
87, M
101, M
102, M
103, M
104, M
108, M
109, M
110, M
111, M
124, M
130, M
135, M
136, M
141, M
142, M
143, M
150, M
162, M
198, M
203, M
204, M
210, M
250, M
251, M
257, M
258, M
259, M
260, M
261, M
262, M
263, M
265, M
269, M
270, M
272, M
273, M
274, M
277, and M
278. Due to limitation of paper space, the detailed information of above 16 dead markings and 61 quasi-dead ones will not be shown. The detailed information can be obtained in INA [21].Figure 5
Another classical FMS PN model [19].Therefore, the maximally permissive number of states is 205 since 210-16-61 = 205. In the following, five sets of minimal siphons are calculated and obtained in siphon identification stage. They areS
1
=
{
p
2
,
p
5
,
p
13
,
p
15
,
p
18
}, S
2
=
{
p
5
,
p
13
,
p
1
4
,
p
1
5
,
p
18
}, S
3
=
{
p
2
,
p
7
,
p
1
1
,
p
1
3
,
p
1
6
,
p
1
7
,
p
18
,
p
1
9
}, S
4
=
{
p
2
,
p
7
,
p
1
3
,
p
1
5
,
p
1
6
,
p
1
7
,
p
18
,
p
1
9
}, and S
5
=
{
p
7
,
p
13
,
p
1
4
,
p
1
5
,
p
1
6
,
p
1
7
,
p
18
,
p
1
9
}. Furthermore, S
1, S
2, and S
3 are the selective siphons since (S
1
∪
S
2
∪
S
3) can cover all critical markings except M
96, M
125, M
151, M
158, and M
181. In other words, (S
4
∪
S
5) are included in (S
1
∪
S
2
∪
S
3). In siphon control stage, one can obtain three controllers shown in Table 8 from S
1, S
2, and S
3, respectively.Table 8
The first additional control places in Example2.
Control places
M
0(C
p
i)
●(C
p
i)
(C
p
i)●
C
p
1
1
t
5
,
t
13
t
2
,
t
11
C
p
2
2
t
4
,
t
5
,
t
13
t
1
,
t
11
C
p
3
3
t
7
,
t
11
t
4
,
t
5
,
t
9After adding the three controllers, ten new minimal siphons appear in the second stage. The detailed information of them is thatS
6
=
{
p
5
,
p
11
,
p
13
,
p
14
,
p
18
,
p
20
}, S
7
=
{
p
5
,
p
6
,
p
12
,
p
15
,
p
21
,
p
22
}, S
8
=
{
p
5
,
p
6
,
p
11
,
p
12
,
p
21
,
p
22
}, S
9
=
{
p
5
,
p
6
,
p
12
,
p
15
,
p
20
,
p
22
}, S
10
=
{
p
5
,
p
6
,
p
11
,
p
12
,
p
20
,
p
22
}, S
11
=
{
p
7
,
p
12
,
p
15
,
p
17
,
p
19
,
p
21
,
p
22
}, S
12
=
{
p
7
,
p
11
,
p
12
,
p
17
,
p
19
,
p
21
,
p
22
}, S
13
=
{
p
7
,
p
12
,
p
15
,
p
17
,
p
19
,
p
20
,
p
22
}, S
14
=
{
p
7
,
p
11
,
p
12
,
p
17
,
p
19
,
p
20
,
p
22
}, and S
15
=
{
p
7
,
p
11
,
p
13
,
p
14
,
p
16
,
p
17
,
p
18
,
p
19
,
p
20
}. Similarly, one just needed to check if the places of these new uncontrolled minimal siphons are empty in above still uncontrolled critical markings (M
9
6, M
125, M
151, M
158, and M
181). Table 9 shows the relation between ten new uncontrolled minimal siphons and five uncontrolled critical markings. From Table 9, it is obvious that (S
7
∪
S
8) or (S
7
∪
S
9) can cover all critical markings. It means that the five critical markings can then be controlled once (S
7
∪
S
8) or (S
7
∪
S
9) are controlled. For convenience, we just choose S
7 and S
8 as the two selective siphons. Therefore, two control places can then be obtained shown in Table 10. When the five control places are added into Example 2, the model is deadlock-free too.Table 9
The relation between minimal siphons and critical markings in the second iteration of Example2.
S
6
S
7
S
8
S
9
S
10
S
11
S
12
S
13
S
14
S
15
M
86
v
v
M
110
v
v
M
129
v
v
v
v
M
133
v
M
151
v
v
v
vTable 10
The second additional control places in Example2.
Control places
M
0(C
p
i)
●(C
p
i)
(C
p
i)●
C
p
4
6
t
7
,
2
t
11
t
1
,
2
t
9
C
p
5
3
t
7
,
t
11
t
4
,
t
5
,
t
9


## 5. Comparison and Discuss

Based on Tables11 and 12, the proposed methodology in this paper for solving problems of deadlock can make sure of the exact number of maximally permissive live (legal) markings in the reachability running stage. Besides, there are just 5 and 77 markings in first stage and 1 and 5 markings are needed to check, respectively. However, the conventional method has to check all markings in every selective siphon identification stage. To summarize, our work presents a computationally improved optimal control methodology compared to this pioneer work [15].Table 11
The comparison results in Example1.
Important parameter comparison
[15]
This work
Optimal (maximally permissive) control?
Yes
Yes
Can make sure the exact number of optimal states in first stage?
No
Yes
How many reachable markings are needed to check in first stage?
20
5
How many reachable markings are needed to check in second stage?
16
1Table 12
The comparison results in Example2.
Important parameter comparison
[15]
This work
Optimal (maximally permissive) control?
Yes
Yes
Can make sure the exact number of optimal states in first stage?
No
Yes
How many reachable markings are needed to check in first stage?
282
77
How many reachable markings are needed to check in second stage?
210
5


## 6. Conclusions

The proposed policy can be implemented for the deadlock problems of FMSs based on the selective siphons method and critical markings. The underlying notion of the prior work is that it cannot check the exact number of maximally permissive states of a deadlock net in advance. After all iterating steps, the final maximally permissive can then be known. Additionally, all legal markings are still to be checked again and again until all critical markings vanished. In this work, one computationally improved methodology is proposed to solve the two problems. Under the proposed methodology, the reachability graph is only run one time in initial stage. All critical markings are identified based on the reachability graph. One just checks if strict minimal siphons are empty in these markings or not. According to the experimental results, the computational efficiency can be enhanced based on the proposed methodology in this papers.



---

*Source: 196514-2015-08-26.xml*