# Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors

Authors: Liang Hong; YiFan Hou; JunFeng Jing; AnRong Wang; Dmitry A. Litvin
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

This work develops an iterative deadlock prevention method for a special class of Petri nets that can well model a variety of flexible manufacturing systems. A deadlock detection technique, called mixed integer programming (MIP), is used to find a strict minimal siphon (SMS) in a plant model without a complete enumeration of siphons. The policy consists of two phases. At the first phase, SMSs are obtained by MIP technique iteratively and monitors are added to the complementary sets of the SMSs. For the possible existence of new siphons generated after the first phase, we add monitors with their output arcs first pointed to source transitions at the second phase to avoid new siphons generating and then rearrange the output arcs step by step on condition that liveness is preserved. In addition, an algorithm is proposed to remove the redundant constraints of the MIP problem in this paper. The policy improves the behavioral permissiveness of the resulting net and greatly enhances the structural simplicity of the supervisor. Theoretical analysis and experimental results verify the effectiveness of the proposed method.


---

## Body

## 1. Introduction

Deadlocks [1] always appear in the operations of a flexible manufacturing system (FMS). Hence, deciding how to reduce the impact of deadlocks is a very tricky problem that we have to cope with. Digraphs, automata, and Petri nets are three major mathematical tools to deal with deadlock problems in resource allocation systems.Digraphs are used to deal with the deadlock detection and avoidance in [2, 3]. Researchers [4, 5] adopt automata as model tools to dispose the deadlock problem while Petri nets [6] are applied to model and analyze FMS. The main Petri net strategies are deadlock detection and recovery [7, 8], deadlock avoidance [9–11], and deadlock prevention [12–19].This paper focuses our attention on deadlock prevention problems. A Petri net based deadlock prevention approach utilizes an off-line computational mechanism to impose constraints on a system to prevent the system from reaching deadlock states. Monitors (control places) and their related arcs are used to achieve such purposes and collectively called a supervisor of the plant model.The theory of regions, as a technique to design supervisors for a Petri net, is adopted in [13, 20, 21]. Generally, the theory can lead to an optimal supervisor [22–28] if it exists. However, the theory is based on a reachability graph, which may cause state explosion with a net size increasing.McMillan and Probst propose the concept of unfolding nets in [29] to describe the behavior of an FMS. A prefix of an unfolding net is adequate to completely describe the properties of a net, which is a concise but efficient method compared with the theory of regions. However, deciding how to find a complete and simple prefix is still worth consideration.Siphons are special sets of places of a Petri net, by controlling which one can effectively prevent deadlocks. Ezpeleta et al. [12] propose a policy by enumerating siphons and impose constraints for the siphons to solve deadlock prevention problems. However, it is a time-consuming task with nets scale expansion [30]. In addition, behavioral permissiveness and structural complexity are tough issues that we have to face. Li and Zhou [14] propose elementary siphon theory, where enumerated siphons are divided into two parts: elementary and dependent. Monitors are only needed for the elementary siphons as long as the dependent siphons are controllable, which greatly reduces the structural complexity. Moreover, the computational complexity is reduced and the behavioral permissiveness is enhanced in the subsequent research [15, 31–38].Huang et al. [39] propose a two-stage deadlock prevention policy for System of Simple Sequential Processes with Resources (S3PR), a class of Petri nets that was proposed in [12]. The policy explores SMS based on the MIP technique, developed by Chu and Xie [40] for structurally bounded nets. For S3PR, at the first stage, by the MIP technique, maximal unmarked siphon is obtained first if there exist deadlocks. SMS can be derived from the maximal unmarked siphon and a corresponding constraint, imposed on the complementary set of the SMSs to prevent it from being unmarked, is obtained enforcing the constraint to the MIP problem to check the liveness of the plant net under the constraint. If there still exists a maximal unmarked siphon, repeat the above process till the plant net is live under the derived constraints. Thus, we can obtain one or more constraints and add corresponding monitors (including their related arcs) to the complementary sets of the SMSs. Hence, the resulting net obtained after the first stage is a net consisting of the plant net and the corresponding monitors. Control-induced siphons (composed by operation places, resource places, and the monitors) can possibly be generated due to the addition of the monitors. The second stage, similar to the first one, is still an iterative process in finding siphons and the difference is that the monitors of this stage are added with their output arcs pointed to source transitions, which makes the control-induced siphons controlled and no problematic siphons were generated. The policy can usually lead to a more permissive supervisor than that proposed in [12].However, there exist the following defects in [39]. First, the SMS obtained after an iteration is nondeterministic due to the following two reasons. The first is that the solution (corresponds to a maximal unmarked siphon) of the MIP problem is not unique and the second is that we can find different SMSs from the same maximal unmarked siphon via different place selection sequences. Thus, the sequence of the generation of SMSs is uncertain. Sometimes, SMS can be controlled if the subsequent SMSs are controlled. Hence, adding a monitor for the SMS is redundant and makes the control structure complex.Second, at the second stage in [39], the constraint, mentioned at Step  17 of Algorithm 2 of [39] and used for exploring the condition of liveness in the considered MIP problem, is imposed on the complementary set of new generated SMSs (derived from a control-induced siphon) while the output arcs of the constraint corresponding monitor are pointed to source transitions. It causes the fact that the constraints obtained at the second stage are always more than the necessary monitors. However, the number of added monitors for SMSs is requested consistent with that of the obtained constraints in terms of the policy, which leads to the fact that redundant monitors are generated and the behavioral permissiveness is generally restricted.This work improves [39] in terms of structural complexity and behavioral permissiveness by the following three points. First, for removing the redundant constraints, an algorithm is developed that checks the redundancy of a constraint by deciding whether the liveness is preserved after its removal. This operation markedly reduces the structural complexity. Second, a new type of constraints is constructed to replace the one that emerged at Step  17 of Algorithm  2 in [39] to reduce structural complexity and enhance behavioral permissiveness. The generation of redundant monitors is avoided by imposing the new constraint on the complementary set of newly generated SMSs and the set of its upstream places (defined in Definition 14), which makes the constraint have the same effect with the monitors added at the second stage on preventing the newly generated SMS from being unmarked. Third, for each output arc of the monitors added at the second stage, it is led from the source transition step by step to release more legal states on condition that the liveness is preserved. In summary, the improvements largely enhance the performance of a supervisor for a plant net.The rest of this paper is organized as follows. Preliminaries used in this paper are presented in the next section. In Section3, we introduce a deadlock prevention policy that mainly contains two phases: siphon control phase and extended siphon control phase. The specific method is shaped to an algorithm in Section 4. By experimental analysis, the performance of the proposed method is shown in Section 5. Finally, Section 6 concludes this paper.


## 2. Preliminaries

### 2.1. Basics of Petri Nets

A Petri net is a four-tupleN
=
(
P
,
T
,
F
,
W
), where P and T are the sets of places and transitions, respectively. F
⊆
(
P
×
T
)
∪
(
T
×
P
) is called a flow relation, represented by arcs with arrows from transitions to places or from places to transitions. W
:
(
P
×
T
)
∪
(
T
×
P
)
→
N is a mapping that assigns a weight to an arc: W
(
x
,
y
)
>
0 if (
x
,
y
)
∈
F, where x
∈
P, y
∈
T  (or x
∈
T, y
∈
P), and N
=
{
0,1
,
2
,
…
}. If W
(
x
,
y
)
≤
1, ∀
(
x
,
y
)
∈
F, the net is called an ordinary Petri net; otherwise, it is called a generalized Petri net.A marking (also called a state)M is a mapping from P to N. The number of tokens in place p is denoted by M
(
p
). A place p is marked at a marking M if M
(
p
)
>
0. M
(
S
) denotes the sum of tokens of all places in S; that is, M
(
S
)
=
∑
p
∈
S
‍
M
(
p
), where S
⊆
P. S is marked at M if M
(
S
)
>
0. S is unmarked at M if M
(
S
)
=
0. (
N
,
M
0
) is called a net system and M
0 is called an initial marking of N.Letx
∈
P
∪
T be a node of N
=
(
P
,
T
,
F
,
W
). x
∙
=
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F is called the preset of x and x
∙
=
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F is called the postset of x. Similar notation extended to a set of nodes is as follows: given X
⊆
P
∪
T, X
∙
=
∪
x
∈
X
x
∙, X
∙
=
∪
x
∈
X
x
∙, X
∙
∙
=
∪
x
∈
X
x
∙
∙, and X
∙
∙
=
∪
x
∈
X
x
∙
∙.A nonempty setS
⊆
P is called a siphon if S
∙
⊆
S
∙. S is minimal if there is no siphon in S as a proper subset. S is strict if S
∙
⫋
S
∙.A transitiont
∈
T is enabled at a marking M if, ∀
p
∈
t
∙, M
(
p
)
≥
W
(
p
,
t
) and denoted as M
[
t
〉. Firing t yields a new marking M
′ that can be denoted by M
[
t
〉
M
′ and M
′ is called an immediately reachable marking from M. A marking M
′
′ is said to be reachable from M if there exists a sequence of transitions σ
=
t
0
t
1
⋯
t
n and markings M
1
,
M
2
,
…, and M
n such that M
[
t
0
〉
M
1
[
t
1
〉
M
2
⋯
M
n
[
t
n
〉
M
′
′ holds. The set of markings reachable from M in N is called the reachability set of Petri net (
N
,
M
) and denoted as R
(
N
,
M
). The set of legal states of net (
N
,
M
0
) is defined as follows: M
=
M
∣
M
∈
R
(
N
,
M
0
)
∧
M
0
∈
R
(
N
,
M
).A transitiont
∈
T is live at M
0 if, ∀
M
∈
R
(
N
,
M
0
), ∃
M
′
∈
R
(
N
,
M
), M
′
t. (
N
,
M
0
) is live if, ∀
t
∈
T, t is live at M
0. It is dead at M
0 if ∄
t
∈
T, M
0
t. It is deadlock-free if ∀
M
∈
R
(
N
,
M
0
), ∃
t
∈
T, M
t.AP-vector is a column vector I
:
P
→
Z indexed by P and a T-vector is a column vector J
:
T
→
Z indexed by T, where Z is the set of integers. The column vectors where every entry equals 0
(
1
) are denoted by 0
(
1
). [
N
] is a |
P
|
×
|
T
| integer matrix with [
N
]
(
p
,
t
)
=
W
(
t
,
p
)
-
W
(
p
,
t
). I
T is the transposed versions of vector I. P-vector I is called a P-invariant if I
≠
0 and I
T
[
N
]
=
0
T and I
=
p
∣
I
(
p
)
≠
0 is the support of I. I is minimal if its support is not contained in the support of any other and its components are mutually prime. P-invariant I is a P-semiflow if its every element is nonnegative.


### 2.2. S3PR

In this subsection, we introduce a class of Petri nets, called S3PR, first defined in [12], which stands forSystems of Simple Sequential Processes with Resources and can model real-life automated FMSs.Definition 1 (see [12]).
An ordinary Petri netN
=
(
P
,
T
,
F
) is called a state machine if, ∀
t
∈
T,  t
∙
=
|
t
∙
|
=
1. It is strongly connected if, ∀
x
,
y
∈
P
∪
T, there is a sequence of nodes x
,
a
,
b
,
…
,
c, and y such that (
x
,
a
)
,
(
a
,
b
)
,
…, and (
c
,
y
)
∈
F, where {
a
,
b
,
…
,
c
}
⊆
P
∪
T.Definition 2 (see [12]).
A simple sequential process (S2P) is a Petri net N
=
(
{
p
0
}
∪
P
A
,
T
,
F
), where P
A
≠
∅ is the set of operation places, p
0 is the idle process place, N is a strongly connected state machine, and the circuit of N contains p
0.Definition 3 (see [12]).
A simple sequential process with resources (S2PR) is a Petri net N
=
(
{
p
0
}
∪
P
A
∪
P
R
,
T
,
F
) such that (1)
the subnet generated byX
=
P
A
∪
{
p
0
}
∪
T is S2P,
(2)
P
R
≠
∅ and (
P
A
∪
{
p
0
}
)
∩
P
R
=
∅, where P
R is called the set of resource places,
(3)
∀
p
∈
P
A, ∀
t
∈
p
∙, ∀
t
′
∈
p
∙, ∃
r
p
∈
P
R, t
∙
∩
P
R
=
t
′
∙
∩
P
R
=
{
r
p
},
(4)
(a)∀
r
∈
P
R, r
∙
∙
∩
P
A
=
r
∙
∙
∩
P
A
≠
∅ and (b), ∀
r
∈
P
R, r
∙
∩
r
∙
=
∅,
(5)
(
p
0
)
∙
∙
∩
P
R
=
(
p
0
)
∙
∙
∩
P
R
=
∅.Definition 4 (see [12]).
S3PR is a system of S2PR, defined as follows: (1)
An S2PR is an S3PR.
(2)
LetN
i
=
(
{
p
i
0
}
∪
P
A
i
∪
P
R
i
,
T
i
,
F
i
), i
∈
{
1,2
}, be two S3PR such that (
P
A
1
∪
{
p
1
0
}
)
∩
(
P
A
2
∪
{
p
2
0
}
)
=
∅, P
R
1
∩
P
R
2
=
P
C
≠
∅, and T
1
∩
T
2
=
∅. Then, combine N
1 and N
2 via P
C into a net N
=
P
0
∪
P
A
∪
P
R
,
T
,
F. N is also an S3PR, defined as follows: (1) P
A
=
P
A
1
∪
P
A
2, (2) P
0
=
{
p
1
0
}
∪
{
p
2
0
}, (3) P
R
=
P
R
1
∪
P
R
2, (4) T
=
T
1
∪
T
2, and (5) F
=
F
1
∪
F
2.Transitions in(
P
0
)
∙ are calledsource transitions, which represent the entry of raw materials when FMS is modeled with an S3PR.Definition 5 (see [12]).
Forr
∈
P
R, H
(
r
)
=
r
∙
∙
∩
P
A is called the set of holders of r, which represent the operation places that use r. Let S be s siphon and S
R
=
S
∩
P
R; [
S
]
=
(
∪
r
∈
S
R
H
(
r
)
)
∖
S is called thecomplementary set of S.Theorem 6 (see [12]).
An S3PR (
N
,
M
0
) is live if, ∀
M
∈
R
(
N
,
M
0
), ∀
S
∈
Π, M
(
S
)
>
0.LetΠ be the set of SMSs in an S3PR. The above theorem indicates that an S3PR is live if there is no siphon that can be emptied.


### 2.3. MIP Technique

Let(
N
,
M
) be an ordinary net with N
=
(
P
,
T
,
F
) and let S be the maximal unmarked siphon at M; that is, ∀
p
∉
S, M
(
p
)
>
0. In the sequel, we introduce a technique, first proposed in [40], to find S in N by exploring the solution of a mixed integer programming (MIP) problem. ∀
p
∉
S, let v
p
=
1 and, ∀
t
∉
S
∙, let z
t
=
1.SinceS is a siphon and, ∀
p
∉
S, M
(
p
)
>
0, any p with v
p
=
1 and any t with z
t
=
1 should be removed from the solution. Furthermore, ∀
t
∈
p
∙, v
p
=
0 implies z
t
=
0 and, ∀
p
∈
t
∙, z
t
=
1 implies the truth of v
p
=
1. This leads to(1)
z
t
≥
∑
p
∈
t
∙
v
p
-
t
∙
+
1
,
∀
t
∈
T
,
v
p
≥
z
t
,
∀
t
,
p
∈
F
,
v
p
,
z
t
∈
0,1
.For a structurally bounded net, we have(2)
v
p
≥
M
p
S
B
p
,
∀
p
∈
P
,where S
B
(
p
)
=
max
⁡
M
(
p
)
∣
M
=
M
0
+
[
N
]
Y
,
M
≥
0
,
Y
≥
0 denotes the structural bound of place p. Therefore, the maximal unmarked siphon can be determined by the following MIP problem and there exist siphons unmarked in (
N
,
M
0
) if G
M
I
P
(
M
0
)
<
|
P
|:(3)
G
M
I
P
M
0
=
M
i
n
i
m
i
z
e
∑
p
∈
P
v
psubject to constraints (1)-(2) and(4)
M
=
M
0
+
N
Y
,
M
≥
0
,
Y
≥
0
.Although MIP problems are NP-hard, it is shown in [40] that its computational efficiency is relatively insensitive to the initial marking and more efficient than state enumeration methods.Theorem 7 (see [40]).
Let(
N
,
M
0
) be an ordinary Petri net with N
=
(
P
,
T
,
F
). (
N
,
M
0
) is live if G
M
I
P
(
M
0
)
=
|
P
|.Theorem7 is used to check S3PR (
N
,
M
0
) whether liveness is enforced or not. If G
M
I
P
(
M
0
) equals the cardinality of the place set of N, it implies that (
N
,
M
0
) is live.However, the classical MIP problem to determine a maximal unmarked siphon in [40] only applies to ordinary Petri nets. As for a generalized Petri net, deadlocks may occur due to insufficiently marked siphons. Hence, the new conditions for checking whether there exist a maximal unmarked siphon in a generalized Petri net (
N
,
M
0
) with N
=
(
P
,
T
,
F
,
W
) are presented in [41], where a new constraint (5) is used to replace constraint (2):(5)
v
p
≥
M
p
-
W
p
,
t
+
1
S
B
p
,
∀
p
∈
P
,
∀
W
p
,
t
>
0
.The maximal unmarked siphon of a generalized Petri net(
N
,
M
0
) can be determined by the following MIP problem and there exist unmarked siphons if G
g
e
n
M
I
P
(
M
0
)
<
|
P
|:(6)
G
g
e
n
M
I
P
M
0
=
M
i
n
i
m
i
z
e
∑
p
∈
P
v
psubject to constraints (1) and (5) and(7)
M
=
M
0
+
N
Y
,
M
≥
0
,
Y
≥
0
.Theorem 8 (see [41]).
Let(
N
,
M
0
) be a generalized Petri net with N
=
(
P
,
T
,
F
,
W
). (
N
,
M
0
) is live if G
g
e
n
M
I
P
(
M
0
)
=
|
P
|.For a generalized Petri net(
N
,
M
0
), if G
g
e
n
M
I
P
(
M
0
) equals the cardinality of the place set of N, we can conclude that (
N
,
M
0
) is live.


## 2.1. Basics of Petri Nets

A Petri net is a four-tupleN
=
(
P
,
T
,
F
,
W
), where P and T are the sets of places and transitions, respectively. F
⊆
(
P
×
T
)
∪
(
T
×
P
) is called a flow relation, represented by arcs with arrows from transitions to places or from places to transitions. W
:
(
P
×
T
)
∪
(
T
×
P
)
→
N is a mapping that assigns a weight to an arc: W
(
x
,
y
)
>
0 if (
x
,
y
)
∈
F, where x
∈
P, y
∈
T  (or x
∈
T, y
∈
P), and N
=
{
0,1
,
2
,
…
}. If W
(
x
,
y
)
≤
1, ∀
(
x
,
y
)
∈
F, the net is called an ordinary Petri net; otherwise, it is called a generalized Petri net.A marking (also called a state)M is a mapping from P to N. The number of tokens in place p is denoted by M
(
p
). A place p is marked at a marking M if M
(
p
)
>
0. M
(
S
) denotes the sum of tokens of all places in S; that is, M
(
S
)
=
∑
p
∈
S
‍
M
(
p
), where S
⊆
P. S is marked at M if M
(
S
)
>
0. S is unmarked at M if M
(
S
)
=
0. (
N
,
M
0
) is called a net system and M
0 is called an initial marking of N.Letx
∈
P
∪
T be a node of N
=
(
P
,
T
,
F
,
W
). x
∙
=
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F is called the preset of x and x
∙
=
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F is called the postset of x. Similar notation extended to a set of nodes is as follows: given X
⊆
P
∪
T, X
∙
=
∪
x
∈
X
x
∙, X
∙
=
∪
x
∈
X
x
∙, X
∙
∙
=
∪
x
∈
X
x
∙
∙, and X
∙
∙
=
∪
x
∈
X
x
∙
∙.A nonempty setS
⊆
P is called a siphon if S
∙
⊆
S
∙. S is minimal if there is no siphon in S as a proper subset. S is strict if S
∙
⫋
S
∙.A transitiont
∈
T is enabled at a marking M if, ∀
p
∈
t
∙, M
(
p
)
≥
W
(
p
,
t
) and denoted as M
[
t
〉. Firing t yields a new marking M
′ that can be denoted by M
[
t
〉
M
′ and M
′ is called an immediately reachable marking from M. A marking M
′
′ is said to be reachable from M if there exists a sequence of transitions σ
=
t
0
t
1
⋯
t
n and markings M
1
,
M
2
,
…, and M
n such that M
[
t
0
〉
M
1
[
t
1
〉
M
2
⋯
M
n
[
t
n
〉
M
′
′ holds. The set of markings reachable from M in N is called the reachability set of Petri net (
N
,
M
) and denoted as R
(
N
,
M
). The set of legal states of net (
N
,
M
0
) is defined as follows: M
=
M
∣
M
∈
R
(
N
,
M
0
)
∧
M
0
∈
R
(
N
,
M
).A transitiont
∈
T is live at M
0 if, ∀
M
∈
R
(
N
,
M
0
), ∃
M
′
∈
R
(
N
,
M
), M
′
t. (
N
,
M
0
) is live if, ∀
t
∈
T, t is live at M
0. It is dead at M
0 if ∄
t
∈
T, M
0
t. It is deadlock-free if ∀
M
∈
R
(
N
,
M
0
), ∃
t
∈
T, M
t.AP-vector is a column vector I
:
P
→
Z indexed by P and a T-vector is a column vector J
:
T
→
Z indexed by T, where Z is the set of integers. The column vectors where every entry equals 0
(
1
) are denoted by 0
(
1
). [
N
] is a |
P
|
×
|
T
| integer matrix with [
N
]
(
p
,
t
)
=
W
(
t
,
p
)
-
W
(
p
,
t
). I
T is the transposed versions of vector I. P-vector I is called a P-invariant if I
≠
0 and I
T
[
N
]
=
0
T and I
=
p
∣
I
(
p
)
≠
0 is the support of I. I is minimal if its support is not contained in the support of any other and its components are mutually prime. P-invariant I is a P-semiflow if its every element is nonnegative.


## 2.2. S3PR

In this subsection, we introduce a class of Petri nets, called S3PR, first defined in [12], which stands forSystems of Simple Sequential Processes with Resources and can model real-life automated FMSs.Definition 1 (see [12]).
An ordinary Petri netN
=
(
P
,
T
,
F
) is called a state machine if, ∀
t
∈
T,  t
∙
=
|
t
∙
|
=
1. It is strongly connected if, ∀
x
,
y
∈
P
∪
T, there is a sequence of nodes x
,
a
,
b
,
…
,
c, and y such that (
x
,
a
)
,
(
a
,
b
)
,
…, and (
c
,
y
)
∈
F, where {
a
,
b
,
…
,
c
}
⊆
P
∪
T.Definition 2 (see [12]).
A simple sequential process (S2P) is a Petri net N
=
(
{
p
0
}
∪
P
A
,
T
,
F
), where P
A
≠
∅ is the set of operation places, p
0 is the idle process place, N is a strongly connected state machine, and the circuit of N contains p
0.Definition 3 (see [12]).
A simple sequential process with resources (S2PR) is a Petri net N
=
(
{
p
0
}
∪
P
A
∪
P
R
,
T
,
F
) such that (1)
the subnet generated byX
=
P
A
∪
{
p
0
}
∪
T is S2P,
(2)
P
R
≠
∅ and (
P
A
∪
{
p
0
}
)
∩
P
R
=
∅, where P
R is called the set of resource places,
(3)
∀
p
∈
P
A, ∀
t
∈
p
∙, ∀
t
′
∈
p
∙, ∃
r
p
∈
P
R, t
∙
∩
P
R
=
t
′
∙
∩
P
R
=
{
r
p
},
(4)
(a)∀
r
∈
P
R, r
∙
∙
∩
P
A
=
r
∙
∙
∩
P
A
≠
∅ and (b), ∀
r
∈
P
R, r
∙
∩
r
∙
=
∅,
(5)
(
p
0
)
∙
∙
∩
P
R
=
(
p
0
)
∙
∙
∩
P
R
=
∅.Definition 4 (see [12]).
S3PR is a system of S2PR, defined as follows: (1)
An S2PR is an S3PR.
(2)
LetN
i
=
(
{
p
i
0
}
∪
P
A
i
∪
P
R
i
,
T
i
,
F
i
), i
∈
{
1,2
}, be two S3PR such that (
P
A
1
∪
{
p
1
0
}
)
∩
(
P
A
2
∪
{
p
2
0
}
)
=
∅, P
R
1
∩
P
R
2
=
P
C
≠
∅, and T
1
∩
T
2
=
∅. Then, combine N
1 and N
2 via P
C into a net N
=
P
0
∪
P
A
∪
P
R
,
T
,
F. N is also an S3PR, defined as follows: (1) P
A
=
P
A
1
∪
P
A
2, (2) P
0
=
{
p
1
0
}
∪
{
p
2
0
}, (3) P
R
=
P
R
1
∪
P
R
2, (4) T
=
T
1
∪
T
2, and (5) F
=
F
1
∪
F
2.Transitions in(
P
0
)
∙ are calledsource transitions, which represent the entry of raw materials when FMS is modeled with an S3PR.Definition 5 (see [12]).
Forr
∈
P
R, H
(
r
)
=
r
∙
∙
∩
P
A is called the set of holders of r, which represent the operation places that use r. Let S be s siphon and S
R
=
S
∩
P
R; [
S
]
=
(
∪
r
∈
S
R
H
(
r
)
)
∖
S is called thecomplementary set of S.Theorem 6 (see [12]).
An S3PR (
N
,
M
0
) is live if, ∀
M
∈
R
(
N
,
M
0
), ∀
S
∈
Π, M
(
S
)
>
0.LetΠ be the set of SMSs in an S3PR. The above theorem indicates that an S3PR is live if there is no siphon that can be emptied.


## 2.3. MIP Technique

Let(
N
,
M
) be an ordinary net with N
=
(
P
,
T
,
F
) and let S be the maximal unmarked siphon at M; that is, ∀
p
∉
S, M
(
p
)
>
0. In the sequel, we introduce a technique, first proposed in [40], to find S in N by exploring the solution of a mixed integer programming (MIP) problem. ∀
p
∉
S, let v
p
=
1 and, ∀
t
∉
S
∙, let z
t
=
1.SinceS is a siphon and, ∀
p
∉
S, M
(
p
)
>
0, any p with v
p
=
1 and any t with z
t
=
1 should be removed from the solution. Furthermore, ∀
t
∈
p
∙, v
p
=
0 implies z
t
=
0 and, ∀
p
∈
t
∙, z
t
=
1 implies the truth of v
p
=
1. This leads to(1)
z
t
≥
∑
p
∈
t
∙
v
p
-
t
∙
+
1
,
∀
t
∈
T
,
v
p
≥
z
t
,
∀
t
,
p
∈
F
,
v
p
,
z
t
∈
0,1
.For a structurally bounded net, we have(2)
v
p
≥
M
p
S
B
p
,
∀
p
∈
P
,where S
B
(
p
)
=
max
⁡
M
(
p
)
∣
M
=
M
0
+
[
N
]
Y
,
M
≥
0
,
Y
≥
0 denotes the structural bound of place p. Therefore, the maximal unmarked siphon can be determined by the following MIP problem and there exist siphons unmarked in (
N
,
M
0
) if G
M
I
P
(
M
0
)
<
|
P
|:(3)
G
M
I
P
M
0
=
M
i
n
i
m
i
z
e
∑
p
∈
P
v
psubject to constraints (1)-(2) and(4)
M
=
M
0
+
N
Y
,
M
≥
0
,
Y
≥
0
.Although MIP problems are NP-hard, it is shown in [40] that its computational efficiency is relatively insensitive to the initial marking and more efficient than state enumeration methods.Theorem 7 (see [40]).
Let(
N
,
M
0
) be an ordinary Petri net with N
=
(
P
,
T
,
F
). (
N
,
M
0
) is live if G
M
I
P
(
M
0
)
=
|
P
|.Theorem7 is used to check S3PR (
N
,
M
0
) whether liveness is enforced or not. If G
M
I
P
(
M
0
) equals the cardinality of the place set of N, it implies that (
N
,
M
0
) is live.However, the classical MIP problem to determine a maximal unmarked siphon in [40] only applies to ordinary Petri nets. As for a generalized Petri net, deadlocks may occur due to insufficiently marked siphons. Hence, the new conditions for checking whether there exist a maximal unmarked siphon in a generalized Petri net (
N
,
M
0
) with N
=
(
P
,
T
,
F
,
W
) are presented in [41], where a new constraint (5) is used to replace constraint (2):(5)
v
p
≥
M
p
-
W
p
,
t
+
1
S
B
p
,
∀
p
∈
P
,
∀
W
p
,
t
>
0
.The maximal unmarked siphon of a generalized Petri net(
N
,
M
0
) can be determined by the following MIP problem and there exist unmarked siphons if G
g
e
n
M
I
P
(
M
0
)
<
|
P
|:(6)
G
g
e
n
M
I
P
M
0
=
M
i
n
i
m
i
z
e
∑
p
∈
P
v
psubject to constraints (1) and (5) and(7)
M
=
M
0
+
N
Y
,
M
≥
0
,
Y
≥
0
.Theorem 8 (see [41]).
Let(
N
,
M
0
) be a generalized Petri net with N
=
(
P
,
T
,
F
,
W
). (
N
,
M
0
) is live if G
g
e
n
M
I
P
(
M
0
)
=
|
P
|.For a generalized Petri net(
N
,
M
0
), if G
g
e
n
M
I
P
(
M
0
) equals the cardinality of the place set of N, we can conclude that (
N
,
M
0
) is live.


## 3. Siphon Control Approach

In general, the presented method mainly contains two phases: siphon control phase and extended siphon control phase. The two phases are similar in finding siphons and the difference between them is the fashion of adding monitors for the siphons.First, we apply the MIP technique to a plant net to obtain a maximal unmarked siphon (if there exists one), derive a minimal siphon from the maximal one by the minimal siphon extraction algorithm in [42], and check liveness by solving an MIP problem of the plant net after enforcing a constraint imposed on the complementary set of the minimal siphons. Repeat the above process until the plant net is live under a set of constraints. After removing redundant constraints by a proposed algorithm, we add monitors to the complementary sets of the minimal siphons according to the remaining constraints. If in the resulting net there still exists a deadlock, we conduct the next phase.At the second phase, a newly presented constraint, different from the one claimed at Step  17 of Algorithm2 in [39], is enforced to the MIP problem of the resulting net of the first phase for preventing the system from reaching deadlock states. After iterations, we obtain a set of constraints and implement the constraints by adding monitors with the output arcs (with weights) pointing to the source transitions to avoid the generation of new problematic siphons. Then the output arcs of the monitors are rearranged to obtain a more permissive supervisor.


### 3.1. Siphon Control Phase

At this phase, for modeling a maximally permissive supervisor as much as possible, a monitor for an SMS is designed to be imposed on the complementary set of the SMSs.Definition 9 (see [39]).
LetS be an SMS in an S3PR (
N
,
M
0
). A monitor V
S for S is added to N to prevent S from being unmarked such that(1)
V
∙
S
=
t
∈
p
∙
∣
p
∈
[
S
]
,
p
∙
∙
∉
[
S
]; V
S
∙
=
t
∈
p
∙
∣
p
∈
S
,
p
∙
∙
∉
[
S
],
(2)
∀
t
∈
V
∙
S
,
W
(
t
,
V
S
)
=
1; ∀
t
∈
V
S
∙, W
(
V
S
,
t
)
=
1,
(3)
M
(
V
S
)
=
M
0
(
S
)
-
1,where W
(
V
S
,
t
) and W
(
t
,
V
S
) denote the weights of related arcs of V
S and M
(
V
S
) denotes the initial number of tokens in V
S.Theorem 10 (see [43]).
The addition ofV
S for S minimally restricts the behavior of a plant net.Definition9 shows the fashion of adding a monitor for an SMS at the first phase. In the sequel, we should identify SMSs that need to be controlled.In this study, the MIP technique is applied to iteratively find SMSs to avoid a complete siphon enumeration. For an S3PR (
N
,
M
0
), an SMS S can be found in N by the MIP technique if it is not live. A constraint ∑
p
∈
[
S
]
‍
M
(
p
)
≤
M
0
(
S
)
-
1 is enforced to the MIP problem of N, which implies that S cannot be unmarked any more in the MIP problem while the constraint minimally restricts the behavior of the plant net, where M
(
p
) is a variable of the MIP problem and denotes the number of tokens in p and M
0
(
S
) is the number of tokens in S at the initial marking. If N is live under the constraint, we just need to enforce the constraint by adding a corresponding monitor to N and end the first phase. Otherwise, we need to iterate and will obtain a set of constraints in the MIP problem, under which N can never reach deadlock states.However, if the number of constraints is more than one, there may be the case that not all the constraints are necessary. As mentioned in Introduction, some constraints can be replaced by the combination of other constraints and therefore they are redundant. Here, we propose an algorithm to exclude redundant constraints and the remaining ones are necessary.Algorithm1 eliminates redundancy by excluding a constraint each time. If the liveness is preserved after removing the constraint, we can conclude that the constraint is redundant and should be removed. Otherwise, it should be considered as necessary.Algorithm 1:Extraction of necessary constraints.
Input: A Petri net (
N, M
) and a set of constraints C
=
{
c
1
,
…
,
c
n
}.
Output: A set of necessary constraints C
N.
(1)begin
(2)C
N
≔
∅. ∖
∗  C
N denotes a set  of necessary constraints ∗
∖
(3)while  {
C
≠
∅
}
(3.1) Choose a constraintc
i from C; C
≔
C
∖
{
c
i
}.
(3.2) EnforceC
∪
C
N to the MIP problem of N.
(3.3)if  {there exists a maximal unmarked siphon}
(3.3.1)C
N
≔
C
N
∪
{
c
i
}.
(4) OutputC
N.
(5)endA necessary constraint corresponds to an SMS that needs to be controlled. The constraint is achieved by adding a monitor and related arcs to the plant net to prevent the corresponding SMS from being unmarked. Hence, a necessary constraint requires a monitor.Given an S3PR (
N
,
M
0
) with N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
), we enforce the necessary constraints by adding monitors according to Definition 9 and denote the resulting net as (N
1
,
M
1), where N
1
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
∪
F
1
,
W
1
) and P
V denotes the set of monitors V
S. Then,(1)
∀
p
∈
P
0
∪
P
A
∪
P
R
,
∀
t
∈
T
,
W
1
(
p
,
t
)
=
W
(
p
,
t
)
,
W
1
(
t
,
p
)
=
W
(
t
,
p
) and
(2)
∀
t
∈
V
∙
S
,
∀
V
S
∈
P
V
,
W
1
(
t
,
V
S
)
=
1; ∀
t
∈
V
S
∙
,
∀
V
S
∈
P
V
,
W
1
(
V
S
,
t
)
=
1,
(3)
∀
p
∈
P
A
∪
P
0
∪
P
R, M
1
(
p
)
=
M
0
(
p
),
(4)
∀
V
S
∈
P
V, M
1
(
V
S
) is the same as M
(
V
S
) in Definition 9.Theorem 11 (see [39]).
(
N
1
,
M
1
) is live if no siphon in N
1 can be emptied.Now, the S3PR net depicted in Figure 1(a) is taken as an example. It has 11 places, where {
p
1
,
p
5
} is the set of idle places, {
p
2
,
p
3
,
p
4
,
p
6
,
p
7
,
p
8
} is the set of operation places, and {
p
9
,
p
10
,
p
11
} is the set of resource places. Applying the MIP technique to the net, a maximal unmarked siphon {
p
4
,
p
7
,
p
8
,
p
9
,
p
10
,
p
11
} is found. An SMS can be derived from the maximal one, denoted as S
1
=
{
p
4
,
p
7
,
p
10
,
p
11
}, where p
10 and p
11 are resource places and {
p
3
,
p
7
} and {
p
4
,
p
6
} denote their holder sets, respectively. According to the definition of complementary sets, we have [
S
1
]
=
{
p
3
,
p
6
} and M
0
(
S
1
)
-
1
=
3
-
1
=
2. Constraint M
(
p
3
)
+
M
(
p
6
)
≤
2 is enforced to the MIP problem of the plant net to check whether the plant net is live under the constraint. If it is not live, we need to continue to find an SMS and enforce a corresponding constraint to the MIP problem of the plant net. After three iterations, the plant net is live under three derived constraints. We find that there exists no redundant constraint by applying Algorithm 1. Three monitors are added by Definition 9 and shown in Figure 1(b).Figure 1
(a) An S3PR (
N
,
M
0
) and (b) a controlled system of N.
(a)
(b)We find that all of the above three constraints are necessary. However, if we change the initial marking of the net in Figure1(a) to the one shown in Figure 2(a), we may find three constraints in turn:(8)
M
p
2
+
M
p
3
+
M
p
6
+
M
p
7
≤
4
,
(9)
M
p
2
+
M
p
7
≤
2
,
(10)
M
p
3
+
M
p
6
≤
2
.Figure 2
(a) An S3PR (
N
,
M
0
) and (b) a controlled system of N.
(a)
(b)If constraint (8) can be found first, we still require constraints (9) and (10) to guarantee liveness, which makes constraint (8) redundant. Consequently, Algorithm 1 becomes an essential tool to deal with this condition. The controlled net is shown in Figure 2(b).In fact, the condition of Theorem11 is not always met. Newly added monitors and resource places may coproduce new siphons. Therefore, the second phase is proposed to solve this problem.


### 3.2. Extended Siphon Control Phase

In this subsection, we still utilize the MIP-based deadlock detection method to find siphons (if there exist ones). In order to avoid the case that the added monitors take part in generating new siphons (i.e., control-induced siphons), the output arcs of monitors (with weighted arcs) added at this phase are pointed to source transitions first. Then the output arcs are rearranged to be far away from the source transitions to release legal states. The following definitions are presented to introduce the fashion of adding a monitor for an SMS at the second phase.Definition 12.
Let(
N
,
M
0
) be an S3PR, let p
0 be the idle place of a process, and let p
a and p
b be different operation places in the process. If p
b can be found in the process path (in accordance with the direction of the arrows of the process flow) from p
a to p
0 (p
a and p
0 are not included), p
b is called a downstream place of p
a, denoted as p
b
≺
p
a, and p
a is called an upstream place of p
b, denoted as p
a
≻
p
b.Definition 13.
Letp be an operation place of an S3PR. P
D
(
p
)
=
q
∣
q
≺
p is called the set of downstream places of p and P
U
(
p
)
=
q
∣
q
≻
p is called the set of upstream places of p.Definition 14.
LetS be an SMS of an S3PR, let [
S
] be the complementary set of S, and let p be an operation place in [
S
]. P
U
(
[
S
]
)
=
⋃
p
∈
S
q
∣
q
∈
P
U
(
p
)
∧
q
∉
[
S
] is called the set of upstream places of [
S
] and P
U
i
(
[
S
]
)
=
P
U
(
[
S
]
)
∩
P
A
i is called the set of upstream places of [
S
] in process i, where P
A
i denotes the set of operation places in process i.Take the S3PR net (
N
,
M
0
) depicted in Figure 1(a) as an example. p
4 is a downstream place of p
3, denoted as p
4
≺
p
3. p
2 is an upstream place of p
3, denoted as p
2
≻
p
3. Moreover, p
3 and p
4 are the downstream places of p
2, denoted as P
D
(
p
2
)
=
{
p
3
,
p
4
}. p
2 and p
3 are the upstream places of p
4, denoted as P
U
(
p
4
)
=
{
p
2
,
p
3
}. It is supposed that P
A
1
=
{
p
2
,
p
3
,
p
4
} and P
A
2
=
{
p
6
,
p
7
,
p
8
}. S
1
=
{
p
4
,
p
7
,
p
10
,
p
11
} and S
2
=
{
p
3
,
p
8
,
p
9
,
p
10
} are two SMSs in N. P
U
(
[
S
1
]
)
=
{
p
2
}, P
U
1
(
[
S
1
]
)
=
{
p
2
}, and P
U
2
(
[
S
1
]
)
=
∅. Similarly, P
U
(
[
S
2
]
)
=
{
p
6
}, P
U
1
(
[
S
1
]
)
=
∅, and P
U
2
(
[
S
1
]
)
=
{
p
6
}.Definition 15.
LetS be an SMS of (
N
1
,
M
1
) with N
1
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
∪
F
1
). The complementary set of S is defined as S
=
⋃
V
S
∈
S
H
V
S
⋃
r
∈
S
H
r
∖
S, where V
S
∈
P
V and r
∈
P
R. [
S
] can be written in the multiset form T
h
S
=
∑
p
∈
H
(
V
S
)
‍
p
+
∑
p
∈
H
(
r
)
‍
p
-
∑
p
∈
S
‍
p and T
h
S
(
p
) represents the coefficient of p.Suppose thatT
h
S
=
a
·
p
l
+
b
·
p
m
+
c
·
p
n, and we have T
h
S
(
p
l
)
=
a, T
h
S
(
p
m
)
=
b, and T
h
S
(
p
n
)
=
c.Definition 16.
LetS be an SMS of (
N
1
,
M
1
). Q
S
(
p
)
=
max
⁡
{
m
a
x
q
∈
P
D
(
p
)
T
h
S
(
q
)
,
T
h
S
(
p
)
} is called the maximum demand for resources of p on S.Next, we illustrate the definition with the exampleT
h
S
=
a
·
p
l
+
b
·
p
m
+
c
·
p
n
+
⋯
+
r
·
p
x
+
s
·
p
y
+
t
·
p
z. Suppose that {
p
l
,
p
m
,
p
n
} is a set of operation places in a process with p
l
≻
p
m
≻
p
n while {
p
x
,
p
y
,
p
z
} is a set of operation places in another process, and we have P
D
(
p
l
)
=
{
p
m
,
p
n
}, Q
S
(
p
l
)
=
max
⁡
{
T
h
S
(
p
l
)
,
T
h
S
(
p
m
)
,
T
h
S
(
p
n
)
}, P
D
(
p
m
)
=
{
p
n
}, and Q
S
(
p
m
)
=
max
⁡
{
T
h
S
(
p
m
)
,
T
h
S
(
p
n
)
}.Definition 17 (see [39]).
LetS be an SMS in (
N
1
,
M
1
). A monitor E
V
S for S is added to N
1 to prevent S from being unmarked such that(1)
∀
t
∈
P
0
∙
,
W
(
E
V
S
,
t
)
=
Q
S
(
p
)
(
p
∈
t
∙
∩
P
A
),
(2)
∀
t
∈
T
∖
P
0
∙
,
W
(
t
,
E
V
S
)
=
Q
S
(
p
)
-
Q
S
(
p
′
)
(
p
∈
t
∙
∩
P
A
,
p
′
∈
t
∙
∩
P
A
),
(3)
M
(
E
V
S
)
=
M
1
(
S
)
-
1,where W
(
E
V
S
,
t
) and W
(
t
,
E
V
S
) denote the weights of related arcs of E
V
S and M
(
E
V
S
) denotes the initial number of tokens in E
V
S.If(
N
1
,
M
1
) is not live, we can find an SMS S containing monitors added at the first phase. In [39], at the second stage, a constraint ∑
p
∈
[
S
]
‍
M
(
p
)
≤
M
1
(
S
)
-
1 is enforced to the MIP problem of N
1 to prevent S from being unmarked in the MIP problem, where M
(
p
) is a variable of the MIP problem and denotes the number of tokens in p, M
1
(
S
) is the number of tokens in S at M
1. By exprimental analysis, it is found that the constraint is imposed on the complementary set of S while the output arcs of monitors are pointed to source transitions to prevent the generation of control-induced siphons, which makes redundant constraints emerged. Hence, in the following, a new type of constraints is proposed to solve the problem.Based on Definitions12–16, we propose a new constraint, ∑
p
∈
[
S
]
∪
P
U
(
[
S
]
)
‍
Q
S
(
p
)
·
M
(
p
)
≤
M
1
(
S
)
-
1, to replace ∑
p
∈
[
S
]
‍
M
(
p
)
≤
M
1
(
S
)
-
1, where M
(
p
) is a variable of the MIP problem and denotes the number of tokens in p and M
1
(
S
) is the number of tokens in S at M
1. Similar to the first phase, for controlling the derived SMSs in the MIP problem, we can obtain one or a set of such constraints, under which N
1 is live. Applying Algorithm 1 to the constraints, we find a set of necessary constraints and each of them corresponds to an SMS that needs to be controlled.For the net(
N
1
,
M
1
) with N
1
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
∪
F
1
,
W
1
) obtained after the first phase, the necessary constraints are enforced by adding monitors to N
1 according to Definition 17 and the resulting net is denoted as (N
2
,
M
2), where N
2
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
,
W
2
) and P
E
V denotes the set of monitors E
V
S. Then,(1)
∀
p
∈
P
0
∪
P
A
∪
P
R
∪
P
V
,
∀
t
∈
T
,
W
2
(
p
,
t
)
=
W
1
(
p
,
t
)
,
W
2
(
t
,
p
)
=
W
1
(
t
,
p
),
(2)
∀
t
∈
T, ∀
E
V
S
∈
P
E
V, W
2
(
E
V
S
,
t
) and W
2
(
t
,
E
V
S
) are the same as W
(
E
V
S
,
t
) and W
(
t
,
E
V
S
) in Definition 17, respectively,
(3)
∀
p
∈
P
0
∪
P
A
∪
P
R
∪
P
V
,
M
2
(
p
)
=
M
1
(
p
),
(4)
∀
E
V
S
∈
P
E
V, M
2
(
E
V
S
) is the same as M
(
E
V
S
) in Definition 17.Theorem 18 (see [44]).
(
N
2
,
M
2
) is live.The fashion of adding monitors in Definition17 restricts the behavioral permissiveness while avoiding the generation of control-induced siphons. Hence, we utilize Algorithm 2 to release legal states.Algorithm 2:Synthesis of a more permissive supervisor.
Input: Net (
N
2, M
2
) with N
2
=
(
P
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
,
W
2
).
Output: A more permissive supervisor (
N
2
′, M
2
′
).
(1)begin
(2)P
E
V
fin
≔
∅. ∖
∗  P
E
V
fin denotes the set of monitors with rearranged output arcs ∗
∖
(3)while  {
P
E
V
≠
∅
}
(3.1) Choose a monitorE
V
S from P
E
V; P
E
V
≔
P
E
V
∖
{
E
V
S
}; P
m
1
≔
P
∪
P
V
∪
P
E
V
∪
P
E
V
fin.
The resulting net is denoted by(
N
m
1, M
m
1
), where N
m
1
=
(
P
m
1
,
T
,
F
∪
F
1
∪
F
m
1
,
W
m
1
).
(3.2) FindP
U
(
[
S
]
)
=
⋃
i
∈
K
P
U
i
(
[
S
]
), where K
=
{
1
,
…
,
k
} and k is the total number of processes.
∖
∗  S is the SMS controlled by E
V
S  ∗
∖
(3.3)foreach  P
U
i
(
[
S
]
)
(
0
<
i
<
k
+
1
),
(3.3.1)P
I
R
≔
{
p
i
0
}
•
•; P
I
R
′
≔
∅; P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∖
P
U
i
(
[
S
]
).
∖
∗  P
I
R and P
I
R
′ denote two sets of operation places ∗
∖
(3.3.2)while  {
P
I
R
≠
∅
}
(3.3.2.1) Choosep
∈
P
I
R; P
I
R
≔
P
I
R
∖
{
p
}.
(3.3.2.2)P
U
i
(
[
S
]
)
≔
P
U
i
(
[
S
]
)
∖
{
p
}; P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∪
P
U
i
(
[
S
]
).
(3.3.2.3)E
V
S with rearranged output arcs is added to (
N
m
1, M
m
1
)
such thatE
V
S
+
∑
p
∈
P
U
(
[
S
]
)
p
+
∑
p
∈
[
S
]
p is a P-invariant of the resulting net,
denoted by(
N
m
2, M
m
2
), where N
m
2
=
(
P
m
2
,
T
,
F
∪
F
1
∪
F
m
2
,
W
m
2
) and P
m
2
=
P
m
1
∪
{
E
V
S
}.
(3.3.2.4)if  {
G
gen
MIP
(
M
m
2
)
=
P
m
2
}
(3.3.2.4.1)P
I
R
′
≔
P
I
R
′
∪
{
p
}.
(3.3.2.5)else
(3.3.2.5.1)P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∖
P
U
i
(
[
S
]
); P
U
i
(
[
S
]
)
≔
P
U
i
(
[
S
]
)
∪
{
p
}; P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∪
P
U
i
(
[
S
]
).
(3.3.2.6) RemoveE
V
S from (
N
m
2, M
m
2
) and obtain (
N
m
1, M
m
1
).
(3.3.3)if  {
P
I
R
′
≠
∅
}
(3.3.3.1)P
I
R
≔
P
I
R
′
•
•; P
I
R
′
≔
∅; go to (3.3.2)
(3.4)E
V
S with rearranged output arcs is added to (
N
m
1, M
m
1
) such that E
V
S
+
∑
p
∈
P
U
(
[
S
]
)
p
+
∑
p
∈
[
S
]
p is a P-invariant
of the resulting net, denoted by(
N
2
′, M
2
′
); P
E
V
fin
≔
P
E
V
fin
∪
{
E
V
S
}.
(4) Output(
N
2
′, M
2
′
) with N
2
′
=
(
P
∪
P
V
∪
P
E
V
fin
,
T
,
F
∪
F
1
∪
F
2
′
,
W
2
′
).
(5)endAlgorithm2 aims to construct a more permissive supervisor, which releases most legal states. For each monitor added by Definition 17, move each of its output arcs that originally points to a source transition step by step away from the source transition. Note that all the movements are implemented on condition that the liveness is preserved and the liveness is checked by the MIP problem for generalized Petri nets.Theorem 19.
(
N
2
′
,
M
2
′
) is live.Proof.
(
N
2
′
,
M
2
′
) is obtained based on the rearrangements of the output arcs of monitors in (
N
2
,
M
2
). By Theorem 18, it is found that (
N
2
,
M
2
) is live. In addition, each movement of the output arcs is implemented on condition that G
g
e
n
M
I
P
(
M
m
2
) ((
N
m
2
,
M
m
2
) denotes the resulting net of each movement) equals the cardinality of the place set of N
m
2, which implies that there is no unmarked siphon. According to Theorem 8, (
N
2
′
,
M
2
′
) is live.For the S3PR shown in Figure 3, the number of its maximally permissive states is 891. The first phase leads to 12 monitors, as shown in Table 1. The resulting net is denoted as (
N
1
,
M
1
). However, there still exist maximal unmarked siphons rendering deadlocks. Two minimal siphons S
13
=
{
p
5
,
p
10
,
p
16
,
p
21
,
p
22
,
p
24
,
p
25
,
V
S
4
,
V
S
6
,
V
S
8
} and S
14
=
{
p
5
,
p
10
,
p
16
,
p
21
,
p
22
,
p
24
,
p
25
,
V
S
3, V
S
4
,
V
S
9
} can be derived. The multisets of [
S
13
] and [
S
14
] are presented as below. N
1 is live under constraints (12) and (13).Table 1
Monitors added at the first phase.
V
S
i
M
1
(
V
S
i
)
Preset
Postset
V
S
i
M
1
(
V
S
i
)
Preset
Postset
V
S
1
4
t
4
,
t
9
,
t
15
,
t
20
t
1
,
t
6
,
t
11
t
17
V
S
2
3
t
4
,
t
7
,
t
15
,
t
20
t
1
,
t
6
,
t
11
,
t
17
V
S
3
3
t
3
,
t
8
,
t
14
,
t
19
t
1
,
t
6
,
t
11
,
t
17
V
S
4
3
t
4
,
t
9
,
t
20
t
1
,
t
6
,
t
17
V
S
5
2
t
4
,
t
20
t
1
,
t
17
V
S
6
3
t
2
,
t
9
,
t
15
,
t
18
t
1
,
t
6
,
t
11
,
t
17
V
S
7
1
t
12
,
t
18
t
11
,
t
17
V
S
8
2
t
3
,
t
7
,
t
14
t
1
,
t
6
,
t
11
V
S
9
2
t
14
,
t
19
t
11
,
t
17
V
S
10
2
t
2
,
t
9
t
1
,
t
6
V
S
11
2
t
8
,
t
12
,
t
18
t
6
,
t
11
,
t
17
V
S
12
1
t
14
t
11Figure 3
An S3PR example.Multisets are as follows:(11)
T
h
S
13
=
2
p
2
+
p
3
+
p
4
+
2
p
7
+
2
p
8
+
2
p
9
+
3
p
12
+
2
p
13
+
3
p
14
+
p
15
+
2
p
18
+
2
p
19
+
p
20
,
T
h
S
14
=
3
p
2
+
p
3
+
p
4
+
2
p
7
+
2
p
8
+
3
p
9
+
2
p
12
+
p
13
+
2
p
14
+
p
15
+
p
18
+
p
19
+
p
20
.Constraints are as follows:(12)
2
M
p
2
+
M
p
3
+
M
p
4
+
2
M
p
7
+
2
M
p
8
+
2
M
p
9
+
3
M
p
12
+
3
M
p
13
+
3
M
p
14
+
M
p
15
+
2
M
p
18
+
2
M
p
19
+
M
p
20
≤
9
,
(13)
3
M
p
2
+
M
p
3
+
M
p
4
+
3
M
p
7
+
3
M
p
8
+
3
M
p
9
+
2
M
p
12
+
2
M
p
13
+
2
M
p
14
+
M
p
15
+
M
p
18
+
M
p
19
+
M
p
20
≤
9
.It is found that constraint (10) is redundant by applying Algorithm 1. According to constraint (12), E
V
S
13 with its output arcs pointed to source transitions, as shown in Figure 4(a), is added to N
1 by Definition 17. The resulting net N
2 is live and it has 870 reachable states. Finally, we find E
V
S
13 with rearranged output arcs by Algorithm 2, as depicted in Figure 4(b). We denote the resulting net as N
2
′. It is live and has 878 reachable states that are very close to the number of maximally permissive states.Figure 4
MonitorE
V
S
13 (a) with original output arcs and (b) with rearranged output arcs.
(a)
(b)


## 3.1. Siphon Control Phase

At this phase, for modeling a maximally permissive supervisor as much as possible, a monitor for an SMS is designed to be imposed on the complementary set of the SMSs.Definition 9 (see [39]).
LetS be an SMS in an S3PR (
N
,
M
0
). A monitor V
S for S is added to N to prevent S from being unmarked such that(1)
V
∙
S
=
t
∈
p
∙
∣
p
∈
[
S
]
,
p
∙
∙
∉
[
S
]; V
S
∙
=
t
∈
p
∙
∣
p
∈
S
,
p
∙
∙
∉
[
S
],
(2)
∀
t
∈
V
∙
S
,
W
(
t
,
V
S
)
=
1; ∀
t
∈
V
S
∙, W
(
V
S
,
t
)
=
1,
(3)
M
(
V
S
)
=
M
0
(
S
)
-
1,where W
(
V
S
,
t
) and W
(
t
,
V
S
) denote the weights of related arcs of V
S and M
(
V
S
) denotes the initial number of tokens in V
S.Theorem 10 (see [43]).
The addition ofV
S for S minimally restricts the behavior of a plant net.Definition9 shows the fashion of adding a monitor for an SMS at the first phase. In the sequel, we should identify SMSs that need to be controlled.In this study, the MIP technique is applied to iteratively find SMSs to avoid a complete siphon enumeration. For an S3PR (
N
,
M
0
), an SMS S can be found in N by the MIP technique if it is not live. A constraint ∑
p
∈
[
S
]
‍
M
(
p
)
≤
M
0
(
S
)
-
1 is enforced to the MIP problem of N, which implies that S cannot be unmarked any more in the MIP problem while the constraint minimally restricts the behavior of the plant net, where M
(
p
) is a variable of the MIP problem and denotes the number of tokens in p and M
0
(
S
) is the number of tokens in S at the initial marking. If N is live under the constraint, we just need to enforce the constraint by adding a corresponding monitor to N and end the first phase. Otherwise, we need to iterate and will obtain a set of constraints in the MIP problem, under which N can never reach deadlock states.However, if the number of constraints is more than one, there may be the case that not all the constraints are necessary. As mentioned in Introduction, some constraints can be replaced by the combination of other constraints and therefore they are redundant. Here, we propose an algorithm to exclude redundant constraints and the remaining ones are necessary.Algorithm1 eliminates redundancy by excluding a constraint each time. If the liveness is preserved after removing the constraint, we can conclude that the constraint is redundant and should be removed. Otherwise, it should be considered as necessary.Algorithm 1:Extraction of necessary constraints.
Input: A Petri net (
N, M
) and a set of constraints C
=
{
c
1
,
…
,
c
n
}.
Output: A set of necessary constraints C
N.
(1)begin
(2)C
N
≔
∅. ∖
∗  C
N denotes a set  of necessary constraints ∗
∖
(3)while  {
C
≠
∅
}
(3.1) Choose a constraintc
i from C; C
≔
C
∖
{
c
i
}.
(3.2) EnforceC
∪
C
N to the MIP problem of N.
(3.3)if  {there exists a maximal unmarked siphon}
(3.3.1)C
N
≔
C
N
∪
{
c
i
}.
(4) OutputC
N.
(5)endA necessary constraint corresponds to an SMS that needs to be controlled. The constraint is achieved by adding a monitor and related arcs to the plant net to prevent the corresponding SMS from being unmarked. Hence, a necessary constraint requires a monitor.Given an S3PR (
N
,
M
0
) with N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
), we enforce the necessary constraints by adding monitors according to Definition 9 and denote the resulting net as (N
1
,
M
1), where N
1
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
∪
F
1
,
W
1
) and P
V denotes the set of monitors V
S. Then,(1)
∀
p
∈
P
0
∪
P
A
∪
P
R
,
∀
t
∈
T
,
W
1
(
p
,
t
)
=
W
(
p
,
t
)
,
W
1
(
t
,
p
)
=
W
(
t
,
p
) and
(2)
∀
t
∈
V
∙
S
,
∀
V
S
∈
P
V
,
W
1
(
t
,
V
S
)
=
1; ∀
t
∈
V
S
∙
,
∀
V
S
∈
P
V
,
W
1
(
V
S
,
t
)
=
1,
(3)
∀
p
∈
P
A
∪
P
0
∪
P
R, M
1
(
p
)
=
M
0
(
p
),
(4)
∀
V
S
∈
P
V, M
1
(
V
S
) is the same as M
(
V
S
) in Definition 9.Theorem 11 (see [39]).
(
N
1
,
M
1
) is live if no siphon in N
1 can be emptied.Now, the S3PR net depicted in Figure 1(a) is taken as an example. It has 11 places, where {
p
1
,
p
5
} is the set of idle places, {
p
2
,
p
3
,
p
4
,
p
6
,
p
7
,
p
8
} is the set of operation places, and {
p
9
,
p
10
,
p
11
} is the set of resource places. Applying the MIP technique to the net, a maximal unmarked siphon {
p
4
,
p
7
,
p
8
,
p
9
,
p
10
,
p
11
} is found. An SMS can be derived from the maximal one, denoted as S
1
=
{
p
4
,
p
7
,
p
10
,
p
11
}, where p
10 and p
11 are resource places and {
p
3
,
p
7
} and {
p
4
,
p
6
} denote their holder sets, respectively. According to the definition of complementary sets, we have [
S
1
]
=
{
p
3
,
p
6
} and M
0
(
S
1
)
-
1
=
3
-
1
=
2. Constraint M
(
p
3
)
+
M
(
p
6
)
≤
2 is enforced to the MIP problem of the plant net to check whether the plant net is live under the constraint. If it is not live, we need to continue to find an SMS and enforce a corresponding constraint to the MIP problem of the plant net. After three iterations, the plant net is live under three derived constraints. We find that there exists no redundant constraint by applying Algorithm 1. Three monitors are added by Definition 9 and shown in Figure 1(b).Figure 1
(a) An S3PR (
N
,
M
0
) and (b) a controlled system of N.
(a)
(b)We find that all of the above three constraints are necessary. However, if we change the initial marking of the net in Figure1(a) to the one shown in Figure 2(a), we may find three constraints in turn:(8)
M
p
2
+
M
p
3
+
M
p
6
+
M
p
7
≤
4
,
(9)
M
p
2
+
M
p
7
≤
2
,
(10)
M
p
3
+
M
p
6
≤
2
.Figure 2
(a) An S3PR (
N
,
M
0
) and (b) a controlled system of N.
(a)
(b)If constraint (8) can be found first, we still require constraints (9) and (10) to guarantee liveness, which makes constraint (8) redundant. Consequently, Algorithm 1 becomes an essential tool to deal with this condition. The controlled net is shown in Figure 2(b).In fact, the condition of Theorem11 is not always met. Newly added monitors and resource places may coproduce new siphons. Therefore, the second phase is proposed to solve this problem.


## 3.2. Extended Siphon Control Phase

In this subsection, we still utilize the MIP-based deadlock detection method to find siphons (if there exist ones). In order to avoid the case that the added monitors take part in generating new siphons (i.e., control-induced siphons), the output arcs of monitors (with weighted arcs) added at this phase are pointed to source transitions first. Then the output arcs are rearranged to be far away from the source transitions to release legal states. The following definitions are presented to introduce the fashion of adding a monitor for an SMS at the second phase.Definition 12.
Let(
N
,
M
0
) be an S3PR, let p
0 be the idle place of a process, and let p
a and p
b be different operation places in the process. If p
b can be found in the process path (in accordance with the direction of the arrows of the process flow) from p
a to p
0 (p
a and p
0 are not included), p
b is called a downstream place of p
a, denoted as p
b
≺
p
a, and p
a is called an upstream place of p
b, denoted as p
a
≻
p
b.Definition 13.
Letp be an operation place of an S3PR. P
D
(
p
)
=
q
∣
q
≺
p is called the set of downstream places of p and P
U
(
p
)
=
q
∣
q
≻
p is called the set of upstream places of p.Definition 14.
LetS be an SMS of an S3PR, let [
S
] be the complementary set of S, and let p be an operation place in [
S
]. P
U
(
[
S
]
)
=
⋃
p
∈
S
q
∣
q
∈
P
U
(
p
)
∧
q
∉
[
S
] is called the set of upstream places of [
S
] and P
U
i
(
[
S
]
)
=
P
U
(
[
S
]
)
∩
P
A
i is called the set of upstream places of [
S
] in process i, where P
A
i denotes the set of operation places in process i.Take the S3PR net (
N
,
M
0
) depicted in Figure 1(a) as an example. p
4 is a downstream place of p
3, denoted as p
4
≺
p
3. p
2 is an upstream place of p
3, denoted as p
2
≻
p
3. Moreover, p
3 and p
4 are the downstream places of p
2, denoted as P
D
(
p
2
)
=
{
p
3
,
p
4
}. p
2 and p
3 are the upstream places of p
4, denoted as P
U
(
p
4
)
=
{
p
2
,
p
3
}. It is supposed that P
A
1
=
{
p
2
,
p
3
,
p
4
} and P
A
2
=
{
p
6
,
p
7
,
p
8
}. S
1
=
{
p
4
,
p
7
,
p
10
,
p
11
} and S
2
=
{
p
3
,
p
8
,
p
9
,
p
10
} are two SMSs in N. P
U
(
[
S
1
]
)
=
{
p
2
}, P
U
1
(
[
S
1
]
)
=
{
p
2
}, and P
U
2
(
[
S
1
]
)
=
∅. Similarly, P
U
(
[
S
2
]
)
=
{
p
6
}, P
U
1
(
[
S
1
]
)
=
∅, and P
U
2
(
[
S
1
]
)
=
{
p
6
}.Definition 15.
LetS be an SMS of (
N
1
,
M
1
) with N
1
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
∪
F
1
). The complementary set of S is defined as S
=
⋃
V
S
∈
S
H
V
S
⋃
r
∈
S
H
r
∖
S, where V
S
∈
P
V and r
∈
P
R. [
S
] can be written in the multiset form T
h
S
=
∑
p
∈
H
(
V
S
)
‍
p
+
∑
p
∈
H
(
r
)
‍
p
-
∑
p
∈
S
‍
p and T
h
S
(
p
) represents the coefficient of p.Suppose thatT
h
S
=
a
·
p
l
+
b
·
p
m
+
c
·
p
n, and we have T
h
S
(
p
l
)
=
a, T
h
S
(
p
m
)
=
b, and T
h
S
(
p
n
)
=
c.Definition 16.
LetS be an SMS of (
N
1
,
M
1
). Q
S
(
p
)
=
max
⁡
{
m
a
x
q
∈
P
D
(
p
)
T
h
S
(
q
)
,
T
h
S
(
p
)
} is called the maximum demand for resources of p on S.Next, we illustrate the definition with the exampleT
h
S
=
a
·
p
l
+
b
·
p
m
+
c
·
p
n
+
⋯
+
r
·
p
x
+
s
·
p
y
+
t
·
p
z. Suppose that {
p
l
,
p
m
,
p
n
} is a set of operation places in a process with p
l
≻
p
m
≻
p
n while {
p
x
,
p
y
,
p
z
} is a set of operation places in another process, and we have P
D
(
p
l
)
=
{
p
m
,
p
n
}, Q
S
(
p
l
)
=
max
⁡
{
T
h
S
(
p
l
)
,
T
h
S
(
p
m
)
,
T
h
S
(
p
n
)
}, P
D
(
p
m
)
=
{
p
n
}, and Q
S
(
p
m
)
=
max
⁡
{
T
h
S
(
p
m
)
,
T
h
S
(
p
n
)
}.Definition 17 (see [39]).
LetS be an SMS in (
N
1
,
M
1
). A monitor E
V
S for S is added to N
1 to prevent S from being unmarked such that(1)
∀
t
∈
P
0
∙
,
W
(
E
V
S
,
t
)
=
Q
S
(
p
)
(
p
∈
t
∙
∩
P
A
),
(2)
∀
t
∈
T
∖
P
0
∙
,
W
(
t
,
E
V
S
)
=
Q
S
(
p
)
-
Q
S
(
p
′
)
(
p
∈
t
∙
∩
P
A
,
p
′
∈
t
∙
∩
P
A
),
(3)
M
(
E
V
S
)
=
M
1
(
S
)
-
1,where W
(
E
V
S
,
t
) and W
(
t
,
E
V
S
) denote the weights of related arcs of E
V
S and M
(
E
V
S
) denotes the initial number of tokens in E
V
S.If(
N
1
,
M
1
) is not live, we can find an SMS S containing monitors added at the first phase. In [39], at the second stage, a constraint ∑
p
∈
[
S
]
‍
M
(
p
)
≤
M
1
(
S
)
-
1 is enforced to the MIP problem of N
1 to prevent S from being unmarked in the MIP problem, where M
(
p
) is a variable of the MIP problem and denotes the number of tokens in p, M
1
(
S
) is the number of tokens in S at M
1. By exprimental analysis, it is found that the constraint is imposed on the complementary set of S while the output arcs of monitors are pointed to source transitions to prevent the generation of control-induced siphons, which makes redundant constraints emerged. Hence, in the following, a new type of constraints is proposed to solve the problem.Based on Definitions12–16, we propose a new constraint, ∑
p
∈
[
S
]
∪
P
U
(
[
S
]
)
‍
Q
S
(
p
)
·
M
(
p
)
≤
M
1
(
S
)
-
1, to replace ∑
p
∈
[
S
]
‍
M
(
p
)
≤
M
1
(
S
)
-
1, where M
(
p
) is a variable of the MIP problem and denotes the number of tokens in p and M
1
(
S
) is the number of tokens in S at M
1. Similar to the first phase, for controlling the derived SMSs in the MIP problem, we can obtain one or a set of such constraints, under which N
1 is live. Applying Algorithm 1 to the constraints, we find a set of necessary constraints and each of them corresponds to an SMS that needs to be controlled.For the net(
N
1
,
M
1
) with N
1
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
∪
F
1
,
W
1
) obtained after the first phase, the necessary constraints are enforced by adding monitors to N
1 according to Definition 17 and the resulting net is denoted as (N
2
,
M
2), where N
2
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
,
W
2
) and P
E
V denotes the set of monitors E
V
S. Then,(1)
∀
p
∈
P
0
∪
P
A
∪
P
R
∪
P
V
,
∀
t
∈
T
,
W
2
(
p
,
t
)
=
W
1
(
p
,
t
)
,
W
2
(
t
,
p
)
=
W
1
(
t
,
p
),
(2)
∀
t
∈
T, ∀
E
V
S
∈
P
E
V, W
2
(
E
V
S
,
t
) and W
2
(
t
,
E
V
S
) are the same as W
(
E
V
S
,
t
) and W
(
t
,
E
V
S
) in Definition 17, respectively,
(3)
∀
p
∈
P
0
∪
P
A
∪
P
R
∪
P
V
,
M
2
(
p
)
=
M
1
(
p
),
(4)
∀
E
V
S
∈
P
E
V, M
2
(
E
V
S
) is the same as M
(
E
V
S
) in Definition 17.Theorem 18 (see [44]).
(
N
2
,
M
2
) is live.The fashion of adding monitors in Definition17 restricts the behavioral permissiveness while avoiding the generation of control-induced siphons. Hence, we utilize Algorithm 2 to release legal states.Algorithm 2:Synthesis of a more permissive supervisor.
Input: Net (
N
2, M
2
) with N
2
=
(
P
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
,
W
2
).
Output: A more permissive supervisor (
N
2
′, M
2
′
).
(1)begin
(2)P
E
V
fin
≔
∅. ∖
∗  P
E
V
fin denotes the set of monitors with rearranged output arcs ∗
∖
(3)while  {
P
E
V
≠
∅
}
(3.1) Choose a monitorE
V
S from P
E
V; P
E
V
≔
P
E
V
∖
{
E
V
S
}; P
m
1
≔
P
∪
P
V
∪
P
E
V
∪
P
E
V
fin.
The resulting net is denoted by(
N
m
1, M
m
1
), where N
m
1
=
(
P
m
1
,
T
,
F
∪
F
1
∪
F
m
1
,
W
m
1
).
(3.2) FindP
U
(
[
S
]
)
=
⋃
i
∈
K
P
U
i
(
[
S
]
), where K
=
{
1
,
…
,
k
} and k is the total number of processes.
∖
∗  S is the SMS controlled by E
V
S  ∗
∖
(3.3)foreach  P
U
i
(
[
S
]
)
(
0
<
i
<
k
+
1
),
(3.3.1)P
I
R
≔
{
p
i
0
}
•
•; P
I
R
′
≔
∅; P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∖
P
U
i
(
[
S
]
).
∖
∗  P
I
R and P
I
R
′ denote two sets of operation places ∗
∖
(3.3.2)while  {
P
I
R
≠
∅
}
(3.3.2.1) Choosep
∈
P
I
R; P
I
R
≔
P
I
R
∖
{
p
}.
(3.3.2.2)P
U
i
(
[
S
]
)
≔
P
U
i
(
[
S
]
)
∖
{
p
}; P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∪
P
U
i
(
[
S
]
).
(3.3.2.3)E
V
S with rearranged output arcs is added to (
N
m
1, M
m
1
)
such thatE
V
S
+
∑
p
∈
P
U
(
[
S
]
)
p
+
∑
p
∈
[
S
]
p is a P-invariant of the resulting net,
denoted by(
N
m
2, M
m
2
), where N
m
2
=
(
P
m
2
,
T
,
F
∪
F
1
∪
F
m
2
,
W
m
2
) and P
m
2
=
P
m
1
∪
{
E
V
S
}.
(3.3.2.4)if  {
G
gen
MIP
(
M
m
2
)
=
P
m
2
}
(3.3.2.4.1)P
I
R
′
≔
P
I
R
′
∪
{
p
}.
(3.3.2.5)else
(3.3.2.5.1)P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∖
P
U
i
(
[
S
]
); P
U
i
(
[
S
]
)
≔
P
U
i
(
[
S
]
)
∪
{
p
}; P
U
(
[
S
]
)
≔
P
U
(
[
S
]
)
∪
P
U
i
(
[
S
]
).
(3.3.2.6) RemoveE
V
S from (
N
m
2, M
m
2
) and obtain (
N
m
1, M
m
1
).
(3.3.3)if  {
P
I
R
′
≠
∅
}
(3.3.3.1)P
I
R
≔
P
I
R
′
•
•; P
I
R
′
≔
∅; go to (3.3.2)
(3.4)E
V
S with rearranged output arcs is added to (
N
m
1, M
m
1
) such that E
V
S
+
∑
p
∈
P
U
(
[
S
]
)
p
+
∑
p
∈
[
S
]
p is a P-invariant
of the resulting net, denoted by(
N
2
′, M
2
′
); P
E
V
fin
≔
P
E
V
fin
∪
{
E
V
S
}.
(4) Output(
N
2
′, M
2
′
) with N
2
′
=
(
P
∪
P
V
∪
P
E
V
fin
,
T
,
F
∪
F
1
∪
F
2
′
,
W
2
′
).
(5)endAlgorithm2 aims to construct a more permissive supervisor, which releases most legal states. For each monitor added by Definition 17, move each of its output arcs that originally points to a source transition step by step away from the source transition. Note that all the movements are implemented on condition that the liveness is preserved and the liveness is checked by the MIP problem for generalized Petri nets.Theorem 19.
(
N
2
′
,
M
2
′
) is live.Proof.
(
N
2
′
,
M
2
′
) is obtained based on the rearrangements of the output arcs of monitors in (
N
2
,
M
2
). By Theorem 18, it is found that (
N
2
,
M
2
) is live. In addition, each movement of the output arcs is implemented on condition that G
g
e
n
M
I
P
(
M
m
2
) ((
N
m
2
,
M
m
2
) denotes the resulting net of each movement) equals the cardinality of the place set of N
m
2, which implies that there is no unmarked siphon. According to Theorem 8, (
N
2
′
,
M
2
′
) is live.For the S3PR shown in Figure 3, the number of its maximally permissive states is 891. The first phase leads to 12 monitors, as shown in Table 1. The resulting net is denoted as (
N
1
,
M
1
). However, there still exist maximal unmarked siphons rendering deadlocks. Two minimal siphons S
13
=
{
p
5
,
p
10
,
p
16
,
p
21
,
p
22
,
p
24
,
p
25
,
V
S
4
,
V
S
6
,
V
S
8
} and S
14
=
{
p
5
,
p
10
,
p
16
,
p
21
,
p
22
,
p
24
,
p
25
,
V
S
3, V
S
4
,
V
S
9
} can be derived. The multisets of [
S
13
] and [
S
14
] are presented as below. N
1 is live under constraints (12) and (13).Table 1
Monitors added at the first phase.
V
S
i
M
1
(
V
S
i
)
Preset
Postset
V
S
i
M
1
(
V
S
i
)
Preset
Postset
V
S
1
4
t
4
,
t
9
,
t
15
,
t
20
t
1
,
t
6
,
t
11
t
17
V
S
2
3
t
4
,
t
7
,
t
15
,
t
20
t
1
,
t
6
,
t
11
,
t
17
V
S
3
3
t
3
,
t
8
,
t
14
,
t
19
t
1
,
t
6
,
t
11
,
t
17
V
S
4
3
t
4
,
t
9
,
t
20
t
1
,
t
6
,
t
17
V
S
5
2
t
4
,
t
20
t
1
,
t
17
V
S
6
3
t
2
,
t
9
,
t
15
,
t
18
t
1
,
t
6
,
t
11
,
t
17
V
S
7
1
t
12
,
t
18
t
11
,
t
17
V
S
8
2
t
3
,
t
7
,
t
14
t
1
,
t
6
,
t
11
V
S
9
2
t
14
,
t
19
t
11
,
t
17
V
S
10
2
t
2
,
t
9
t
1
,
t
6
V
S
11
2
t
8
,
t
12
,
t
18
t
6
,
t
11
,
t
17
V
S
12
1
t
14
t
11Figure 3
An S3PR example.Multisets are as follows:(11)
T
h
S
13
=
2
p
2
+
p
3
+
p
4
+
2
p
7
+
2
p
8
+
2
p
9
+
3
p
12
+
2
p
13
+
3
p
14
+
p
15
+
2
p
18
+
2
p
19
+
p
20
,
T
h
S
14
=
3
p
2
+
p
3
+
p
4
+
2
p
7
+
2
p
8
+
3
p
9
+
2
p
12
+
p
13
+
2
p
14
+
p
15
+
p
18
+
p
19
+
p
20
.Constraints are as follows:(12)
2
M
p
2
+
M
p
3
+
M
p
4
+
2
M
p
7
+
2
M
p
8
+
2
M
p
9
+
3
M
p
12
+
3
M
p
13
+
3
M
p
14
+
M
p
15
+
2
M
p
18
+
2
M
p
19
+
M
p
20
≤
9
,
(13)
3
M
p
2
+
M
p
3
+
M
p
4
+
3
M
p
7
+
3
M
p
8
+
3
M
p
9
+
2
M
p
12
+
2
M
p
13
+
2
M
p
14
+
M
p
15
+
M
p
18
+
M
p
19
+
M
p
20
≤
9
.It is found that constraint (10) is redundant by applying Algorithm 1. According to constraint (12), E
V
S
13 with its output arcs pointed to source transitions, as shown in Figure 4(a), is added to N
1 by Definition 17. The resulting net N
2 is live and it has 870 reachable states. Finally, we find E
V
S
13 with rearranged output arcs by Algorithm 2, as depicted in Figure 4(b). We denote the resulting net as N
2
′. It is live and has 878 reachable states that are very close to the number of maximally permissive states.Figure 4
MonitorE
V
S
13 (a) with original output arcs and (b) with rearranged output arcs.
(a)
(b)


## 4. Deadlock Prevention Algorithm

In this section, the proposed method is shaped to an algorithm to show how to synthesize a liveness-enforcing supervisor and a supporting example is given in Algorithm3.Algorithm 3:A liveness-enforcing policy.
Input: An S3PR (
N, M
0
) with N
=
(
P
,
T
,
F
).
Output: A liveness-enforcing net (
N
2
′, M
2
′
) with N
2
′
=
(
P
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
′
,
W
2
′
).
(1)begin
(2)C
S
C
≔
∅; P
V
≔
∅.  ∖
∗  C
S
C and P
V denote the sets of constraints in the MIP problem and monitors obtained
at the first phase, respectively∗
∖
(3) Apply MIP toN to obtain a maximal unmarked siphon.
(4)if  {there exists such a siphon}  then
(4.1) Obtain a minimal siphonS
i from the maximal one.
(4.2) Enforce a constraintc
i, ∑
p
∈
[
S
i
]
M
(
p
)
≤
M
0
(
S
i
)
-
1, to the MIP problem of N; C
S
C
≔
C
S
C
∪
{
c
i
}; go to step (3).
(5)if  {
C
S
C
=
∅
}  then  N
2
′
≔
N; M
2
′
≔
M
0; go to step (17).
(6) Apply Algorithm1 to C
S
C, obtain a set of necessary constraints C
N.
(7)foreach  c
i
∈
C
N,
(7.1) Add a corresponding monitorV
S
i to N by Definition 9.
(7.2)P
V
≔
P
V
∪
{
V
S
i
}.
(8) Obtain (N
1, M
1) and N
1
=
(
P
∪
P
V
,
T
,
F
∪
F
1
).
(9)C
E
S
C
≔
∅; P
E
V
≔
∅.  ∖
∗  C
E
S
C and P
E
V denote the sets of constraints in the MIP problem and monitors obtained
at the second phase, respectively∗
∖
(10) Apply MIP toN
1 to obtain a maximal unmarked siphon.
(11)if  {there exists such a siphon}  then
(11.1) Obtain a minimal siphon S
E
i from the maximal one.
(11.2) Enforce a constraint c
E
i, ∑
p
∈
[
S
E
i
]
∪
P
U
(
[
S
E
i
]
)
Q
S
(
p
)
⋅
M
(
p
)
≤
M
1
(
S
i
)
-
1, to the MIP problem of N
1;
C
E
S
C
≔
C
E
S
C
∪
{
c
E
i
}; go to step (10).
(12)if  {
C
E
S
C
=
∅
}  then  N
2
′
≔
N
1; M
2
′
≔
M
1; go to step (17).
(13) Apply Algorithm1 to C
E
S
C to obtain a set of necessary constraints C
E
N.
(14)foreach  c
E
i
∈
C
E
N,
(14.1) Add a corresponding monitorE
V
S
i to N
1 by Definition 17.
(14.2)P
E
V
≔
P
E
V
∪
{
E
V
S
i
}; N
2
=
(
P
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
,
W
2
).
(15) Obtain(
N
2, M
2
) and N
2
=
(
P
∪
P
V
∪
P
E
V
,
T
,
F
∪
F
1
∪
F
2
,
W
2
).
(16) Apply Algorithm2 to (
N
2, M
2
) to find (
N
2
′, M
2
′
).
(17) Output(
N
2
′, M
2
′
).
(18)endThe supervisor synthesized by Algorithm3 preserves the legal states of a plant net to a large extent on a basis of low computational complexity. The MIP-based deadlock detection approach is iteratively used to find unmarked siphons, which avoids a complete siphon enumeration and saves computational time. The first phase is optimal or maximally permissive in the sense that no legal states are excluded since a monitor is added to the complementary set of SMSs. However, it always makes the generation of control-induced siphons unavoidable while minimally restricting the behavior of a plant net. To accelerate the convergence, the output arcs of the monitors added at the second phase are first pointed to the source transitions of the plant net and subsequently rearranged away from the source transitions to release legal states on condition that the liveness is preserved. It guarantees the liveness as well as largely enhances the behavioral permissiveness. Hence, the policy in Algorithm 3 can synthesize a liveness-enforcing supervisor with low computational complexity.The Petri net shown in Figure5 is a well-known model of FMS [12]. We can define this Petri net model as an S3PR (
N
,
M
0
) if P
0
=
{
p
1
,
p
5
,
p
14
}, P
A
=
P
1
∪
P
2
∪
P
3
=
{
p
2
,
p
3
,
p
4
}
∪
{
p
6
,
p
7
,
p
8
,
p
9
,
p
10
,
p
11
,
p
12
,
p
13
}
∪
{
p
15
,
p
16
,
p
17
,
p
18
,
p
19
}, and P
R
=
{
p
20
,
p
21
,
p
22
,
p
23
,
p
24
,
p
25
,
p
26
}.Figure 5
The Petri net model of an FMS.The MIP technique is applied toN and a maximal unmarked siphon S
m
a
x
1
=
{
p
1
,
p
4
,
p
8
,
p
9
,
p
10
,
p
11
,
p
12
,
p
15
,
p
17
,
p
18
,
p
20
,
p
21
,
p
22
,
p
23
,
p
24
,
p
25
,
p
26
} can be obtained. A minimal siphon S
1
=
{
p
10
,
p
18
,
p
22
,
p
26
} can be derived from S
m
a
x
1. Thus, we have [
S
1
]
=
{
p
13
,
p
19
} and M
0
(
S
1
)
-
1
=
M
0
(
p
22
)
+
M
0
(
p
26
)
-
1
=
2. Constraint M
(
p
13
)
+
M
(
p
19
)
≤
2 is enforced to the MIP problem of N. Unfortunately, there still exists a maximal unmarked siphon. The above process proceeds until we find seven constraints under which N is live. There is no redundant constraint acquired by Algorithm 1 implying that there are seven SMSs to be controlled. Then we add seven monitors P
V
=
V
S
i
∣
i
∈
{
1
,
…
,
7
} to N by Definition 9, as shown in Table 2, and denote the resulting net as (
N
1
,
M
1
).Table 2
Monitors added at the first phase.
V
S
i
M
1
(
V
S
i
)
Preset
Postset
V
S
1
2
t
10
,
t
16
t
9
,
t
15
V
S
2
2
t
4
,
t
13
t
3
,
t
11
V
S
3
5
t
5
,
t
10
,
t
13
,
t
17
t
3
,
t
8
,
t
11
,
t
15
V
S
4
2
t
8
,
t
18
t
7
,
t
17
V
S
5
5
t
3
,
t
8
,
t
19
t
1
,
t
17
V
S
6
2
t
9
,
t
17
t
8
,
t
16
V
S
7
3
t
10
,
t
17
t
8
,
t
15Applying the MIP technique toN
1, we can still find a maximal unmarked siphon S
m
a
x
8
=
{
p
2
,
p
3
,
p
4
,
p
8
,
p
10
,
p
12
,
p
13
,
p
15
,
p
16
,
p
17
,
p
20
,
p
22
,
p
23
,
p
24
,
p
25
,
p
26
,
V
S
3
,
V
S
4
,
V
S
5
,
V
S
6
,
V
S
7
}. A minimal siphon S
8
=
{
p
13
,
p
17
,
p
26
,
V
S
4
,
V
S
6
} can be extracted from S
m
a
x
8, and the multisets form of its complementary set are T
h
S
8
=
p
11
+
p
12
+
2
p
18. We have M
1
(
S
8
)
-
1
=
M
1
(
p
26
)
+
M
1
(
V
S
4
)
+
M
1
(
V
S
6
)
-
1
=
2
+
2
+
2
-
1
=
5. Then constraint M
(
p
6
)
+
M
(
p
11
)
+
M
(
p
12
)
+
2
M
(
p
18
)
+
2
M
(
p
19
)
≤
5 is enforced to the MIP problem of N
1. However, there still exists a maximal unmarked siphon and N
1 requires another constraint to guarantee liveness. It is found that both constraints are necessary by Algorithm 1 and we add two monitors, P
E
V
=
E
V
S
i
∣
i
∈
{
8,9
}, as shown in Figure 6, to N
1 by Definition 17. The resulting net is denoted as (
N
2
,
M
2
).Figure 6
(a) MonitorsE
V
S
8 and (b) E
V
S
9.
(a)
(b)(
N
2
,
M
2
) excludes many legal states although it is live. The number of maximally permissive states of this plant model is 21581 while (
N
2
,
M
2
) preserves 19773 ones. Then we apply Algorithm 2 to (
N
2
,
M
2
) to rearrange the output arcs of monitors added at the second phase. The two monitors with rearranged output arcs are shown in Figure 7. The final net, denoted by (
N
2
′
,
M
2
′
), is live and it has 20444 reachable states.Figure 7
(a) MonitorsE
V
S
8 with rearranged output arcs and (b) E
V
S
9 with rearranged output arcs.
(a)
(b)


## 5. Comparison and Discussion

The performance of the proposed policy is shown in Table3 by calculating the example in Figure 5 compared with the existing methods. The first column represents the policies and the second column shows the number of reachable states. The third and fourth list the numbers of the added monitors and the related arcs, respectively. The fifth exhibits whether a complete siphon enumeration is necessary in a policy. Similarly, the sixth points out the necessity of a complete state enumeration. The seventh indicates the computational complexity.Table 3
Performance comparison of policies applied to the example in Figure5.
Policy referred to
Number of states
Number of monitors
Number of arcs
Complete siphon
Complete state
Computational complexity
Piroddi et al.  [45]
21581
13
82
✓
✗
Exponential
Ezpeleta et al.  [12]
6287
18
106
✓
✗
Exponential
Huang et al.  [39]
12656
16
88
✗
✗
NP-hard
Huang [47]
16425
7
34
✓
✗
Exponential
Li and Zhou [14]
6287
6
32
✓
✗
Exponential
Li et al.  [32]
6331
5
27
✗
✗
NP-hard
Li and Zhou [15]
15999
6
29
✗
✗
NP-hard
Park and Reveliotis [16]
2480
7
38
✓
✗
Polynomial
Tricas et al.  [17]
14850
8
40
✗
✗
NP-hard
Uzam and Zhou [46]
21562
19
112
✗
✓
Exponential
Xing and Hu [48]
15098
4
17
✓
✗
Exponential
The proposed policy
20444
9
45
✗
✗
NP-hardThe performance analysis of the policies is conducted by considering the following three criteria: behavioral permissiveness, computational complexity, and structural complexity. The advantage of the proposed policy can be analyzed in terms of the three criteria. The obtained supervisor by the proposed method of the net in Figure5 is suboptimal. However, the number of its reachable states is nearly maximally permissive, only a bit smaller than those of the policies in [45, 46] while the computational complexity of these policies is exponential, their supervisors have more monitors and arcs, and they need either a complete siphon enumeration or a complete reachability graph. The proposed policy, compared with the policies in [15, 17, 32, 39], can provide more reachable states.Among the policies listed in Table3, we choose four representative ones to compare with the proposed policy in Table 4 through ten examples (obtained by an S3PR-generating program of our work group except examples 7, 8, and 10), where number of RS and number of M denote the numbers of reachable states and the additonal monitors, respectively. The 12th and the last column indicate the maximally permissive behavior and the ratio of the reachable states of supervisors obtained by the proposed policy to the maximally permissive behavior, respectively. By the experimental study, we can find that the supervisor, synthesized by the proposed policy, has less monitors and is more permissive than the existing ones.Table 4
Performance analysis through ten examples.
Example
Ezpeleta et al. 1995 [12]
Huang et al. 2001 [39]
Li and Zhou 2006 [15]
Li et al. 2007 [32]
Proposed policy
Maximallypermissive behavior
Optimalityratio
Number of RS
Number of M
Number of RS
Number of M
Number of RS
Number of M
Number of RS
Number of M
Number of RS
Number of M
1
48
5
196
5
97
1
97
1
196
4
205
95.61%
2
268
5
336
4
268
3
268
3
336
4
336
100%
3
250
5
516
5
250
2
250
2
516
5
516
100%
4
103
11
632
6
118
3
112
3
632
5
632
100%
5
642
12
827
17
830
8
696
8
878
13
891
98.54%
6
792
6
1746
3
1572
2
800
2
1746
3
1746
100%
7 [49]
1463
13
2108
12
1591
4
1591
4
2108
10
2108
100%
8 [50]
585
8
2328
9
1518
3
594
3
2328
7
2328
100%
9
8500
11
16116
11
9000
11
8500
11
16116
11
16116
100%
10 [12]
6287
18
12656
16
15999
6
6331
6
20444
9
21581
94.73%


## 6. Conclusions

The deadlock prevention problem is always a tough and fussy task in FMSs. Behavioral permissiveness, computational complexity, and structural complexity are three criteria for checking the performance of supervisors. This work presents a deadlock prevention method for an S3PR. A siphon is a special set of places that can lead a system to a deadlock state. The MIP technique is iteratively used to find maximal unmarked siphons. Due to the high computational efficiency of the MIP method, we can save computation time substantially. At the first phase, in order to find a more permissive supervisor, monitors are added to the complementary sets of the derived minimal siphons. Unfortunately, the added monitors are always involved in the generation of control-induced siphons. Hence, at the second phase, a new fashion of adding monitors such that the output arcs of the monitors are pointed to source transitions is adopted to avoid generating control-induced siphons. Then the output arcs are moved from the source transitions along the opposite direction to the work flow for releasing legal states on condition that the liveness is preserved. In addition, this work proposes a redundant constraint removal algorithm that greatly reduces the structural complexity and enhances the behavioral permissiveness.



---

*Source: 579623-2015-12-01.xml*