# Comparison and Evaluation of Deadlock Prevention Methods for Different Size Automated Manufacturing Systems

Authors: Emad Abouel Nasr; Abdulaziz M. El-Tamimi; Abdulrahman Al-Ahmari; Husam Kaid
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In automated manufacturing systems (AMSs), deadlocks problems can arise due to limited shared resources. Petri nets are an effective tool to prevent deadlocks in AMSs. In this paper, a simulation based on existing deadlock prevention policies and different Petri net models are considered to explore whether a permissive liveness-enforcing Petri net supervisor can provide better time performance. The work of simulation is implemented as follows. (1) Assign the time to the controlled Petri net models, which leads to timed Petri nets. (2) Build the Petri net model using MATLAB software. (3) Run and simulate the model, and simulation results are analyzed to determine which existing policies are suitable for different systems. Siphons and iterative methods are used for deadlocks prevention. Finally, the computational results show that the selected deadlock policies may not imply high resource utilization and plant productivity, which have been shown theoretically in previous publications. However, for all selected AMSs, the iterative methods always lead to structurally and computationally complex liveness-enforcing net supervisors compared to the siphons methods. Moreover, they can provide better behavioral permissiveness than siphons methods for small systems. For large systems, a strict minimal siphon method leads to better behavioral permissiveness than the other methods.


---

## Body

## 1. Introduction

Effectively designing and operating an automated manufacturing system can be of assistance to manufacturers to adapt the variety in the market in order to maintain and confirm competitiveness. Different types of parts in AMS enter the system at discrete points of time and are produced concurrently; these parts have to share some common resources, such as robots, machine tools, buffers, automated guided vehicles, and fixtures. The deadlocks can occur in an AMS during its operation by shared resources competition, which are highly unwanted phenomena that often cause low use of some expensive and critical resources and long downtime and can lead to calamitous results in automated manufacturing systems. Therefore, it is required to develop a successful AMS control policy to prevent deadlocks occurrence in AMS.There are several mathematical tools to solve deadlock problems in AMSs including automata, graph theory, and Petri nets. Recently, Petri nets have been known as one of the most robust mathematical tools for modelling, analyzing, and controlling deadlocks in resource allocation systems including AMS [1]. To overcome the deadlocks in AMS, there are methods which have been derived from a Petri net tool either to forbid the deadlock occurrences by preventing some necessary condition or to detect and resolve a deadlock when it occurs. In general, these methods can be classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention [1, 2].The researchers proposed three criteria for designing and evaluating a supervisor for a manufacturing system to be controlled. These criteria include behavioral permissiveness, which leads to increase in the resources utilization of system, structural complexity that leads to design supervisor with a few number of monitors to decrease the software and hardware costs, and computational complexity that means a deadlock control policy can be implemented in huge systems [1]. Therefore, the objectives of many researchers are to develop deadlock prevention policies which can provide liveness-enforcing supervisors with maximal permissiveness, a structural complexity, and computational complexity [1].From previous studies, there are mainly two techniques of analysis for deadlock prevention in AMSs using Petri net: structural analysis [3, 4] and reachability graph analysis [5–7]. Oftentimes structural analysis is applied for structural objects of Petri nets, such as resource transition circuits and siphons. In this case, control steps are simple, and each empty minimal siphon requires a monitor to be added to prevent itself from being not emptied, but the disadvantages of this technique are the fact that the resulting controlled system can be suboptimal and linearly the number of control places is dependent on the size of a net [8].The reachability graph analysis suffers from a state explosion problem because it requires listing of all or a part of reachable markings. The reachability graph of a Petri net has been classified into two zones: live zone (LZ) and deadlock zone (DZ). In DZ, there is first-met bad markings (FBMs) which are extracted from it; the FBMs are representing the very first entry from LZ to DZ. In this case, a control place is designed and added to forbid the FBM from being reached. This process requires iterations to forbid all FBMs and single out each FBM. The process is terminated if the resulting net is a live [9]. There are several methods and algorithms used for deadlocks prevention; some of them are siphon control methods, a theory of region, and iterative methods [4, 6, 9–11].Most of the researchers have used structural analysis and reachability graph analysis to design deadlocks prevention policies for different scales of AMSs under three criteria that are maximal permissiveness, structural complexity, and computational complexity. The comparison between these policies has been done according to the three aforementioned criteria. It is taken for granted in the literature that a maximally permissive supervisor in the logical level usually leads to the better time performance in an AMS such as productivity and resource utilization, which looks intuitive, as an optimal supervisor will permit more permissive behavior. However, there is a shortage in the quantitative evaluation of time performance of these policies in terms of maximal permissiveness and productivity. Simulation is a powerful tool for performance analysis of complex manufacturing systems.The contribution of this paper is using a simulation tool based on existing deadlock prevention policies and different types of Petri net models to explore whether a permissive liveness-enforcing Petri net supervisor can provide better time performance (maximal permissiveness).The work of simulation is implemented in the following steps. (1) Assign the time to the controlled Petri net models, which leads to timed Petri nets. (2) Build the Petri net model using MATLAB software (Petri Net Toolbox (PN Toolbox)). (3) Run and simulate the model to obtain the system time performance. (4) Finally, the simulation results will be analyzed to determine which existing deadlock prevention policies are convenient for different types of manufacturing systems. Different control methods (siphon control methods and iterative methods) are used for deadlocks prevention. Moreover, this paper aims to evaluate the performance of the selected methods such as utilization of resources, plant throughput, the number of monitors, the number of arcs, and the number of reachable states. This paper focuses on the performance evaluation of automated manufacturing systems by using Petri nets under different deadlock prevention policies. The considered Petri net models belong toM-nets [12] that are a general class of manufacturing-oriented net models in the literature. In an M-net, there are a number of structural properties thanks to its definition [12].Including this introductory section, the paper is organized as follows. Section2 provides a literature review of previous researchers works related to deadlock prevention. The basics of Petri nets are discussed in Section 3. The deadlock prevention methods and policies are presented in Section 4. Sections 5 and 6 show the analysis of the selected methods for four different automated manufacturing systems. Finally, Section 7 presents the conclusion and future work.


## 2. Literature Review

Deadlock prevention policies have been widely achieved for AMS and led to a huge number of results [1, 11]. In this section, deadlock prevention strategies are reviewed by using Petri nets and developed based on different techniques such as structural analysis and reachability graph analysis.


### 2.1. Structural-Analysis Methods

Ezpeleta et al. [13] used a class of Petri nets, called System of Simple Sequential Processes with Resources (S3PR) and proposed an algorithm for resource allocation in flexible manufacturing systems (FMSs). The proposed algorithm added new places to the net to impose certain restrictions that forbid the presence of unmarked siphons. The works of Huang et al. [14] and Huang et al. [15] present a new deadlock prevention policy for the class of Petri nets, where deadlocks are related to unmarked siphons. Two types of control places are added to the original model for flexible manufacturing system called ordinary control place and weighted control place to prevent siphons from being unmarked.The study by Li and Zhou [11] presents a Petri net model which consists of 26 places, 20 transitions, and 18 strict minimal siphons. In [16], elementary siphons concept is introduced to design a liveness-enforcing Petri net supervisor for the same Petri net model, and six elementary siphons are obtained; therefore, only six monitors are added to control the 18 strict minimal siphons. Nevertheless, the proposed algorithm by Ezpeleta et al. [13] adds monitors for all 18 strict minimal siphons.A new methodology is proposed by Huang [17] to synthesize supervisors for resource allocation in FMSs; the class of Petri net, namely, S3PR, is considered, where deadlocks are related to unmarked minimal siphons; all minimal siphons should be controlled by adding control places. In this study, the number of control places is reduced by using the concept of the elementary siphon. Based on elementary siphons and P-invariants concepts in Petri nets, a deadlock prevention algorithm is introduced by Li and Wei for a specific class of Petri nets which can properly model several FMSs [16], siphons in a Petri net model are classified into dependent and elementary siphons, and control places are added for all elementary siphons, so that the siphons are invariant-controlled. Therefore, the controllability of dependent siphons is guaranteed by adjusting the control requirements of its related elementary siphons. A novel deadlock prevention algorithm is presented by Chen et al. [1], and the concept of siphon extraction is used to compute unmarked siphons for the Petri net model. First, a siphon extraction algorithm obtains a maximal unmarked siphon, divides the places in it, and determines a necessary siphon from the divided places; this process is carried out for all unmarked siphons. Then, the proposed deadlock prevention algorithm designs a convenient monitor for each necessary siphon to be marked until the controlled Petri net model is a live.Most of the deadlock control algorithms have been developed for reliable automated manufacturing systems (AMSs). Liu et al. [18] proposed a variety of deadlock control algorithms for AMSs with unreliable resources, monitors and recovery subnets are designed for strict minimal siphons (emptied siphon) and unreliable resources, respectively, and two types of arcs which are normal and inhibitor are used to connect monitors with recovery subnets. In order to obtain a supervisor with structural complexity, elementary siphons extracted from all strict minimal siphons are obviously controlled. The problems of structural complexity, behavioral permissiveness, and computational complexity are considered in the study of Wang et al. [19] to design liveness-enforcing supervisors for a class of Petri nets, namely, S3PR, without ξ-resources. They used two steps to obtain a supervisor for the model. In the first step, an algorithm is proposed to extract unmarked strict minimal siphons from a given unmarked siphon by using loop resource subsets. In the second step, a siphon-based deadlock prevention algorithm is introduced to provide a maximally permissive liveness-enforcing supervisor with small numbers and no weighted monitors.


### 2.2. Reachability Graph-Based Approaches

Viswanadham et al. [20] presented static resource allocation methods for eliminating deadlocks; in this study, a reachability graph of the Petri net (PN) model is used to reach static resource allocation method. A deadlock prevention algorithm is implemented for a small size manufacturing system consisting of a machine and an automated guided vehicle (AGV). The authors observed that the proposed algorithm can be applied effectively only for small size manufacturing systems. The forbidden state problem of Petri nets (PN) with uncontrollable transitions and liveness requirement is addressed by Ghaffari et al. [5]. An approach is presented to compute a maximally permissive Petri net controller that consists of two steps. In the first step, an ordinary Petri net is used to build the system model. In the second step, control places are designed and added to the original model by using a theory of regions method. The work of Uzam [7, 9] proposes and improves method based on a theory of regions to design an optimal Petri net supervisor. The size of the reachability graph of Petri net model is a major problem to apply the deadlock prevention policy to very large Petri net model. Therefore, they proposed a reduction algorithm to simplify very large Petri nets models in order to make necessary computation easily. Based on the theory of regions, Uzam and Zhou [6] developed an iterative deadlock prevention policy for FMS. In their study, the reachability graph of a Petri net model is divided into two parts: deadlock-free zone (live zone, LZ) and the deadlock zone (DZ). The live zone is developed since the maximal strongly connected component contains the initial marking. The deadlock zone contains markings from which the initial marking is unreachable. FBM is defined as a marking in the deadlock zone. The deadlocks can be eliminated by forbidding the firing of the enabled transitions at FBM. In their work, the presented approach has two problems. First, an optimal supervisor cannot be guaranteed in general even if such an optimal supervisor exists. Second, at each iteration full reachability graph computation is required to check whether the markings in the deadlock zone are reachable. This approach is easy to use and simple if the reachable graph of a system is small but cannot ensure the supervisor behavioral optimality. The redundant monitors in Petri net supervisor may exist when the supervisor is designed by an iterative siphon control approach. Therefore, Uzam et al. [21] introduced an approach to identify and eliminate the redundant monitors by computing the reachability graph of a controlled Petri net model. If the controlled Petri net model does not lose liveness when removing redundant monitors, then the redundant monitors can be eliminated from the supervisor. The reachability graph and liveness check are the major problems in designing liveness-enforcing supervisor. To overcome a full state enumeration, Li and Hu [22] proposed two approaches to eliminating control places from a Petri net supervisor. The first approach is based on the concept of implicit places [23, 24]. The implicity of a monitor is computed by solving a linear programming problem (LPP) that can be implemented in polynomial time. The second approach is extracted from the Mixed Integer Programming- (MIP-) based deadlock detection approach. If the optimal solution to an MIP problem does not lose optimality when removing control place, then the control place is implicit and may provide permissive behavior while liveness is guaranteed. Chen et al. [1] developed a novel and computationally effective approach to design optimal monitors and an iterative approach that can compute the reachability graph to get an optimal supervisor of the flexible manufacturing system, which is demonstrated by a set of control places. The vector covering approach is used to compute the minimal sets of FBMs and legal markings. Iteratively, an FBM is selected from the minimal set of FBMs, an integer linear programming problem (ILPP) is used to design a place invariant (PI) that prevents the FBM from being reached, and all minimal sets of legal markings are not forbidden. The process is terminated if all FBMs cannot be reached and the resulting net is a live. This study is improved in its computational efficiency in [25], and the objective function of the ILPP is maximizing the number of FBMs that are prohibited by the PI; in other words, a control place is designed such that as many FBMs as possible are forbidden and all minimal sets of legal markings are not prohibited. If the ILPP has no solution, it means that there is no maximally permissive Petri net supervisor for the Petri net model.


## 2.1. Structural-Analysis Methods

Ezpeleta et al. [13] used a class of Petri nets, called System of Simple Sequential Processes with Resources (S3PR) and proposed an algorithm for resource allocation in flexible manufacturing systems (FMSs). The proposed algorithm added new places to the net to impose certain restrictions that forbid the presence of unmarked siphons. The works of Huang et al. [14] and Huang et al. [15] present a new deadlock prevention policy for the class of Petri nets, where deadlocks are related to unmarked siphons. Two types of control places are added to the original model for flexible manufacturing system called ordinary control place and weighted control place to prevent siphons from being unmarked.The study by Li and Zhou [11] presents a Petri net model which consists of 26 places, 20 transitions, and 18 strict minimal siphons. In [16], elementary siphons concept is introduced to design a liveness-enforcing Petri net supervisor for the same Petri net model, and six elementary siphons are obtained; therefore, only six monitors are added to control the 18 strict minimal siphons. Nevertheless, the proposed algorithm by Ezpeleta et al. [13] adds monitors for all 18 strict minimal siphons.A new methodology is proposed by Huang [17] to synthesize supervisors for resource allocation in FMSs; the class of Petri net, namely, S3PR, is considered, where deadlocks are related to unmarked minimal siphons; all minimal siphons should be controlled by adding control places. In this study, the number of control places is reduced by using the concept of the elementary siphon. Based on elementary siphons and P-invariants concepts in Petri nets, a deadlock prevention algorithm is introduced by Li and Wei for a specific class of Petri nets which can properly model several FMSs [16], siphons in a Petri net model are classified into dependent and elementary siphons, and control places are added for all elementary siphons, so that the siphons are invariant-controlled. Therefore, the controllability of dependent siphons is guaranteed by adjusting the control requirements of its related elementary siphons. A novel deadlock prevention algorithm is presented by Chen et al. [1], and the concept of siphon extraction is used to compute unmarked siphons for the Petri net model. First, a siphon extraction algorithm obtains a maximal unmarked siphon, divides the places in it, and determines a necessary siphon from the divided places; this process is carried out for all unmarked siphons. Then, the proposed deadlock prevention algorithm designs a convenient monitor for each necessary siphon to be marked until the controlled Petri net model is a live.Most of the deadlock control algorithms have been developed for reliable automated manufacturing systems (AMSs). Liu et al. [18] proposed a variety of deadlock control algorithms for AMSs with unreliable resources, monitors and recovery subnets are designed for strict minimal siphons (emptied siphon) and unreliable resources, respectively, and two types of arcs which are normal and inhibitor are used to connect monitors with recovery subnets. In order to obtain a supervisor with structural complexity, elementary siphons extracted from all strict minimal siphons are obviously controlled. The problems of structural complexity, behavioral permissiveness, and computational complexity are considered in the study of Wang et al. [19] to design liveness-enforcing supervisors for a class of Petri nets, namely, S3PR, without ξ-resources. They used two steps to obtain a supervisor for the model. In the first step, an algorithm is proposed to extract unmarked strict minimal siphons from a given unmarked siphon by using loop resource subsets. In the second step, a siphon-based deadlock prevention algorithm is introduced to provide a maximally permissive liveness-enforcing supervisor with small numbers and no weighted monitors.


## 2.2. Reachability Graph-Based Approaches

Viswanadham et al. [20] presented static resource allocation methods for eliminating deadlocks; in this study, a reachability graph of the Petri net (PN) model is used to reach static resource allocation method. A deadlock prevention algorithm is implemented for a small size manufacturing system consisting of a machine and an automated guided vehicle (AGV). The authors observed that the proposed algorithm can be applied effectively only for small size manufacturing systems. The forbidden state problem of Petri nets (PN) with uncontrollable transitions and liveness requirement is addressed by Ghaffari et al. [5]. An approach is presented to compute a maximally permissive Petri net controller that consists of two steps. In the first step, an ordinary Petri net is used to build the system model. In the second step, control places are designed and added to the original model by using a theory of regions method. The work of Uzam [7, 9] proposes and improves method based on a theory of regions to design an optimal Petri net supervisor. The size of the reachability graph of Petri net model is a major problem to apply the deadlock prevention policy to very large Petri net model. Therefore, they proposed a reduction algorithm to simplify very large Petri nets models in order to make necessary computation easily. Based on the theory of regions, Uzam and Zhou [6] developed an iterative deadlock prevention policy for FMS. In their study, the reachability graph of a Petri net model is divided into two parts: deadlock-free zone (live zone, LZ) and the deadlock zone (DZ). The live zone is developed since the maximal strongly connected component contains the initial marking. The deadlock zone contains markings from which the initial marking is unreachable. FBM is defined as a marking in the deadlock zone. The deadlocks can be eliminated by forbidding the firing of the enabled transitions at FBM. In their work, the presented approach has two problems. First, an optimal supervisor cannot be guaranteed in general even if such an optimal supervisor exists. Second, at each iteration full reachability graph computation is required to check whether the markings in the deadlock zone are reachable. This approach is easy to use and simple if the reachable graph of a system is small but cannot ensure the supervisor behavioral optimality. The redundant monitors in Petri net supervisor may exist when the supervisor is designed by an iterative siphon control approach. Therefore, Uzam et al. [21] introduced an approach to identify and eliminate the redundant monitors by computing the reachability graph of a controlled Petri net model. If the controlled Petri net model does not lose liveness when removing redundant monitors, then the redundant monitors can be eliminated from the supervisor. The reachability graph and liveness check are the major problems in designing liveness-enforcing supervisor. To overcome a full state enumeration, Li and Hu [22] proposed two approaches to eliminating control places from a Petri net supervisor. The first approach is based on the concept of implicit places [23, 24]. The implicity of a monitor is computed by solving a linear programming problem (LPP) that can be implemented in polynomial time. The second approach is extracted from the Mixed Integer Programming- (MIP-) based deadlock detection approach. If the optimal solution to an MIP problem does not lose optimality when removing control place, then the control place is implicit and may provide permissive behavior while liveness is guaranteed. Chen et al. [1] developed a novel and computationally effective approach to design optimal monitors and an iterative approach that can compute the reachability graph to get an optimal supervisor of the flexible manufacturing system, which is demonstrated by a set of control places. The vector covering approach is used to compute the minimal sets of FBMs and legal markings. Iteratively, an FBM is selected from the minimal set of FBMs, an integer linear programming problem (ILPP) is used to design a place invariant (PI) that prevents the FBM from being reached, and all minimal sets of legal markings are not forbidden. The process is terminated if all FBMs cannot be reached and the resulting net is a live. This study is improved in its computational efficiency in [25], and the objective function of the ILPP is maximizing the number of FBMs that are prohibited by the PI; in other words, a control place is designed such that as many FBMs as possible are forbidden and all minimal sets of legal markings are not prohibited. If the ILPP has no solution, it means that there is no maximally permissive Petri net supervisor for the Petri net model.


## 3. Basics of Petri Nets

Petri nets are a mathematical and graphical tool suitable for several systems. It is a major tool for studying and describing manufacturing system operations that are characterized as being asynchronous, concurrent, parallel, and distributed.A Petri net or place/transition net can be defined as a four-tupleN
=
(
P
,
T
,
F
,
W
), where P is a finite nonempty set of places, T is a finite nonempty set of transitions, P and T are disjoint, P
∪
T are called nodes with P
∪
T
≠
∅ and P
∩
T
=
∅, and P and T are represented by circle and bar, respectively. F
⊆
(
P
×
T
)
∪
(
T
×
P
) is called a flow relation or directed arcs of the net that can be represented by arcs with arrows from places (transitions) to transitions (places). W
:
(
P
×
T
)
∪
(
T
×
P
)
→
N is a mapping that assigns a weight to an arc: if (
a
,
b
)
∈
F
,
W
(
a
,
b
)
>
0; otherwise, W
(
a
,
b
)
=
0, where a
,
b
∈
P
∪
T and N
=
{
0,1
,
2
,
…
}. N is called an ordinary net, if W
(
a
,
b
)
=
1, ∀
(
a
,
b
)
∈
F. Consider a node a
∈
P
∪
T, and a
∙
=
{
b
∈
P
∪
T
∣
(
b
,
a
)
∈
F
} is a preset of a. Postset of a is a
∙
=
{
b
∈
P
∪
T
∣
(
a
,
b
)
∈
F
}. A marking M of N is a mapping from P
→
N. M
(
p
) denotes the number of tokens in place p. Usually, markings and vectors can be described using formal sum. Therefore, vector M is denoted by ∑
p
∈
P
M
(
p
)
p. For example, a marking that puts two tokens in place p
2, five tokens in place p
4, and no tokens in other places in a net is denoted by 2
p
2
+
5
p
4. (N
,
M
0) is a net system or marked net and is denoted by N
=
(
P
,
T
,
F
,
W
,
M
0
), where M
0 is an initial marking of N. For a Petri net modeling M
0 represents the different raw parts that are to be synchronously processed in the system, and the state of resources, such as machines and robots. A net is self-loop free or pure if for all a
,
b
∈
P
∪
T, W
(
a
,
b
)
>
0 and W
(
b
,
a
)
=
0. Incidence matrix [N] in a net N is an integer matrix that consists of P rows and T columns with [
N
]
(
p
,
t
)
=
W
(
t
,
p
)
-
W
(
p
,
t
). The enabled rule for each t
∈
T at marking M if ∀
p
∈
t
∙, M
(
p
)
≥
W
(
p
,
t
). As a result, enabled rule is denoted by M
[
t. When a transition t fires, it removes W
(
p
,
t
) tokens from each place p
∈
t
∙ and deposits W
(
t
,
p
) tokens in each place p
∈
t
∙. Therefore, it yields a new marking M
′, denoted by M
[
t
M
′, where M
′
(
p
)
=
M
(
p
)
-
W
(
p
,
t
)
+
W
(
t
,
p
). M
′ is reachable from M if there exists a fireable finite transition sequence δ
=
{
t
1
,
t
2
,
t
3
,
…
,
t
n
}, and markings M
1
,
M
2
,
M
3
,
…, and M
n
-
1 so that M
[
t
1
M
1
t
2
M
2
t
3
M
2
,
…
,
M
n
-
1
[
t
n
〉
M
′, which can be denoted by M
[
δ
M
′ and satisfied the state equation M
′
=
M
+
[
N
]
δ
→, where δ
→
:
T
→
N is a mapping t in T to the number of occurrences of t in δ, called a Parikh vector or a firing count vector. Obviously, M
0
[ is the set of all reachable markings of a net N from initial marking M
0 and is denoted by R
(
N
,
M
0
). The reachable markings R
(
N
,
M
0
) can be involved in the enumeration of all reachable markings of a net N and graphically expressed by a reachability tree. The reachability tree is denoted by G
(
N
,
M
0
), which is a directed graph and consists of nodes and arcs, nodes are markings in the reachable markings R
(
N
,
M
0
), and arcs are labeled by the transitions of a net N. For instance, an arc from M
2 to M
3 is labeled by t
1 if M
2
[
t
1
M
3. A net N with initial marking M
0 is to be k-bounded if, for all M
∈
R
(
N
,
M
0
), M
(
p
)
≤
k
(
k
=
{
1,2
,
3
,
…
}
). In other words, for each reachable marking “M” from the initial marking M
0, the number of tokens in each place “p” never exceeds a finite number “k
.” A net is called safe if all its places are safe, and the number of tokens in each place “p” does not exceed one. In other words, a net is k-safe if it is 1-bounded. A Petri net with (
N
,
M
0
) is a live if all its transitions are a live at M
0. A transition t
∈
T is a live if, for all M
∈
R
(
N
,
M
0
), ∃
M
∈
R
(
N
,
M
), there is a firing sequence M
′
[
t. A transition is dead at M
0 if ∄
t
∈
T, M
0
[
t. P-vector (place vector) and T-vector (transition vector) are column vectors. The former I
:
P
→
Z is catalogued by P and called a P-invariant or place invariant if I
≠
0 and I
T
·
[
N
]
=
0
T. The latter J
:
T
→
Z is catalogued by T and called a T-invariant or transition invariant if J
≠
0 and N
·
J
=
0, where Z is the integers set. If each element of I is nonnegative the P-invariant I is called a P-semiflow or place semiflow. Suppose that I is a place invariant of a Petri net with (N
,
M
0) and M is a reachable marking from the initial marking M
0. Then, I
T
M
=
I
T
M
0. Let I
=
{
p
∣
I
(
p
)
≠
0
} be a support of place invariant I and it can be classified into three parts. Firstly, I
+ is a positive support of place invariant I, and I
+
=
{
p
∣
I
(
p
)
>
0
}. Secondly, I
- is a negative support of place invariant I, and I
-
=
{
p
∣
I
(
p
)
<
0
}. Finally, I is a minimal place invariant if I is not a superset of the support of any other one and its components are mutually prime. Let l
i’s be the coefficients of place invariant I if, for all p
i
∈
P, l
i
=
I
(
p
i
).


## 4. Deadlock Prevention Methods and Policies

### 4.1. Siphon Control Methods

This section presents two methods that are motivated by Ezpeleta et al. [13] and Li and Zhou [11]. These methods are called a strict minimal siphons control method and an elementary siphons control method, respectively.


#### 4.1.1. Strict Minimal Siphons (SMSs) Control Method

A siphon in a Petri net is a set of placesS
=
{
p
1
,
…
,
p
k
}. The very important property of siphon is that, for a given marking, the siphon is unmarked.Definition 1.
LetN be a net. Any set S
⊆
P, S
≠
∅ with S
∙
⊆
S
∙ is called a siphon. If a siphon does not properly contain another siphon is called a minimal siphon. A minimal siphon S is called a strict if S
∙
⊊
S
∙.
Siphons play a significant role in the liveness analysis of a Petri net, especially in ordinary ones. If a siphonS in a net has no tokens, then no transitions in S
∙ are enabled and all the transitions connected to S cannot be fired; as a result, the transitions are dead leading to the loss of liveness of the Petri net. In [13], a monitor is added to each strict minimal siphon in order to achieve the liveness of the system. The proposed approach is simple and ensures a success. Nevertheless, it leads to a complex Petri net model than the originally model because the added places are equal to the strict minimal siphons in the target net model and the added arcs are larger than that of places added.
The SMS control based on complementary sets of siphonsS is used to design the control places. A complementary set of a siphon S is a set of operation places which are the holders of the resources in S but do not belong to S. In addition, S
∪
S is the support of a place invariant, which means the operation places in S will compete for the resources in S with the operation places belonging to S. S will be unmarked when all tokens in S flow into S. The following notation will be used in the establishment of the control policy.(1)
S denotes the set of strict minimal siphons which does not contain the support of any place semiflow (i.e., siphons that can be emptied).
(2)
Given the fact thatS is a siphon we have S
=
S
A
∪
S
R, S
R
=
S
∩
P
R, S
A
=
S
∖
S
R, where S
A is the operation places and S
R is the resource places. S denotes the following set of state places: S
=
(
U
r
∈
S
R
H
(
r
)
)
∖
S
A, where H
r
=
I
r
+
∖
r, I
r
+
=
{
p
∣
I
(
p
)
>
0
} indicates the positive support of place invariant I, ∀
i
,
j
∈
1,2
,
…
,
n
i
≠
j,  H
r
i
∩
H
r
j
=
∅. For a given siphon S, S is the set of holders, corresponding to resources in S that do not belong to S. S is called S’s complementary set.
(3)
Given the fact thatS is a complementary set of S, add a control place for S and the initial marking of control place is M
0
A
(
V
S
)
=
M
0
(
S
)
-
1.
Based on the concept of strict minimal siphon, the proposed deadlock prevention algorithm developed by Ezpeleta et al. [13] is stated as follows.Algorithm 2 (SMS based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), compute all SMSs.
Step
2. For each siphon SMS, add a monitor V
S such that(i)
theV
S output arcs are connected to the source transitions leading to the sink transitions of S and all arcs weights are ones;
(ii)
theV
S input arcs are connected from the stealing places of S and all arcs weights are ones;
(iii)
M
0
A
(
V
S
)
=
M
0
(
S
)
-
1, where M
0
A
(
V
S
) is an initial marking of a monitor.
Step
3. Repeat Step 2 until all existing SMSs are covered.
Step
4. Add all monitors into (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
5. Output (N
1
,
M
1).
Step
6. End.For instance, consider the AMS shown in Figure1(a). Its Petri net model is shown in Figure 1(b). It consists of one robot R1 that can hold a part at a time, two machines M1 and M2, where each machine can process a part at a time, two loading buffers (I1 and I2), and unloading buffers (O1 and O2). Two parts types are considered in the system: PA and PB. PA moves to M1 and PB moves to M2. The robot R1 reaches the machine that finishes its operation first and grips and loads the part to the next machine 1 or machine 2. The Petri net model consists of 11 places and 8 transitions. The places have the following set partition: P
0
=
{
P
1
,
P
8
}, P
R
=
{
P
9
,
P
10
,
P
11
}, and P
A
=
{
P
2
,
…
,
P
7
}, where P
0 is the input places, P
R is the resources places, and P
A is the operation places. It has 8 minimal siphons, 3 of which are strict minimal siphons and 20 reachable markings. The three SMSs are S
1
=
{
P
4
,
P
7
,
P
9
,
P
10
,
P
11
}, S
2
=
{
P
4
,
P
6
,
P
10
,
P
11
}, and S
3
=
{
P
3
,
P
7
,
P
9
,
P
10
}. Table 1 shows the required monitors using Algorithm 2 for Figure 1(b). Figure 2 illustrates the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 2.Table 1
Control places computations by Algorithm2.
SMS
I
+
H
(
r
R
)
S
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
S
1
=
{
P
4
,
P
7
,
P
9
,
P
10
,
P
11
}
,
S
A
=
{
P
4
,
P
7
}
,
S
R
=
{
P
9
,
P
10
,
P
11
}.
I
p
9
+
=
{
p
2
,
p
7
,
p
9
}
,
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}
,
I
p
11
+
=
{
p
4
,
p
5
,
p
11
}.
H
r
9
=
p
2
,
p
7,
H
r
10
=
p
3
,
p
6,
H
r
11
=
p
4
,
p
5.
S
1
=
{
p
2
,
p
3
,
p
5
,
p
6
}.
t
3
,
t
7
t
1
,
t
5
2
S
2
=
{
P
4
,
P
6
,
P
10
,
P
11
}
,
S
A
=
{
P
4
,
P
6
}
,
S
R
=
{
P
10
,
P
11
}.
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}
,
I
p
11
+
=
{
p
4
,
p
5
,
p
11
}.
H
r
10
=
p
3
,
p
6,
H
r
11
=
p
4
,
p
5.
S
2
=
{
p
3
,
p
5
}.
t
3
,
t
6
t
2
,
t
5
1
S
3
=
{
P
3
,
P
7
,
P
9
,
P
10
}
,
S
A
=
{
P
3
,
P
7
}
,
S
R
=
{
P
9
,
P
10
}.
I
p
9
+
=
{
p
2
,
p
7
,
p
9
}
,
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}.
H
r
9
=
p
2
,
p
7,
H
r
10
=
p
3
,
p
6.
S
3
=
{
p
2
,
p
6
}.
t
2
,
t
7
t
1
,
t
5
1Figure 1
(a) An AMS example and (b) Petri net model of an AMS.
(a)
(b)Figure 2
Controlled system of the Petri net in Figure1(b) by Algorithm 2.


#### 4.1.2. Elementary Siphons Control Method

The strict minimal siphons (SMSs) are classified into elementary and dependent ones. Π is used to denote the set of strict minimal siphons whileΠ
E and Π
D denote the sets of elementary and dependent (redundant) ones, respectively. Otherwise, when a strict minimal one is mentioned, it can be called a siphon.Definition 3.
Let an ordinary Petri net (N
,
M
0) and S is a siphon, S
⊆
P. Place vector λ
S is said to be the characteristic place vector of S if for all p
∈
S, λ
S
(
p
)
=
1; otherwise, λ
S
(
p
)
=
0.Definition 4.
LetN
=
(
P
,
T
,
F
) be an ordinary Petri net with P
=
m, T
=
n, and we suppose that N has f SMS, S
1
,
S
2
,
…, and S
f
,
m
,
n
,
f
∈
I
N
. Let λ
S
i
(
η
S
i
) be the characteristic place (transition) vector of siphon S
i, i
∈
{
1,2
,
…
,
n
}. We define λ
f
×
m
=
λ
S
1
,
λ
S
2
,
…
,
λ
S
f
T and η
f
×
n
=
λ
f
×
m
·
N
m
×
n are said to be the characteristic place vector and transition vector matrices of the siphons of N, respectively.Proposition 5.
LetN be an ordinary Petri net and let η be the characteristic transition vector matrix of the siphons of it. The set of elementary siphons in N can be defined as a rank of η.From Proposition5, it can easily enumerate all elementary siphons in a Petri net system (N
,
M
0) given all siphons. First, compute matrices λ and η. Then independent linear vectors can be determined in η. Finally, the siphons that correspond to these independent linear vectors are called the elementary siphons in the Petri net (N
,
M
0). Li and Zhou [11] introduced some results and theorems as follows.Theorem 6.
LetN
0 be a marked ordinary Petri net and S
=
{
p
i
1
,
p
i
2
,
…
,
p
i
n
} be a siphon in N
0. Monitor V
S is added to N
0, and the new net system can be denoted by (
N
1
,
M
1
), such that (a) I
1
=
…
,
1
p
i
1
,
1
p
i
2
,
…
,
1
p
i
n
,
…
,
-
1
V
S
,
…
T is a place invariant of N
1 and (b) M
1
(
V
S
)
=
M
0
(
S
)
-
ξ
S, where ξ
S is said to be the control depth variable of siphon S, which states the least number of tokens that siphon can hold. Evidently is greater than or equal to 1 to fulfil purpose of control 1
≤
ξ
S
≤
M
0
(
S
)
-
1, and (c) for all p
∈
P
0, M
1
(
p
)
=
M
0
(
p
), where P
0 is the set of operation places of N
0, such that S can be called invariant-controlled.Theorem 7.
Let(
N
,
M
0
) be an ordinary Petri net and let S
0 be a generally dependent siphon on elementary siphons S
1
,
S
2
,
…
,
S
n
,
S
n
+
1
,
S
n
+
2
,
…, and S
n
+
m that means η
S
0
=
∑
i
=
1
n
a
i
·
η
S
i
-
∑
j
=
n
+
1
n
+
m
a
j
·
η
S
j. If S
1
,
S
2
,
…
,
S
n
,
S
n
+
1
,
S
n
+
2,…, and S
n
+
m are invariant-controlled by adding monitors V
S
1
,
V
S
2
,
…
,
V
S
n
+
m
,
…, and M
0
(
S
0
)
>
∑
i
=
1
n
a
i
·
M
0
S
i
-
∑
i
=
1
n
a
i
·
ξ
S
i, where 1
≤
ξ
S
i
≤
M
0
(
S
i
)
-
1, S
0 is called controlled. Based on the concept of elementary siphons, the proposed deadlock prevention algorithm developed by Li and Zhou [11] is stated as follows.Algorithm 8 (elementary siphon-based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), compute all SMSs.
Step
2. Compute the transition vector matrix η of the SMS.
Step
3. Compute the elementary siphons of Petri net N. The remaining are the dependent siphons.
Step
4. For each siphon elementary siphon, add a monitor V
S such that(i)
theV
S output arcs are connected to the source transitions leading to the sink transitions of S and all arcs weights are ones;
(ii)
theV
S input arcs are connected from the stealing places of S and all arcs weights are ones;
(iii)
M
0
A
(
V
S
)
=
M
0
(
S
)
-
ξ
S, where M
0
A
(
V
S
) is an initial marking of a monitor and 1
≤
ξ
S
≤
M
0
(
S
)
-
1.
Step
5. Repeat Step 4 until all elementary siphons are covered.
Step
6. Adjust ξ
i, such that each dependent siphon is controlled.
Step
7. Add all monitors to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
8. Output (N
1
,
M
1).
Step
9. End.For example, there are three SMSs in the Petri net model shown in Figure1(b), which are S
1
=
{
p
4
,
p
7
,
p
9
,
p
10
,
p
11
}, S
2
=
{
p
4
,
p
6
,
p
10
,
p
11
}, and S
3
=
{
p
3
,
p
7
,
p
9
,
p
10
}. One can obtain that λ
S
1
=
(
0,0
,
0,1
,
0,0
,
1,0
,
1,1
,
1
)
T, λ
S
2
=
(
0,0
,
0,1
,
0,1
,
0,0
,
0,1
,
1
)
T, and λ
S
3
=
(
0,0
,
1,0
,
0,0
,
1,0
,
1,1
,
0
)
T. Hence, η
S
1
=
(
-
1,0
,
1,0
,
-
1,0
,
1,0
)
T, η
S
2
=
(
0
,
-
1,1
,
0
,
-
1,1
,
0,0
)
T, and η
S
3
=
(
-
1,1
,
0,0
,
0
,
-
1,1
,
0
)
T. The transition vector matrix η for the Petri net model in Figure 1(b) is as follows. Obviously, the rank of η is 2 since the first row η
S
1 can be linearly represented by the second and third rows, and we can see that η
S
1
=
η
S
2
+
η
S
3. As a result, the siphons that correspond to the second and third rows S
2 and S
3 are elementary siphons. Thus, S
1 is a dependent siphon:(1)
η
=
-
1
0
1
0
-
1
0
1
0
0
-
1
1
0
-
1
1
0
0
-
1
1
0
0
0
-
1
1
0
.The dependent siphons and their elementary siphons, the initial marking relationships between dependent and elementary siphons, and the controllability of dependent siphons due to Theorem 7 are shown in Table 2. Table 3 shows the required monitors using Algorithm 8 for Figure 1(b). Figure 3 presents the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 8.Table 2
Marking relationships between dependent and elementary siphons.
Dependent
η relationship
Initial marking relationships,
M
0
(
S
0
)
>
∑
i
=
1
n
a
i
⋅
M
0
S
i
-
∑
i
=
1
n
a
i
⋅
ξ
S
i
Controlled
S
1
η
1
=
η
2
+
η
3
M
0
(
S
1
)
>
(
M
0
(
S
2
)
+
M
0
(
S
3
)
)
-
(
ξ
S
2
+
ξ
S
3
) 3 > (2 + 2) − (1 + 1),  3 > 2
YesTable 3
Required monitors using Algorithm8.
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
S
2
t
3
,
t
6
t
2
,
t
5
1
S
3
t
2
,
t
7
t
1
,
t
5
1Figure 3
Controlled system of the Petri net in Figure1(b) by Algorithm 8.


### 4.2. Iterative Methods

This section presents two techniques that are motivated and developed by [25]. These techniques are used to design a place invariant (PI) that can prohibit as many forbidden bad markings (FBMs) as possible. First, the vector covering method is used to find the minimal covering sets of legal markings and FBMs (see Chen et al. [1]). Then, solving the integer linear programming problem (ILPP) can obtain the coefficients of the place invariant and monitors. An iterative monitor design process is executed. At each iteration, a place invariant is designed to prohibit as many FBMs as possible. All FBMs that are prohibited by the place invariant are eliminated from the minimal covered set of FBMs. This process is terminated when all the minimal covered sets of FBMs are forbidden.


#### 4.2.1. Maximal Number of Forbidding FBM Problem 1

The Maximal number of Forbidding FBM Problem 1 (MFFP1) is a technique used to design a monitor synthesis for FBMs. This technique used ILPP to obtain the coefficients of the place invariant that prohibit as many FBMs as possible. The MFFP1 is shown in the following mathematical model.MFFP1 is(2)
max
⁡
f
=
∑
k
∈
N
F
B
M
∗
f
k
subject to
∑
i
∈
N
A
l
i
·
M
l
p
i
≤
β
,
∀
M
l
∈
M
L
∗
(3)
∑
i
∈
N
A
l
i
·
M
k
p
i
≥
β
+
1
-
Q
·
1
-
f
k
,
∀
M
k
∈
M
F
B
M
∗
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
I
N
β
∈
1,2
,
…
f
k
∈
0,1
,
∀
k
∈
N
F
B
M
∗
,where M
L
∗ and M
F
B
M
∗ are the minimal covering sets of legal markings and FBMs, respectively. The objective function f is used to maximize the number of FBMs that are forbidden by place invariant. If f
=
0, we have f
k
=
0, for all k
∈
N
F
B
M
∗ (N
F
B
M
∗ is used to denote {
i
∣
M
i
∈
M
F
B
M
∗
}): that is to say, no FBMs in M
F
B
M
∗ can be prohibited by place invariant. In (2), let I be a place invariant, where l
i’s (i
∈
I
N) are the coefficients of I, β is a positive integer variable, and M
l
p
i
(
∀
M
l
∈
M
L
∗
) are the number of tokens in minimal covering set of legal markings.All legal markings should be kept after a monitor is added, implying that every markingM
l
∈
M
L
∗ cannot be forbidden from being reached, and coefficients l
i’s (i
∈
I
N) should satisfy (2) that is called the reachability condition.In (3), Q is a positive integer constant number that must be large enough, M
k
p
i
(
∀
M
k
∈
M
F
B
M
∗
) are the number of tokens in minimal covering set of FBMs, and f
k’s (f
k
∈
{
0,1
}
,
k
=
1,2
,
…) are a set of M
F
B
M
∗ variables. Moreover, in (3), f
k
=
1 implies that M
k is prohibited by I and f
k
=
0 implies that this constraint is redundant and M
k cannot be prohibited by I.Based on the concept of MFFP1, the proposed deadlock prevention algorithm developed in [25] is stated as follows.Algorithm 9 (MFFP1 based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), find the sets of FBMs M
F
B
M and legal markings M
L.
Step
2. Find the minimal covered sets of FBMs M
F
B
M
∗ and legal markings M
L
∗.
Step
3. V
M
≔
∅. /
V
M
∗ is used to indicate the set of monitors to be found. /
∗
Step
4. While {
M
F
B
M
∗
≠
∅
}, do the following.(i)
Design MFFP1.
(ii)
Solve MFFP1. Letl
i’s (i
∈
I
N) and β be the solution if f
∗
≠
0.
Otherwise, exit, as the solution does not exist.
(iii)
Design a place invariantI and a monitor V
S.
(iv)
V
M
≔
V
M
∪
{
V
S
} and M
F
B
M
∗
=
M
F
B
M
∗
-
F
I. /
∗
F
I is covered M
F
B
M
∗
endwhile.
Step
5. Add all monitors in V
M to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
6. Output (N
1
,
M
1).
Step
7. End.For the Petri net model shown in Figure1(b), we have M
F
B
M
∗
=
{
p
2
+
p
5
,
p
3
+
p
5
,
p
2
+
p
6
} and M
L
∗
=
{
p
2
+
p
3
+
p
4
,
p
5
+
p
6
+
p
7
}. Algorithm 9 is considered. At the first iteration, let I
1 be the place invariant to be calculated. I
1 should satisfy (2) for the two legal markings in M
L
∗: that is, l
2
·
1
+
l
3
·
1
+
l
4
·
1
≤
β and l
5
·
1
+
l
6
·
1
+
l
7
·
1
≤
β. Therefore, we have the following two constraints:(4)
l
2
+
l
3
+
l
4
≤
β
,
l
5
+
l
6
+
l
7
≤
β
.We introduce three variables f
1, f
2, and f
3 (f
1
,
f
2
,
f
3
∈
{
0,1
}) to represent whether I
1 forbids F
B
M
1
=
p
2
+
p
5, F
B
M
2
=
p
3
+
p
5, and F
B
M
3
=
p
2
+
p
6, respectively. Therefore, we have the following three constraints: that is,(5)
l
2
+
l
5
≥
β
+
1
-
Q
·
1
-
f
1
,
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
,
l
2
+
l
6
≥
β
+
1
-
Q
·
1
-
f
3
.Finally, MFFP1 is defined as follows.MFFP1 is(6)
max
⁡
f
=
f
1
+
f
2
+
f
3
subject to
l
2
+
l
3
+
l
4
≤
β
l
5
+
l
6
+
l
7
≤
β
l
2
+
l
5
≥
β
+
1
-
Q
·
1
-
f
1
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
l
2
+
l
6
≥
β
+
1
-
Q
·
1
-
f
3
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
β
∈
1,2
,
…
f
k
∈
0,1
,
∀
k
∈
1,2
,
3
.The optimal solution of the above MFFP1 is l
2
=
2, l
5
=
1, l
6
=
1, β
=
2, f
1
=
1, and f
3
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
1 is designed for I
1
:
2
μ
2
+
μ
5
+
μ
6
+
μ
V
S
1
=
2. As a result, we have M
0
A
(
V
S
1
)
=
β
=
2, V
S
1
∙
=
{
2
t
2
,
t
7
}, and V
S
1
∙
=
{
2
t
1
,
t
5
}. FBM1 and FBM3 are prohibited by I
1: that is, F
I
1
=
{
F
B
M
1
,
F
B
M
3
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
F
B
M
3
=
{
p
3
+
p
5
}.At the next iteration, letI
2 place invariant be calculated. The new MFFP1 can be easily obtained by eliminating constraints that related to FBM1 and FBM3 from the first MFFP1. Therefore, the new MFFP1 is stated as follows.MFFP1 is(7)
max
⁡
f
=
f
2
subject to
l
2
+
l
3
+
l
4
≤
β
l
5
+
l
6
+
l
7
≤
β
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
β
∈
1,2
,
…
f
2
∈
0,1
.The optimal solution of the above MFFP1 is l
3
=
1, l
5
=
1, β
=
1, and f
2
=
1 and all the remaining variables are equal to zero. Then, a monitor V
S
2 is designed for I
2
:
μ
3
+
μ
5
+
μ
V
S
2
=
1. As a result, we have M
0
A
(
V
S
2
)
=
β
=
1, V
S
1
∙
=
{
t
3
,
t
6
}, and V
S
1
∙
=
{
t
2
,
t
5
}. Only FBM2 is prohibited by I
2: that is, F
I
2
=
{
F
B
M
2
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
2: that is, M
F
B
M
∗
=
∅.Algorithm9 is terminated. Totally, there are two monitors computed for this net. Adding the two monitors to the original Petri net model, the controlled system after addition is as shown in Figure 4. Table 4 shows the two required monitors by using Algorithm 9.Table 4
Required monitors using Algorithm9.
i
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
1
2
t
2
,
t
7
2
t
1
,
t
5
2
2
t
3
,
t
6
t
2
,
t
5
1Figure 4
Controlled system of the Petri net in Figure1(b) by Algorithm 9.


#### 4.2.2. Maximal Number of Forbidding FBM Problem 2

The Maximal number of Forbidding FBM Problem 1 has been modified to improve its efficiency and its number of variables and constraints are slightly reduced. The modified technique is called a Maximal number of Forbidding FBM Problem 2 (MFFP2). The MFFP1 is shown in the following mathematical model.MFFP2 is(8)
max
⁡
f
=
∑
k
∈
N
F
B
M
∗
,
k
≠
j
f
k
subject to
∑
i
∈
N
A
l
i
·
M
l
p
i
-
M
j
p
i
≤
-
1
,
∀
M
l
∈
M
L
∗
∑
i
∈
N
A
l
i
·
M
k
p
i
-
M
j
p
i
≥
-
Q
·
1
-
f
k
,
∀
M
k
∈
M
F
B
M
∗
,
k
≠
j
(9)
l
i
∈
0,1
,
2
,
…
.
,
∀
i
∈
I
N
f
k
∈
0,1
,
∀
k
∈
N
F
B
M
∗
,
k
≠
j
.The objective function is maximizing f the number of FBMs that are prohibited by place invariant. If no solution has been obtained from MFFP2 for an FBM, then there are not any FBMs in M
F
B
M
∗ that can be forbidden by that place invariant.In (8), l
i’s (i
∈
I
N) are the coefficients of I, M
l
p
i
(
∀
M
l
∈
M
L
∗
) are the number of tokens in minimal covering set of legal markings, and M
j
p
i are the number of tokens in selected F
B
M
j. In (9), Q is a positive integer constant number that must be large enough, M
k
p
i
(
∀
M
k
∈
M
F
B
M
∗
) are the number of tokens in minimal covering set of FBMs, and f
k’s (f
k
∈
{
0,1
}
,
k
=
1,2
,
…) are a set of M
F
B
M
∗ variables. In (9), f
k
=
1 implies that M
k is prohibited by I and f
k
=
0 implies that this constraint is redundant and M
k cannot be prohibited by I.Based on the concept of MFFP2, the proposed deadlock prevention algorithm developed in [25] is stated as follows.Algorithm 10 (MFFP2 based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), find the sets of FBMs M
F
B
M and legal markings M
L.
Step
2. Find the minimal covered sets of FBMs M
F
B
M
∗ and legal markings M
L
∗.
Step
3. V
M
≔
∅. /
∗
V
M is used to indicate the set of monitors to be found. /
∗
Step
4. While {
M
F
B
M
∗
≠
∅
}, do the following.(i)
Design MFF2.
(ii)
Solve MFFP2. Letl
i’s (i
∈
N
A) and β be the solution if f
∗
≠
0. Otherwise, exit, as the solution does not exist.
(iii)
Design a place invariantI and a monitor V
S
V
M
≔
V
M
∪
{
V
S
} and M
F
B
M
∗
=
M
F
B
M
∗
-
F
I. /
∗
F
I is covered M
F
B
M
∗
endwhile.
Step
5. Add all monitors in V
M to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
6. Output (N
1
,
M
1).
Step
7. End.Consider the Petri net model shown in Figure1(b) by Algorithm 10. At the first iteration, F
B
M
1
=
p
2
+
p
5 is chosen. Let I
1 be the place invariant to prohibit FBM1, whose coefficients are l
i’s (i
∈
{
2,3
,
4,5
,
6,7
}). I
1 should satisfy (8) that is called the reachability condition and does not prohibit any marking in M
L
∗. Therefore, I
1 should satisfy two constraints:(10)
l
2
·
1
-
1
+
l
3
·
1
-
0
+
l
4
·
1
-
0
+
l
5
·
0
-
1
+
l
6
·
0
-
0
+
l
7
·
0
-
0
≤
-
1
,
l
2
·
0
-
1
+
l
3
·
0
-
0
+
l
4
·
0
-
0
+
l
5
·
1
-
1
+
l
6
·
1
-
0
+
l
7
·
1
-
0
≤
-
1for the two legal markings p
2
+
p
3
+
p
4 and p
5
+
p
6
+
p
7 in M
L
∗, respectively. After simplifying the two constraints, we have(11)
l
3
+
l
4
-
l
5
≤
-
1
,
-
l
2
+
l
6
+
l
7
≤
-
1
.Two variables are introduced f
2 and f
3 to represent whether I
1 forbids F
B
M
2
=
p
3
+
p
5 and F
B
M
3
=
p
2
+
p
6, respectively. Therefore, we have the two constraints: that is, l
2
·
(
0
-
1
)
+
l
3
·
(
1
-
0
)
+
l
4
·
(
0
-
0
)
+
l
5
·
(
1
-
1
)
+
l
6
·
(
0
-
0
)
+
l
7
·
(
0
-
0
)
≥
-
Q
·
(
1
-
f
2
) and l
2
·
(
1
-
1
)
+
l
3
·
(
0
-
0
)
+
l
4
·
(
0
-
0
)
+
l
5
·
(
0
-
1
)
+
l
6
·
(
1
-
0
)
+
l
7
·
(
0
-
0
)
≥
-
Q
·
(
1
-
f
3
), where Q is a positive integer constant that must be big enough and f
2
=
1 (f
3
=
1) implies that FBM2 (FBM3) is forbidden by I
1 and f
2
=
0 (f
3
=
0) implies that FBM2 (FBM3) cannot be forbidden by I
1. After simplifying the two constraints, we have(12)
-
l
2
+
l
3
≥
-
Q
·
1
-
f
2
,
-
l
5
+
l
6
≥
-
Q
·
1
-
f
3
.Finally, from the above constrains MFFP2 for FBM1 is stated as follows.MFFP2 is(13)
max
⁡
f
=
f
2
+
f
3
subject to
l
3
+
l
4
-
l
5
≤
-
1
-
l
2
+
l
6
+
l
7
≤
-
1
-
l
2
+
l
3
≥
-
Q
·
1
-
f
2
-
l
5
+
l
6
≥
-
Q
·
1
-
f
3
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
f
k
∈
0,1
,
∀
k
∈
2,3
.The optimal solution of the above MFFP2 is l
2
=
1, l
3
=
1, l
5
=
2, and f
2
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
1 is designed for I
1
:
μ
2
+
μ
3
+
2
μ
5
+
μ
V
S
1
=
2. As a result, we have M
0
A
V
S
1
=
2, V
S
1
∙
=
{
t
3
,
2
t
6
}, and V
S
1
∙
=
t
1
,
2
t
5. FBM1 and FBM2 are prohibited by I
1: that is, F
I
1
=
{
F
B
M
1
,
F
B
M
2
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
{
p
2
+
p
6
}. At the second iteration, the last FBM is considered, that is, FBM3. Let I
2 be the place invariant to prohibit FBM3. First, the coefficients of I
2 should fulfill the reachability conditions: that is,(14)
l
3
+
l
4
-
l
6
≤
-
1
,
-
l
2
+
l
5
+
l
7
≤
-
1
.Since FBM3 is the last marking in M
F
B
M
∗, no other FBMs in the set require to be prohibited by I
2. By solving the above integer linear system, we have a solution with l
2
=
1, l
6
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
2 is designed for I
2
:
μ
2
+
μ
6
+
μ
V
S
2
=
2. As a result, we have M
0
A
(
V
S
2
)
=
1, V
S
2
∙
=
{
t
2
,
t
7
}, and V
S
2
∙
=
{
t
1
,
t
6
}. Only FBM3 is prohibited by I
2: that is, F
I
2
=
{
F
B
M
3
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
∅.Algorithm10 is terminated. Totally, there are two monitors computed for this net. We add the two monitors to the original Petri net model. The controlled system after addition is as shown in Figure 5. Table 5 shows the two required monitors by using Algorithm 10.Table 5
Required monitors using Algorithm10.
i
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
1
t
3
,
2
t
6
t
1
,
2
t
5
2
2
t
2
,
t
7
t
1
,
t
6
1Figure 5
Controlled system of the Petri net in Figure1(b) by Algorithm 10.


## 4.1. Siphon Control Methods

This section presents two methods that are motivated by Ezpeleta et al. [13] and Li and Zhou [11]. These methods are called a strict minimal siphons control method and an elementary siphons control method, respectively.


### 4.1.1. Strict Minimal Siphons (SMSs) Control Method

A siphon in a Petri net is a set of placesS
=
{
p
1
,
…
,
p
k
}. The very important property of siphon is that, for a given marking, the siphon is unmarked.Definition 1.
LetN be a net. Any set S
⊆
P, S
≠
∅ with S
∙
⊆
S
∙ is called a siphon. If a siphon does not properly contain another siphon is called a minimal siphon. A minimal siphon S is called a strict if S
∙
⊊
S
∙.
Siphons play a significant role in the liveness analysis of a Petri net, especially in ordinary ones. If a siphonS in a net has no tokens, then no transitions in S
∙ are enabled and all the transitions connected to S cannot be fired; as a result, the transitions are dead leading to the loss of liveness of the Petri net. In [13], a monitor is added to each strict minimal siphon in order to achieve the liveness of the system. The proposed approach is simple and ensures a success. Nevertheless, it leads to a complex Petri net model than the originally model because the added places are equal to the strict minimal siphons in the target net model and the added arcs are larger than that of places added.
The SMS control based on complementary sets of siphonsS is used to design the control places. A complementary set of a siphon S is a set of operation places which are the holders of the resources in S but do not belong to S. In addition, S
∪
S is the support of a place invariant, which means the operation places in S will compete for the resources in S with the operation places belonging to S. S will be unmarked when all tokens in S flow into S. The following notation will be used in the establishment of the control policy.(1)
S denotes the set of strict minimal siphons which does not contain the support of any place semiflow (i.e., siphons that can be emptied).
(2)
Given the fact thatS is a siphon we have S
=
S
A
∪
S
R, S
R
=
S
∩
P
R, S
A
=
S
∖
S
R, where S
A is the operation places and S
R is the resource places. S denotes the following set of state places: S
=
(
U
r
∈
S
R
H
(
r
)
)
∖
S
A, where H
r
=
I
r
+
∖
r, I
r
+
=
{
p
∣
I
(
p
)
>
0
} indicates the positive support of place invariant I, ∀
i
,
j
∈
1,2
,
…
,
n
i
≠
j,  H
r
i
∩
H
r
j
=
∅. For a given siphon S, S is the set of holders, corresponding to resources in S that do not belong to S. S is called S’s complementary set.
(3)
Given the fact thatS is a complementary set of S, add a control place for S and the initial marking of control place is M
0
A
(
V
S
)
=
M
0
(
S
)
-
1.
Based on the concept of strict minimal siphon, the proposed deadlock prevention algorithm developed by Ezpeleta et al. [13] is stated as follows.Algorithm 2 (SMS based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), compute all SMSs.
Step
2. For each siphon SMS, add a monitor V
S such that(i)
theV
S output arcs are connected to the source transitions leading to the sink transitions of S and all arcs weights are ones;
(ii)
theV
S input arcs are connected from the stealing places of S and all arcs weights are ones;
(iii)
M
0
A
(
V
S
)
=
M
0
(
S
)
-
1, where M
0
A
(
V
S
) is an initial marking of a monitor.
Step
3. Repeat Step 2 until all existing SMSs are covered.
Step
4. Add all monitors into (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
5. Output (N
1
,
M
1).
Step
6. End.For instance, consider the AMS shown in Figure1(a). Its Petri net model is shown in Figure 1(b). It consists of one robot R1 that can hold a part at a time, two machines M1 and M2, where each machine can process a part at a time, two loading buffers (I1 and I2), and unloading buffers (O1 and O2). Two parts types are considered in the system: PA and PB. PA moves to M1 and PB moves to M2. The robot R1 reaches the machine that finishes its operation first and grips and loads the part to the next machine 1 or machine 2. The Petri net model consists of 11 places and 8 transitions. The places have the following set partition: P
0
=
{
P
1
,
P
8
}, P
R
=
{
P
9
,
P
10
,
P
11
}, and P
A
=
{
P
2
,
…
,
P
7
}, where P
0 is the input places, P
R is the resources places, and P
A is the operation places. It has 8 minimal siphons, 3 of which are strict minimal siphons and 20 reachable markings. The three SMSs are S
1
=
{
P
4
,
P
7
,
P
9
,
P
10
,
P
11
}, S
2
=
{
P
4
,
P
6
,
P
10
,
P
11
}, and S
3
=
{
P
3
,
P
7
,
P
9
,
P
10
}. Table 1 shows the required monitors using Algorithm 2 for Figure 1(b). Figure 2 illustrates the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 2.Table 1
Control places computations by Algorithm2.
SMS
I
+
H
(
r
R
)
S
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
S
1
=
{
P
4
,
P
7
,
P
9
,
P
10
,
P
11
}
,
S
A
=
{
P
4
,
P
7
}
,
S
R
=
{
P
9
,
P
10
,
P
11
}.
I
p
9
+
=
{
p
2
,
p
7
,
p
9
}
,
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}
,
I
p
11
+
=
{
p
4
,
p
5
,
p
11
}.
H
r
9
=
p
2
,
p
7,
H
r
10
=
p
3
,
p
6,
H
r
11
=
p
4
,
p
5.
S
1
=
{
p
2
,
p
3
,
p
5
,
p
6
}.
t
3
,
t
7
t
1
,
t
5
2
S
2
=
{
P
4
,
P
6
,
P
10
,
P
11
}
,
S
A
=
{
P
4
,
P
6
}
,
S
R
=
{
P
10
,
P
11
}.
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}
,
I
p
11
+
=
{
p
4
,
p
5
,
p
11
}.
H
r
10
=
p
3
,
p
6,
H
r
11
=
p
4
,
p
5.
S
2
=
{
p
3
,
p
5
}.
t
3
,
t
6
t
2
,
t
5
1
S
3
=
{
P
3
,
P
7
,
P
9
,
P
10
}
,
S
A
=
{
P
3
,
P
7
}
,
S
R
=
{
P
9
,
P
10
}.
I
p
9
+
=
{
p
2
,
p
7
,
p
9
}
,
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}.
H
r
9
=
p
2
,
p
7,
H
r
10
=
p
3
,
p
6.
S
3
=
{
p
2
,
p
6
}.
t
2
,
t
7
t
1
,
t
5
1Figure 1
(a) An AMS example and (b) Petri net model of an AMS.
(a)
(b)Figure 2
Controlled system of the Petri net in Figure1(b) by Algorithm 2.


### 4.1.2. Elementary Siphons Control Method

The strict minimal siphons (SMSs) are classified into elementary and dependent ones. Π is used to denote the set of strict minimal siphons whileΠ
E and Π
D denote the sets of elementary and dependent (redundant) ones, respectively. Otherwise, when a strict minimal one is mentioned, it can be called a siphon.Definition 3.
Let an ordinary Petri net (N
,
M
0) and S is a siphon, S
⊆
P. Place vector λ
S is said to be the characteristic place vector of S if for all p
∈
S, λ
S
(
p
)
=
1; otherwise, λ
S
(
p
)
=
0.Definition 4.
LetN
=
(
P
,
T
,
F
) be an ordinary Petri net with P
=
m, T
=
n, and we suppose that N has f SMS, S
1
,
S
2
,
…, and S
f
,
m
,
n
,
f
∈
I
N
. Let λ
S
i
(
η
S
i
) be the characteristic place (transition) vector of siphon S
i, i
∈
{
1,2
,
…
,
n
}. We define λ
f
×
m
=
λ
S
1
,
λ
S
2
,
…
,
λ
S
f
T and η
f
×
n
=
λ
f
×
m
·
N
m
×
n are said to be the characteristic place vector and transition vector matrices of the siphons of N, respectively.Proposition 5.
LetN be an ordinary Petri net and let η be the characteristic transition vector matrix of the siphons of it. The set of elementary siphons in N can be defined as a rank of η.From Proposition5, it can easily enumerate all elementary siphons in a Petri net system (N
,
M
0) given all siphons. First, compute matrices λ and η. Then independent linear vectors can be determined in η. Finally, the siphons that correspond to these independent linear vectors are called the elementary siphons in the Petri net (N
,
M
0). Li and Zhou [11] introduced some results and theorems as follows.Theorem 6.
LetN
0 be a marked ordinary Petri net and S
=
{
p
i
1
,
p
i
2
,
…
,
p
i
n
} be a siphon in N
0. Monitor V
S is added to N
0, and the new net system can be denoted by (
N
1
,
M
1
), such that (a) I
1
=
…
,
1
p
i
1
,
1
p
i
2
,
…
,
1
p
i
n
,
…
,
-
1
V
S
,
…
T is a place invariant of N
1 and (b) M
1
(
V
S
)
=
M
0
(
S
)
-
ξ
S, where ξ
S is said to be the control depth variable of siphon S, which states the least number of tokens that siphon can hold. Evidently is greater than or equal to 1 to fulfil purpose of control 1
≤
ξ
S
≤
M
0
(
S
)
-
1, and (c) for all p
∈
P
0, M
1
(
p
)
=
M
0
(
p
), where P
0 is the set of operation places of N
0, such that S can be called invariant-controlled.Theorem 7.
Let(
N
,
M
0
) be an ordinary Petri net and let S
0 be a generally dependent siphon on elementary siphons S
1
,
S
2
,
…
,
S
n
,
S
n
+
1
,
S
n
+
2
,
…, and S
n
+
m that means η
S
0
=
∑
i
=
1
n
a
i
·
η
S
i
-
∑
j
=
n
+
1
n
+
m
a
j
·
η
S
j. If S
1
,
S
2
,
…
,
S
n
,
S
n
+
1
,
S
n
+
2,…, and S
n
+
m are invariant-controlled by adding monitors V
S
1
,
V
S
2
,
…
,
V
S
n
+
m
,
…, and M
0
(
S
0
)
>
∑
i
=
1
n
a
i
·
M
0
S
i
-
∑
i
=
1
n
a
i
·
ξ
S
i, where 1
≤
ξ
S
i
≤
M
0
(
S
i
)
-
1, S
0 is called controlled. Based on the concept of elementary siphons, the proposed deadlock prevention algorithm developed by Li and Zhou [11] is stated as follows.Algorithm 8 (elementary siphon-based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), compute all SMSs.
Step
2. Compute the transition vector matrix η of the SMS.
Step
3. Compute the elementary siphons of Petri net N. The remaining are the dependent siphons.
Step
4. For each siphon elementary siphon, add a monitor V
S such that(i)
theV
S output arcs are connected to the source transitions leading to the sink transitions of S and all arcs weights are ones;
(ii)
theV
S input arcs are connected from the stealing places of S and all arcs weights are ones;
(iii)
M
0
A
(
V
S
)
=
M
0
(
S
)
-
ξ
S, where M
0
A
(
V
S
) is an initial marking of a monitor and 1
≤
ξ
S
≤
M
0
(
S
)
-
1.
Step
5. Repeat Step 4 until all elementary siphons are covered.
Step
6. Adjust ξ
i, such that each dependent siphon is controlled.
Step
7. Add all monitors to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
8. Output (N
1
,
M
1).
Step
9. End.For example, there are three SMSs in the Petri net model shown in Figure1(b), which are S
1
=
{
p
4
,
p
7
,
p
9
,
p
10
,
p
11
}, S
2
=
{
p
4
,
p
6
,
p
10
,
p
11
}, and S
3
=
{
p
3
,
p
7
,
p
9
,
p
10
}. One can obtain that λ
S
1
=
(
0,0
,
0,1
,
0,0
,
1,0
,
1,1
,
1
)
T, λ
S
2
=
(
0,0
,
0,1
,
0,1
,
0,0
,
0,1
,
1
)
T, and λ
S
3
=
(
0,0
,
1,0
,
0,0
,
1,0
,
1,1
,
0
)
T. Hence, η
S
1
=
(
-
1,0
,
1,0
,
-
1,0
,
1,0
)
T, η
S
2
=
(
0
,
-
1,1
,
0
,
-
1,1
,
0,0
)
T, and η
S
3
=
(
-
1,1
,
0,0
,
0
,
-
1,1
,
0
)
T. The transition vector matrix η for the Petri net model in Figure 1(b) is as follows. Obviously, the rank of η is 2 since the first row η
S
1 can be linearly represented by the second and third rows, and we can see that η
S
1
=
η
S
2
+
η
S
3. As a result, the siphons that correspond to the second and third rows S
2 and S
3 are elementary siphons. Thus, S
1 is a dependent siphon:(1)
η
=
-
1
0
1
0
-
1
0
1
0
0
-
1
1
0
-
1
1
0
0
-
1
1
0
0
0
-
1
1
0
.The dependent siphons and their elementary siphons, the initial marking relationships between dependent and elementary siphons, and the controllability of dependent siphons due to Theorem 7 are shown in Table 2. Table 3 shows the required monitors using Algorithm 8 for Figure 1(b). Figure 3 presents the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 8.Table 2
Marking relationships between dependent and elementary siphons.
Dependent
η relationship
Initial marking relationships,
M
0
(
S
0
)
>
∑
i
=
1
n
a
i
⋅
M
0
S
i
-
∑
i
=
1
n
a
i
⋅
ξ
S
i
Controlled
S
1
η
1
=
η
2
+
η
3
M
0
(
S
1
)
>
(
M
0
(
S
2
)
+
M
0
(
S
3
)
)
-
(
ξ
S
2
+
ξ
S
3
) 3 > (2 + 2) − (1 + 1),  3 > 2
YesTable 3
Required monitors using Algorithm8.
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
S
2
t
3
,
t
6
t
2
,
t
5
1
S
3
t
2
,
t
7
t
1
,
t
5
1Figure 3
Controlled system of the Petri net in Figure1(b) by Algorithm 8.


## 4.1.1. Strict Minimal Siphons (SMSs) Control Method

A siphon in a Petri net is a set of placesS
=
{
p
1
,
…
,
p
k
}. The very important property of siphon is that, for a given marking, the siphon is unmarked.Definition 1.
LetN be a net. Any set S
⊆
P, S
≠
∅ with S
∙
⊆
S
∙ is called a siphon. If a siphon does not properly contain another siphon is called a minimal siphon. A minimal siphon S is called a strict if S
∙
⊊
S
∙.
Siphons play a significant role in the liveness analysis of a Petri net, especially in ordinary ones. If a siphonS in a net has no tokens, then no transitions in S
∙ are enabled and all the transitions connected to S cannot be fired; as a result, the transitions are dead leading to the loss of liveness of the Petri net. In [13], a monitor is added to each strict minimal siphon in order to achieve the liveness of the system. The proposed approach is simple and ensures a success. Nevertheless, it leads to a complex Petri net model than the originally model because the added places are equal to the strict minimal siphons in the target net model and the added arcs are larger than that of places added.
The SMS control based on complementary sets of siphonsS is used to design the control places. A complementary set of a siphon S is a set of operation places which are the holders of the resources in S but do not belong to S. In addition, S
∪
S is the support of a place invariant, which means the operation places in S will compete for the resources in S with the operation places belonging to S. S will be unmarked when all tokens in S flow into S. The following notation will be used in the establishment of the control policy.(1)
S denotes the set of strict minimal siphons which does not contain the support of any place semiflow (i.e., siphons that can be emptied).
(2)
Given the fact thatS is a siphon we have S
=
S
A
∪
S
R, S
R
=
S
∩
P
R, S
A
=
S
∖
S
R, where S
A is the operation places and S
R is the resource places. S denotes the following set of state places: S
=
(
U
r
∈
S
R
H
(
r
)
)
∖
S
A, where H
r
=
I
r
+
∖
r, I
r
+
=
{
p
∣
I
(
p
)
>
0
} indicates the positive support of place invariant I, ∀
i
,
j
∈
1,2
,
…
,
n
i
≠
j,  H
r
i
∩
H
r
j
=
∅. For a given siphon S, S is the set of holders, corresponding to resources in S that do not belong to S. S is called S’s complementary set.
(3)
Given the fact thatS is a complementary set of S, add a control place for S and the initial marking of control place is M
0
A
(
V
S
)
=
M
0
(
S
)
-
1.
Based on the concept of strict minimal siphon, the proposed deadlock prevention algorithm developed by Ezpeleta et al. [13] is stated as follows.Algorithm 2 (SMS based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), compute all SMSs.
Step
2. For each siphon SMS, add a monitor V
S such that(i)
theV
S output arcs are connected to the source transitions leading to the sink transitions of S and all arcs weights are ones;
(ii)
theV
S input arcs are connected from the stealing places of S and all arcs weights are ones;
(iii)
M
0
A
(
V
S
)
=
M
0
(
S
)
-
1, where M
0
A
(
V
S
) is an initial marking of a monitor.
Step
3. Repeat Step 2 until all existing SMSs are covered.
Step
4. Add all monitors into (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
5. Output (N
1
,
M
1).
Step
6. End.For instance, consider the AMS shown in Figure1(a). Its Petri net model is shown in Figure 1(b). It consists of one robot R1 that can hold a part at a time, two machines M1 and M2, where each machine can process a part at a time, two loading buffers (I1 and I2), and unloading buffers (O1 and O2). Two parts types are considered in the system: PA and PB. PA moves to M1 and PB moves to M2. The robot R1 reaches the machine that finishes its operation first and grips and loads the part to the next machine 1 or machine 2. The Petri net model consists of 11 places and 8 transitions. The places have the following set partition: P
0
=
{
P
1
,
P
8
}, P
R
=
{
P
9
,
P
10
,
P
11
}, and P
A
=
{
P
2
,
…
,
P
7
}, where P
0 is the input places, P
R is the resources places, and P
A is the operation places. It has 8 minimal siphons, 3 of which are strict minimal siphons and 20 reachable markings. The three SMSs are S
1
=
{
P
4
,
P
7
,
P
9
,
P
10
,
P
11
}, S
2
=
{
P
4
,
P
6
,
P
10
,
P
11
}, and S
3
=
{
P
3
,
P
7
,
P
9
,
P
10
}. Table 1 shows the required monitors using Algorithm 2 for Figure 1(b). Figure 2 illustrates the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 2.Table 1
Control places computations by Algorithm2.
SMS
I
+
H
(
r
R
)
S
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
S
1
=
{
P
4
,
P
7
,
P
9
,
P
10
,
P
11
}
,
S
A
=
{
P
4
,
P
7
}
,
S
R
=
{
P
9
,
P
10
,
P
11
}.
I
p
9
+
=
{
p
2
,
p
7
,
p
9
}
,
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}
,
I
p
11
+
=
{
p
4
,
p
5
,
p
11
}.
H
r
9
=
p
2
,
p
7,
H
r
10
=
p
3
,
p
6,
H
r
11
=
p
4
,
p
5.
S
1
=
{
p
2
,
p
3
,
p
5
,
p
6
}.
t
3
,
t
7
t
1
,
t
5
2
S
2
=
{
P
4
,
P
6
,
P
10
,
P
11
}
,
S
A
=
{
P
4
,
P
6
}
,
S
R
=
{
P
10
,
P
11
}.
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}
,
I
p
11
+
=
{
p
4
,
p
5
,
p
11
}.
H
r
10
=
p
3
,
p
6,
H
r
11
=
p
4
,
p
5.
S
2
=
{
p
3
,
p
5
}.
t
3
,
t
6
t
2
,
t
5
1
S
3
=
{
P
3
,
P
7
,
P
9
,
P
10
}
,
S
A
=
{
P
3
,
P
7
}
,
S
R
=
{
P
9
,
P
10
}.
I
p
9
+
=
{
p
2
,
p
7
,
p
9
}
,
I
p
10
+
=
{
p
3
,
p
6
,
p
10
}.
H
r
9
=
p
2
,
p
7,
H
r
10
=
p
3
,
p
6.
S
3
=
{
p
2
,
p
6
}.
t
2
,
t
7
t
1
,
t
5
1Figure 1
(a) An AMS example and (b) Petri net model of an AMS.
(a)
(b)Figure 2
Controlled system of the Petri net in Figure1(b) by Algorithm 2.


## 4.1.2. Elementary Siphons Control Method

The strict minimal siphons (SMSs) are classified into elementary and dependent ones. Π is used to denote the set of strict minimal siphons whileΠ
E and Π
D denote the sets of elementary and dependent (redundant) ones, respectively. Otherwise, when a strict minimal one is mentioned, it can be called a siphon.Definition 3.
Let an ordinary Petri net (N
,
M
0) and S is a siphon, S
⊆
P. Place vector λ
S is said to be the characteristic place vector of S if for all p
∈
S, λ
S
(
p
)
=
1; otherwise, λ
S
(
p
)
=
0.Definition 4.
LetN
=
(
P
,
T
,
F
) be an ordinary Petri net with P
=
m, T
=
n, and we suppose that N has f SMS, S
1
,
S
2
,
…, and S
f
,
m
,
n
,
f
∈
I
N
. Let λ
S
i
(
η
S
i
) be the characteristic place (transition) vector of siphon S
i, i
∈
{
1,2
,
…
,
n
}. We define λ
f
×
m
=
λ
S
1
,
λ
S
2
,
…
,
λ
S
f
T and η
f
×
n
=
λ
f
×
m
·
N
m
×
n are said to be the characteristic place vector and transition vector matrices of the siphons of N, respectively.Proposition 5.
LetN be an ordinary Petri net and let η be the characteristic transition vector matrix of the siphons of it. The set of elementary siphons in N can be defined as a rank of η.From Proposition5, it can easily enumerate all elementary siphons in a Petri net system (N
,
M
0) given all siphons. First, compute matrices λ and η. Then independent linear vectors can be determined in η. Finally, the siphons that correspond to these independent linear vectors are called the elementary siphons in the Petri net (N
,
M
0). Li and Zhou [11] introduced some results and theorems as follows.Theorem 6.
LetN
0 be a marked ordinary Petri net and S
=
{
p
i
1
,
p
i
2
,
…
,
p
i
n
} be a siphon in N
0. Monitor V
S is added to N
0, and the new net system can be denoted by (
N
1
,
M
1
), such that (a) I
1
=
…
,
1
p
i
1
,
1
p
i
2
,
…
,
1
p
i
n
,
…
,
-
1
V
S
,
…
T is a place invariant of N
1 and (b) M
1
(
V
S
)
=
M
0
(
S
)
-
ξ
S, where ξ
S is said to be the control depth variable of siphon S, which states the least number of tokens that siphon can hold. Evidently is greater than or equal to 1 to fulfil purpose of control 1
≤
ξ
S
≤
M
0
(
S
)
-
1, and (c) for all p
∈
P
0, M
1
(
p
)
=
M
0
(
p
), where P
0 is the set of operation places of N
0, such that S can be called invariant-controlled.Theorem 7.
Let(
N
,
M
0
) be an ordinary Petri net and let S
0 be a generally dependent siphon on elementary siphons S
1
,
S
2
,
…
,
S
n
,
S
n
+
1
,
S
n
+
2
,
…, and S
n
+
m that means η
S
0
=
∑
i
=
1
n
a
i
·
η
S
i
-
∑
j
=
n
+
1
n
+
m
a
j
·
η
S
j. If S
1
,
S
2
,
…
,
S
n
,
S
n
+
1
,
S
n
+
2,…, and S
n
+
m are invariant-controlled by adding monitors V
S
1
,
V
S
2
,
…
,
V
S
n
+
m
,
…, and M
0
(
S
0
)
>
∑
i
=
1
n
a
i
·
M
0
S
i
-
∑
i
=
1
n
a
i
·
ξ
S
i, where 1
≤
ξ
S
i
≤
M
0
(
S
i
)
-
1, S
0 is called controlled. Based on the concept of elementary siphons, the proposed deadlock prevention algorithm developed by Li and Zhou [11] is stated as follows.Algorithm 8 (elementary siphon-based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), compute all SMSs.
Step
2. Compute the transition vector matrix η of the SMS.
Step
3. Compute the elementary siphons of Petri net N. The remaining are the dependent siphons.
Step
4. For each siphon elementary siphon, add a monitor V
S such that(i)
theV
S output arcs are connected to the source transitions leading to the sink transitions of S and all arcs weights are ones;
(ii)
theV
S input arcs are connected from the stealing places of S and all arcs weights are ones;
(iii)
M
0
A
(
V
S
)
=
M
0
(
S
)
-
ξ
S, where M
0
A
(
V
S
) is an initial marking of a monitor and 1
≤
ξ
S
≤
M
0
(
S
)
-
1.
Step
5. Repeat Step 4 until all elementary siphons are covered.
Step
6. Adjust ξ
i, such that each dependent siphon is controlled.
Step
7. Add all monitors to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
8. Output (N
1
,
M
1).
Step
9. End.For example, there are three SMSs in the Petri net model shown in Figure1(b), which are S
1
=
{
p
4
,
p
7
,
p
9
,
p
10
,
p
11
}, S
2
=
{
p
4
,
p
6
,
p
10
,
p
11
}, and S
3
=
{
p
3
,
p
7
,
p
9
,
p
10
}. One can obtain that λ
S
1
=
(
0,0
,
0,1
,
0,0
,
1,0
,
1,1
,
1
)
T, λ
S
2
=
(
0,0
,
0,1
,
0,1
,
0,0
,
0,1
,
1
)
T, and λ
S
3
=
(
0,0
,
1,0
,
0,0
,
1,0
,
1,1
,
0
)
T. Hence, η
S
1
=
(
-
1,0
,
1,0
,
-
1,0
,
1,0
)
T, η
S
2
=
(
0
,
-
1,1
,
0
,
-
1,1
,
0,0
)
T, and η
S
3
=
(
-
1,1
,
0,0
,
0
,
-
1,1
,
0
)
T. The transition vector matrix η for the Petri net model in Figure 1(b) is as follows. Obviously, the rank of η is 2 since the first row η
S
1 can be linearly represented by the second and third rows, and we can see that η
S
1
=
η
S
2
+
η
S
3. As a result, the siphons that correspond to the second and third rows S
2 and S
3 are elementary siphons. Thus, S
1 is a dependent siphon:(1)
η
=
-
1
0
1
0
-
1
0
1
0
0
-
1
1
0
-
1
1
0
0
-
1
1
0
0
0
-
1
1
0
.The dependent siphons and their elementary siphons, the initial marking relationships between dependent and elementary siphons, and the controllability of dependent siphons due to Theorem 7 are shown in Table 2. Table 3 shows the required monitors using Algorithm 8 for Figure 1(b). Figure 3 presents the controlled system of the Petri net model in Figure 1(b) after adding monitors by using Algorithm 8.Table 2
Marking relationships between dependent and elementary siphons.
Dependent
η relationship
Initial marking relationships,
M
0
(
S
0
)
>
∑
i
=
1
n
a
i
⋅
M
0
S
i
-
∑
i
=
1
n
a
i
⋅
ξ
S
i
Controlled
S
1
η
1
=
η
2
+
η
3
M
0
(
S
1
)
>
(
M
0
(
S
2
)
+
M
0
(
S
3
)
)
-
(
ξ
S
2
+
ξ
S
3
) 3 > (2 + 2) − (1 + 1),  3 > 2
YesTable 3
Required monitors using Algorithm8.
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
S
2
t
3
,
t
6
t
2
,
t
5
1
S
3
t
2
,
t
7
t
1
,
t
5
1Figure 3
Controlled system of the Petri net in Figure1(b) by Algorithm 8.


## 4.2. Iterative Methods

This section presents two techniques that are motivated and developed by [25]. These techniques are used to design a place invariant (PI) that can prohibit as many forbidden bad markings (FBMs) as possible. First, the vector covering method is used to find the minimal covering sets of legal markings and FBMs (see Chen et al. [1]). Then, solving the integer linear programming problem (ILPP) can obtain the coefficients of the place invariant and monitors. An iterative monitor design process is executed. At each iteration, a place invariant is designed to prohibit as many FBMs as possible. All FBMs that are prohibited by the place invariant are eliminated from the minimal covered set of FBMs. This process is terminated when all the minimal covered sets of FBMs are forbidden.


### 4.2.1. Maximal Number of Forbidding FBM Problem 1

The Maximal number of Forbidding FBM Problem 1 (MFFP1) is a technique used to design a monitor synthesis for FBMs. This technique used ILPP to obtain the coefficients of the place invariant that prohibit as many FBMs as possible. The MFFP1 is shown in the following mathematical model.MFFP1 is(2)
max
⁡
f
=
∑
k
∈
N
F
B
M
∗
f
k
subject to
∑
i
∈
N
A
l
i
·
M
l
p
i
≤
β
,
∀
M
l
∈
M
L
∗
(3)
∑
i
∈
N
A
l
i
·
M
k
p
i
≥
β
+
1
-
Q
·
1
-
f
k
,
∀
M
k
∈
M
F
B
M
∗
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
I
N
β
∈
1,2
,
…
f
k
∈
0,1
,
∀
k
∈
N
F
B
M
∗
,where M
L
∗ and M
F
B
M
∗ are the minimal covering sets of legal markings and FBMs, respectively. The objective function f is used to maximize the number of FBMs that are forbidden by place invariant. If f
=
0, we have f
k
=
0, for all k
∈
N
F
B
M
∗ (N
F
B
M
∗ is used to denote {
i
∣
M
i
∈
M
F
B
M
∗
}): that is to say, no FBMs in M
F
B
M
∗ can be prohibited by place invariant. In (2), let I be a place invariant, where l
i’s (i
∈
I
N) are the coefficients of I, β is a positive integer variable, and M
l
p
i
(
∀
M
l
∈
M
L
∗
) are the number of tokens in minimal covering set of legal markings.All legal markings should be kept after a monitor is added, implying that every markingM
l
∈
M
L
∗ cannot be forbidden from being reached, and coefficients l
i’s (i
∈
I
N) should satisfy (2) that is called the reachability condition.In (3), Q is a positive integer constant number that must be large enough, M
k
p
i
(
∀
M
k
∈
M
F
B
M
∗
) are the number of tokens in minimal covering set of FBMs, and f
k’s (f
k
∈
{
0,1
}
,
k
=
1,2
,
…) are a set of M
F
B
M
∗ variables. Moreover, in (3), f
k
=
1 implies that M
k is prohibited by I and f
k
=
0 implies that this constraint is redundant and M
k cannot be prohibited by I.Based on the concept of MFFP1, the proposed deadlock prevention algorithm developed in [25] is stated as follows.Algorithm 9 (MFFP1 based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), find the sets of FBMs M
F
B
M and legal markings M
L.
Step
2. Find the minimal covered sets of FBMs M
F
B
M
∗ and legal markings M
L
∗.
Step
3. V
M
≔
∅. /
V
M
∗ is used to indicate the set of monitors to be found. /
∗
Step
4. While {
M
F
B
M
∗
≠
∅
}, do the following.(i)
Design MFFP1.
(ii)
Solve MFFP1. Letl
i’s (i
∈
I
N) and β be the solution if f
∗
≠
0.
Otherwise, exit, as the solution does not exist.
(iii)
Design a place invariantI and a monitor V
S.
(iv)
V
M
≔
V
M
∪
{
V
S
} and M
F
B
M
∗
=
M
F
B
M
∗
-
F
I. /
∗
F
I is covered M
F
B
M
∗
endwhile.
Step
5. Add all monitors in V
M to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
6. Output (N
1
,
M
1).
Step
7. End.For the Petri net model shown in Figure1(b), we have M
F
B
M
∗
=
{
p
2
+
p
5
,
p
3
+
p
5
,
p
2
+
p
6
} and M
L
∗
=
{
p
2
+
p
3
+
p
4
,
p
5
+
p
6
+
p
7
}. Algorithm 9 is considered. At the first iteration, let I
1 be the place invariant to be calculated. I
1 should satisfy (2) for the two legal markings in M
L
∗: that is, l
2
·
1
+
l
3
·
1
+
l
4
·
1
≤
β and l
5
·
1
+
l
6
·
1
+
l
7
·
1
≤
β. Therefore, we have the following two constraints:(4)
l
2
+
l
3
+
l
4
≤
β
,
l
5
+
l
6
+
l
7
≤
β
.We introduce three variables f
1, f
2, and f
3 (f
1
,
f
2
,
f
3
∈
{
0,1
}) to represent whether I
1 forbids F
B
M
1
=
p
2
+
p
5, F
B
M
2
=
p
3
+
p
5, and F
B
M
3
=
p
2
+
p
6, respectively. Therefore, we have the following three constraints: that is,(5)
l
2
+
l
5
≥
β
+
1
-
Q
·
1
-
f
1
,
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
,
l
2
+
l
6
≥
β
+
1
-
Q
·
1
-
f
3
.Finally, MFFP1 is defined as follows.MFFP1 is(6)
max
⁡
f
=
f
1
+
f
2
+
f
3
subject to
l
2
+
l
3
+
l
4
≤
β
l
5
+
l
6
+
l
7
≤
β
l
2
+
l
5
≥
β
+
1
-
Q
·
1
-
f
1
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
l
2
+
l
6
≥
β
+
1
-
Q
·
1
-
f
3
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
β
∈
1,2
,
…
f
k
∈
0,1
,
∀
k
∈
1,2
,
3
.The optimal solution of the above MFFP1 is l
2
=
2, l
5
=
1, l
6
=
1, β
=
2, f
1
=
1, and f
3
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
1 is designed for I
1
:
2
μ
2
+
μ
5
+
μ
6
+
μ
V
S
1
=
2. As a result, we have M
0
A
(
V
S
1
)
=
β
=
2, V
S
1
∙
=
{
2
t
2
,
t
7
}, and V
S
1
∙
=
{
2
t
1
,
t
5
}. FBM1 and FBM3 are prohibited by I
1: that is, F
I
1
=
{
F
B
M
1
,
F
B
M
3
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
F
B
M
3
=
{
p
3
+
p
5
}.At the next iteration, letI
2 place invariant be calculated. The new MFFP1 can be easily obtained by eliminating constraints that related to FBM1 and FBM3 from the first MFFP1. Therefore, the new MFFP1 is stated as follows.MFFP1 is(7)
max
⁡
f
=
f
2
subject to
l
2
+
l
3
+
l
4
≤
β
l
5
+
l
6
+
l
7
≤
β
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
β
∈
1,2
,
…
f
2
∈
0,1
.The optimal solution of the above MFFP1 is l
3
=
1, l
5
=
1, β
=
1, and f
2
=
1 and all the remaining variables are equal to zero. Then, a monitor V
S
2 is designed for I
2
:
μ
3
+
μ
5
+
μ
V
S
2
=
1. As a result, we have M
0
A
(
V
S
2
)
=
β
=
1, V
S
1
∙
=
{
t
3
,
t
6
}, and V
S
1
∙
=
{
t
2
,
t
5
}. Only FBM2 is prohibited by I
2: that is, F
I
2
=
{
F
B
M
2
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
2: that is, M
F
B
M
∗
=
∅.Algorithm9 is terminated. Totally, there are two monitors computed for this net. Adding the two monitors to the original Petri net model, the controlled system after addition is as shown in Figure 4. Table 4 shows the two required monitors by using Algorithm 9.Table 4
Required monitors using Algorithm9.
i
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
1
2
t
2
,
t
7
2
t
1
,
t
5
2
2
t
3
,
t
6
t
2
,
t
5
1Figure 4
Controlled system of the Petri net in Figure1(b) by Algorithm 9.


### 4.2.2. Maximal Number of Forbidding FBM Problem 2

The Maximal number of Forbidding FBM Problem 1 has been modified to improve its efficiency and its number of variables and constraints are slightly reduced. The modified technique is called a Maximal number of Forbidding FBM Problem 2 (MFFP2). The MFFP1 is shown in the following mathematical model.MFFP2 is(8)
max
⁡
f
=
∑
k
∈
N
F
B
M
∗
,
k
≠
j
f
k
subject to
∑
i
∈
N
A
l
i
·
M
l
p
i
-
M
j
p
i
≤
-
1
,
∀
M
l
∈
M
L
∗
∑
i
∈
N
A
l
i
·
M
k
p
i
-
M
j
p
i
≥
-
Q
·
1
-
f
k
,
∀
M
k
∈
M
F
B
M
∗
,
k
≠
j
(9)
l
i
∈
0,1
,
2
,
…
.
,
∀
i
∈
I
N
f
k
∈
0,1
,
∀
k
∈
N
F
B
M
∗
,
k
≠
j
.The objective function is maximizing f the number of FBMs that are prohibited by place invariant. If no solution has been obtained from MFFP2 for an FBM, then there are not any FBMs in M
F
B
M
∗ that can be forbidden by that place invariant.In (8), l
i’s (i
∈
I
N) are the coefficients of I, M
l
p
i
(
∀
M
l
∈
M
L
∗
) are the number of tokens in minimal covering set of legal markings, and M
j
p
i are the number of tokens in selected F
B
M
j. In (9), Q is a positive integer constant number that must be large enough, M
k
p
i
(
∀
M
k
∈
M
F
B
M
∗
) are the number of tokens in minimal covering set of FBMs, and f
k’s (f
k
∈
{
0,1
}
,
k
=
1,2
,
…) are a set of M
F
B
M
∗ variables. In (9), f
k
=
1 implies that M
k is prohibited by I and f
k
=
0 implies that this constraint is redundant and M
k cannot be prohibited by I.Based on the concept of MFFP2, the proposed deadlock prevention algorithm developed in [25] is stated as follows.Algorithm 10 (MFFP2 based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), find the sets of FBMs M
F
B
M and legal markings M
L.
Step
2. Find the minimal covered sets of FBMs M
F
B
M
∗ and legal markings M
L
∗.
Step
3. V
M
≔
∅. /
∗
V
M is used to indicate the set of monitors to be found. /
∗
Step
4. While {
M
F
B
M
∗
≠
∅
}, do the following.(i)
Design MFF2.
(ii)
Solve MFFP2. Letl
i’s (i
∈
N
A) and β be the solution if f
∗
≠
0. Otherwise, exit, as the solution does not exist.
(iii)
Design a place invariantI and a monitor V
S
V
M
≔
V
M
∪
{
V
S
} and M
F
B
M
∗
=
M
F
B
M
∗
-
F
I. /
∗
F
I is covered M
F
B
M
∗
endwhile.
Step
5. Add all monitors in V
M to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
6. Output (N
1
,
M
1).
Step
7. End.Consider the Petri net model shown in Figure1(b) by Algorithm 10. At the first iteration, F
B
M
1
=
p
2
+
p
5 is chosen. Let I
1 be the place invariant to prohibit FBM1, whose coefficients are l
i’s (i
∈
{
2,3
,
4,5
,
6,7
}). I
1 should satisfy (8) that is called the reachability condition and does not prohibit any marking in M
L
∗. Therefore, I
1 should satisfy two constraints:(10)
l
2
·
1
-
1
+
l
3
·
1
-
0
+
l
4
·
1
-
0
+
l
5
·
0
-
1
+
l
6
·
0
-
0
+
l
7
·
0
-
0
≤
-
1
,
l
2
·
0
-
1
+
l
3
·
0
-
0
+
l
4
·
0
-
0
+
l
5
·
1
-
1
+
l
6
·
1
-
0
+
l
7
·
1
-
0
≤
-
1for the two legal markings p
2
+
p
3
+
p
4 and p
5
+
p
6
+
p
7 in M
L
∗, respectively. After simplifying the two constraints, we have(11)
l
3
+
l
4
-
l
5
≤
-
1
,
-
l
2
+
l
6
+
l
7
≤
-
1
.Two variables are introduced f
2 and f
3 to represent whether I
1 forbids F
B
M
2
=
p
3
+
p
5 and F
B
M
3
=
p
2
+
p
6, respectively. Therefore, we have the two constraints: that is, l
2
·
(
0
-
1
)
+
l
3
·
(
1
-
0
)
+
l
4
·
(
0
-
0
)
+
l
5
·
(
1
-
1
)
+
l
6
·
(
0
-
0
)
+
l
7
·
(
0
-
0
)
≥
-
Q
·
(
1
-
f
2
) and l
2
·
(
1
-
1
)
+
l
3
·
(
0
-
0
)
+
l
4
·
(
0
-
0
)
+
l
5
·
(
0
-
1
)
+
l
6
·
(
1
-
0
)
+
l
7
·
(
0
-
0
)
≥
-
Q
·
(
1
-
f
3
), where Q is a positive integer constant that must be big enough and f
2
=
1 (f
3
=
1) implies that FBM2 (FBM3) is forbidden by I
1 and f
2
=
0 (f
3
=
0) implies that FBM2 (FBM3) cannot be forbidden by I
1. After simplifying the two constraints, we have(12)
-
l
2
+
l
3
≥
-
Q
·
1
-
f
2
,
-
l
5
+
l
6
≥
-
Q
·
1
-
f
3
.Finally, from the above constrains MFFP2 for FBM1 is stated as follows.MFFP2 is(13)
max
⁡
f
=
f
2
+
f
3
subject to
l
3
+
l
4
-
l
5
≤
-
1
-
l
2
+
l
6
+
l
7
≤
-
1
-
l
2
+
l
3
≥
-
Q
·
1
-
f
2
-
l
5
+
l
6
≥
-
Q
·
1
-
f
3
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
f
k
∈
0,1
,
∀
k
∈
2,3
.The optimal solution of the above MFFP2 is l
2
=
1, l
3
=
1, l
5
=
2, and f
2
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
1 is designed for I
1
:
μ
2
+
μ
3
+
2
μ
5
+
μ
V
S
1
=
2. As a result, we have M
0
A
V
S
1
=
2, V
S
1
∙
=
{
t
3
,
2
t
6
}, and V
S
1
∙
=
t
1
,
2
t
5. FBM1 and FBM2 are prohibited by I
1: that is, F
I
1
=
{
F
B
M
1
,
F
B
M
2
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
{
p
2
+
p
6
}. At the second iteration, the last FBM is considered, that is, FBM3. Let I
2 be the place invariant to prohibit FBM3. First, the coefficients of I
2 should fulfill the reachability conditions: that is,(14)
l
3
+
l
4
-
l
6
≤
-
1
,
-
l
2
+
l
5
+
l
7
≤
-
1
.Since FBM3 is the last marking in M
F
B
M
∗, no other FBMs in the set require to be prohibited by I
2. By solving the above integer linear system, we have a solution with l
2
=
1, l
6
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
2 is designed for I
2
:
μ
2
+
μ
6
+
μ
V
S
2
=
2. As a result, we have M
0
A
(
V
S
2
)
=
1, V
S
2
∙
=
{
t
2
,
t
7
}, and V
S
2
∙
=
{
t
1
,
t
6
}. Only FBM3 is prohibited by I
2: that is, F
I
2
=
{
F
B
M
3
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
∅.Algorithm10 is terminated. Totally, there are two monitors computed for this net. We add the two monitors to the original Petri net model. The controlled system after addition is as shown in Figure 5. Table 5 shows the two required monitors by using Algorithm 10.Table 5
Required monitors using Algorithm10.
i
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
1
t
3
,
2
t
6
t
1
,
2
t
5
2
2
t
2
,
t
7
t
1
,
t
6
1Figure 5
Controlled system of the Petri net in Figure1(b) by Algorithm 10.


## 4.2.1. Maximal Number of Forbidding FBM Problem 1

The Maximal number of Forbidding FBM Problem 1 (MFFP1) is a technique used to design a monitor synthesis for FBMs. This technique used ILPP to obtain the coefficients of the place invariant that prohibit as many FBMs as possible. The MFFP1 is shown in the following mathematical model.MFFP1 is(2)
max
⁡
f
=
∑
k
∈
N
F
B
M
∗
f
k
subject to
∑
i
∈
N
A
l
i
·
M
l
p
i
≤
β
,
∀
M
l
∈
M
L
∗
(3)
∑
i
∈
N
A
l
i
·
M
k
p
i
≥
β
+
1
-
Q
·
1
-
f
k
,
∀
M
k
∈
M
F
B
M
∗
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
I
N
β
∈
1,2
,
…
f
k
∈
0,1
,
∀
k
∈
N
F
B
M
∗
,where M
L
∗ and M
F
B
M
∗ are the minimal covering sets of legal markings and FBMs, respectively. The objective function f is used to maximize the number of FBMs that are forbidden by place invariant. If f
=
0, we have f
k
=
0, for all k
∈
N
F
B
M
∗ (N
F
B
M
∗ is used to denote {
i
∣
M
i
∈
M
F
B
M
∗
}): that is to say, no FBMs in M
F
B
M
∗ can be prohibited by place invariant. In (2), let I be a place invariant, where l
i’s (i
∈
I
N) are the coefficients of I, β is a positive integer variable, and M
l
p
i
(
∀
M
l
∈
M
L
∗
) are the number of tokens in minimal covering set of legal markings.All legal markings should be kept after a monitor is added, implying that every markingM
l
∈
M
L
∗ cannot be forbidden from being reached, and coefficients l
i’s (i
∈
I
N) should satisfy (2) that is called the reachability condition.In (3), Q is a positive integer constant number that must be large enough, M
k
p
i
(
∀
M
k
∈
M
F
B
M
∗
) are the number of tokens in minimal covering set of FBMs, and f
k’s (f
k
∈
{
0,1
}
,
k
=
1,2
,
…) are a set of M
F
B
M
∗ variables. Moreover, in (3), f
k
=
1 implies that M
k is prohibited by I and f
k
=
0 implies that this constraint is redundant and M
k cannot be prohibited by I.Based on the concept of MFFP1, the proposed deadlock prevention algorithm developed in [25] is stated as follows.Algorithm 9 (MFFP1 based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), find the sets of FBMs M
F
B
M and legal markings M
L.
Step
2. Find the minimal covered sets of FBMs M
F
B
M
∗ and legal markings M
L
∗.
Step
3. V
M
≔
∅. /
V
M
∗ is used to indicate the set of monitors to be found. /
∗
Step
4. While {
M
F
B
M
∗
≠
∅
}, do the following.(i)
Design MFFP1.
(ii)
Solve MFFP1. Letl
i’s (i
∈
I
N) and β be the solution if f
∗
≠
0.
Otherwise, exit, as the solution does not exist.
(iii)
Design a place invariantI and a monitor V
S.
(iv)
V
M
≔
V
M
∪
{
V
S
} and M
F
B
M
∗
=
M
F
B
M
∗
-
F
I. /
∗
F
I is covered M
F
B
M
∗
endwhile.
Step
5. Add all monitors in V
M to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
6. Output (N
1
,
M
1).
Step
7. End.For the Petri net model shown in Figure1(b), we have M
F
B
M
∗
=
{
p
2
+
p
5
,
p
3
+
p
5
,
p
2
+
p
6
} and M
L
∗
=
{
p
2
+
p
3
+
p
4
,
p
5
+
p
6
+
p
7
}. Algorithm 9 is considered. At the first iteration, let I
1 be the place invariant to be calculated. I
1 should satisfy (2) for the two legal markings in M
L
∗: that is, l
2
·
1
+
l
3
·
1
+
l
4
·
1
≤
β and l
5
·
1
+
l
6
·
1
+
l
7
·
1
≤
β. Therefore, we have the following two constraints:(4)
l
2
+
l
3
+
l
4
≤
β
,
l
5
+
l
6
+
l
7
≤
β
.We introduce three variables f
1, f
2, and f
3 (f
1
,
f
2
,
f
3
∈
{
0,1
}) to represent whether I
1 forbids F
B
M
1
=
p
2
+
p
5, F
B
M
2
=
p
3
+
p
5, and F
B
M
3
=
p
2
+
p
6, respectively. Therefore, we have the following three constraints: that is,(5)
l
2
+
l
5
≥
β
+
1
-
Q
·
1
-
f
1
,
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
,
l
2
+
l
6
≥
β
+
1
-
Q
·
1
-
f
3
.Finally, MFFP1 is defined as follows.MFFP1 is(6)
max
⁡
f
=
f
1
+
f
2
+
f
3
subject to
l
2
+
l
3
+
l
4
≤
β
l
5
+
l
6
+
l
7
≤
β
l
2
+
l
5
≥
β
+
1
-
Q
·
1
-
f
1
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
l
2
+
l
6
≥
β
+
1
-
Q
·
1
-
f
3
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
β
∈
1,2
,
…
f
k
∈
0,1
,
∀
k
∈
1,2
,
3
.The optimal solution of the above MFFP1 is l
2
=
2, l
5
=
1, l
6
=
1, β
=
2, f
1
=
1, and f
3
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
1 is designed for I
1
:
2
μ
2
+
μ
5
+
μ
6
+
μ
V
S
1
=
2. As a result, we have M
0
A
(
V
S
1
)
=
β
=
2, V
S
1
∙
=
{
2
t
2
,
t
7
}, and V
S
1
∙
=
{
2
t
1
,
t
5
}. FBM1 and FBM3 are prohibited by I
1: that is, F
I
1
=
{
F
B
M
1
,
F
B
M
3
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
F
B
M
3
=
{
p
3
+
p
5
}.At the next iteration, letI
2 place invariant be calculated. The new MFFP1 can be easily obtained by eliminating constraints that related to FBM1 and FBM3 from the first MFFP1. Therefore, the new MFFP1 is stated as follows.MFFP1 is(7)
max
⁡
f
=
f
2
subject to
l
2
+
l
3
+
l
4
≤
β
l
5
+
l
6
+
l
7
≤
β
l
3
+
l
5
≥
β
+
1
-
Q
·
1
-
f
2
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
β
∈
1,2
,
…
f
2
∈
0,1
.The optimal solution of the above MFFP1 is l
3
=
1, l
5
=
1, β
=
1, and f
2
=
1 and all the remaining variables are equal to zero. Then, a monitor V
S
2 is designed for I
2
:
μ
3
+
μ
5
+
μ
V
S
2
=
1. As a result, we have M
0
A
(
V
S
2
)
=
β
=
1, V
S
1
∙
=
{
t
3
,
t
6
}, and V
S
1
∙
=
{
t
2
,
t
5
}. Only FBM2 is prohibited by I
2: that is, F
I
2
=
{
F
B
M
2
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
2: that is, M
F
B
M
∗
=
∅.Algorithm9 is terminated. Totally, there are two monitors computed for this net. Adding the two monitors to the original Petri net model, the controlled system after addition is as shown in Figure 4. Table 4 shows the two required monitors by using Algorithm 9.Table 4
Required monitors using Algorithm9.
i
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
1
2
t
2
,
t
7
2
t
1
,
t
5
2
2
t
3
,
t
6
t
2
,
t
5
1Figure 4
Controlled system of the Petri net in Figure1(b) by Algorithm 9.


## 4.2.2. Maximal Number of Forbidding FBM Problem 2

The Maximal number of Forbidding FBM Problem 1 has been modified to improve its efficiency and its number of variables and constraints are slightly reduced. The modified technique is called a Maximal number of Forbidding FBM Problem 2 (MFFP2). The MFFP1 is shown in the following mathematical model.MFFP2 is(8)
max
⁡
f
=
∑
k
∈
N
F
B
M
∗
,
k
≠
j
f
k
subject to
∑
i
∈
N
A
l
i
·
M
l
p
i
-
M
j
p
i
≤
-
1
,
∀
M
l
∈
M
L
∗
∑
i
∈
N
A
l
i
·
M
k
p
i
-
M
j
p
i
≥
-
Q
·
1
-
f
k
,
∀
M
k
∈
M
F
B
M
∗
,
k
≠
j
(9)
l
i
∈
0,1
,
2
,
…
.
,
∀
i
∈
I
N
f
k
∈
0,1
,
∀
k
∈
N
F
B
M
∗
,
k
≠
j
.The objective function is maximizing f the number of FBMs that are prohibited by place invariant. If no solution has been obtained from MFFP2 for an FBM, then there are not any FBMs in M
F
B
M
∗ that can be forbidden by that place invariant.In (8), l
i’s (i
∈
I
N) are the coefficients of I, M
l
p
i
(
∀
M
l
∈
M
L
∗
) are the number of tokens in minimal covering set of legal markings, and M
j
p
i are the number of tokens in selected F
B
M
j. In (9), Q is a positive integer constant number that must be large enough, M
k
p
i
(
∀
M
k
∈
M
F
B
M
∗
) are the number of tokens in minimal covering set of FBMs, and f
k’s (f
k
∈
{
0,1
}
,
k
=
1,2
,
…) are a set of M
F
B
M
∗ variables. In (9), f
k
=
1 implies that M
k is prohibited by I and f
k
=
0 implies that this constraint is redundant and M
k cannot be prohibited by I.Based on the concept of MFFP2, the proposed deadlock prevention algorithm developed in [25] is stated as follows.Algorithm 10 (MFFP2 based policy).
Input. Petri net model (N
,
M
0) of an AMS, where N
=
(
P
0
∪
P
A
∪
P
R
,
T
,
F
,
W
).
Step
1. For a given Petri net (N
,
M
0), find the sets of FBMs M
F
B
M and legal markings M
L.
Step
2. Find the minimal covered sets of FBMs M
F
B
M
∗ and legal markings M
L
∗.
Step
3. V
M
≔
∅. /
∗
V
M is used to indicate the set of monitors to be found. /
∗
Step
4. While {
M
F
B
M
∗
≠
∅
}, do the following.(i)
Design MFF2.
(ii)
Solve MFFP2. Letl
i’s (i
∈
N
A) and β be the solution if f
∗
≠
0. Otherwise, exit, as the solution does not exist.
(iii)
Design a place invariantI and a monitor V
S
V
M
≔
V
M
∪
{
V
S
} and M
F
B
M
∗
=
M
F
B
M
∗
-
F
I. /
∗
F
I is covered M
F
B
M
∗
endwhile.
Step
5. Add all monitors in V
M to (N
,
M
0) and the resulting net is denoted by (N
1
,
M
1).
Step
6. Output (N
1
,
M
1).
Step
7. End.Consider the Petri net model shown in Figure1(b) by Algorithm 10. At the first iteration, F
B
M
1
=
p
2
+
p
5 is chosen. Let I
1 be the place invariant to prohibit FBM1, whose coefficients are l
i’s (i
∈
{
2,3
,
4,5
,
6,7
}). I
1 should satisfy (8) that is called the reachability condition and does not prohibit any marking in M
L
∗. Therefore, I
1 should satisfy two constraints:(10)
l
2
·
1
-
1
+
l
3
·
1
-
0
+
l
4
·
1
-
0
+
l
5
·
0
-
1
+
l
6
·
0
-
0
+
l
7
·
0
-
0
≤
-
1
,
l
2
·
0
-
1
+
l
3
·
0
-
0
+
l
4
·
0
-
0
+
l
5
·
1
-
1
+
l
6
·
1
-
0
+
l
7
·
1
-
0
≤
-
1for the two legal markings p
2
+
p
3
+
p
4 and p
5
+
p
6
+
p
7 in M
L
∗, respectively. After simplifying the two constraints, we have(11)
l
3
+
l
4
-
l
5
≤
-
1
,
-
l
2
+
l
6
+
l
7
≤
-
1
.Two variables are introduced f
2 and f
3 to represent whether I
1 forbids F
B
M
2
=
p
3
+
p
5 and F
B
M
3
=
p
2
+
p
6, respectively. Therefore, we have the two constraints: that is, l
2
·
(
0
-
1
)
+
l
3
·
(
1
-
0
)
+
l
4
·
(
0
-
0
)
+
l
5
·
(
1
-
1
)
+
l
6
·
(
0
-
0
)
+
l
7
·
(
0
-
0
)
≥
-
Q
·
(
1
-
f
2
) and l
2
·
(
1
-
1
)
+
l
3
·
(
0
-
0
)
+
l
4
·
(
0
-
0
)
+
l
5
·
(
0
-
1
)
+
l
6
·
(
1
-
0
)
+
l
7
·
(
0
-
0
)
≥
-
Q
·
(
1
-
f
3
), where Q is a positive integer constant that must be big enough and f
2
=
1 (f
3
=
1) implies that FBM2 (FBM3) is forbidden by I
1 and f
2
=
0 (f
3
=
0) implies that FBM2 (FBM3) cannot be forbidden by I
1. After simplifying the two constraints, we have(12)
-
l
2
+
l
3
≥
-
Q
·
1
-
f
2
,
-
l
5
+
l
6
≥
-
Q
·
1
-
f
3
.Finally, from the above constrains MFFP2 for FBM1 is stated as follows.MFFP2 is(13)
max
⁡
f
=
f
2
+
f
3
subject to
l
3
+
l
4
-
l
5
≤
-
1
-
l
2
+
l
6
+
l
7
≤
-
1
-
l
2
+
l
3
≥
-
Q
·
1
-
f
2
-
l
5
+
l
6
≥
-
Q
·
1
-
f
3
l
i
∈
0,1
,
2
,
…
,
∀
i
∈
2,3
,
4,5
,
6,7
f
k
∈
0,1
,
∀
k
∈
2,3
.The optimal solution of the above MFFP2 is l
2
=
1, l
3
=
1, l
5
=
2, and f
2
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
1 is designed for I
1
:
μ
2
+
μ
3
+
2
μ
5
+
μ
V
S
1
=
2. As a result, we have M
0
A
V
S
1
=
2, V
S
1
∙
=
{
t
3
,
2
t
6
}, and V
S
1
∙
=
t
1
,
2
t
5. FBM1 and FBM2 are prohibited by I
1: that is, F
I
1
=
{
F
B
M
1
,
F
B
M
2
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
{
p
2
+
p
6
}. At the second iteration, the last FBM is considered, that is, FBM3. Let I
2 be the place invariant to prohibit FBM3. First, the coefficients of I
2 should fulfill the reachability conditions: that is,(14)
l
3
+
l
4
-
l
6
≤
-
1
,
-
l
2
+
l
5
+
l
7
≤
-
1
.Since FBM3 is the last marking in M
F
B
M
∗, no other FBMs in the set require to be prohibited by I
2. By solving the above integer linear system, we have a solution with l
2
=
1, l
6
=
1, and all the remaining variables are equal to zero. Then, a monitor V
S
2 is designed for I
2
:
μ
2
+
μ
6
+
μ
V
S
2
=
2. As a result, we have M
0
A
(
V
S
2
)
=
1, V
S
2
∙
=
{
t
2
,
t
7
}, and V
S
2
∙
=
{
t
1
,
t
6
}. Only FBM3 is prohibited by I
2: that is, F
I
2
=
{
F
B
M
3
}. Therefore, we have M
F
B
M
∗
≔
M
F
B
M
∗
-
F
I
1: that is, M
F
B
M
∗
=
∅.Algorithm10 is terminated. Totally, there are two monitors computed for this net. We add the two monitors to the original Petri net model. The controlled system after addition is as shown in Figure 5. Table 5 shows the two required monitors by using Algorithm 10.Table 5
Required monitors using Algorithm10.
i
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
1
t
3
,
2
t
6
t
1
,
2
t
5
2
2
t
2
,
t
7
t
1
,
t
6
1Figure 5
Controlled system of the Petri net in Figure1(b) by Algorithm 10.


## 5. Case Studies

This section presents four case studies and the applications of the proposed applied algorithms.(a) The production sequence of the first AMS case study is shown in Figure6(a). It consists of two robots (R1 and R2; each one can hold a part at a time) and five machines (Ml, M2, M3, M4, and M5; each one can process one part at a time). There are three loading buffers I1–3 and three unloading buffers O1–3. Three types of parts are considered in the system: PA, PB, and PC. The model of Petri net for this case study is shown in Figure 6(b).Figure 6
(a) Production sequence and (b) Petri net model of case study 1.
(a)
(b)(b) The production sequence of the second AMS case study is shown in Figure7(a) and several studies have been done in this case study (see Elzpeleta et al. [13] and Chen et al. [25]). The system consists of three robots (Rl, R2, and R3; each one can hold a part at a time) and four machines (Ml, M2, M3, and M4; each machine can process two parts at a time). There are three loading buffers I1–3 and three unloading buffers O1–3. Three types of parts are considered in the system: PA, PB, and PC. The model of Petri net for this case study is shown in Figure 7(b).Figure 7
(a) Production sequence and (b) Petri net model of case study 2.
(a)
(b)(c) Next, the production sequence of the third AMS case study is shown in Figure8(a). The cell consists of two robots (R1 and R2; each one can hold a part at a time) and four machines (M1, M2, and M3; each machine can process a part at a time; M4 can process two products at a time) and, for loading and unloading the cell, two loading buffers (I1 and I2) and two unloading buffers (O1 and O2). Two types of parts are considered in the cell: PA and PB. The model of Petri net for this case study is illustrated in Figure 8(b).Figure 8
(a) Production sequence and (b) Petri net model of case study 3.
(a)
(b)(d) Finally, the production sequence of the fourth AMS case study is shown in Figure9(a) and several studies have been achieved in this case study (see Uzam [9], Chen et al. [25], Piroddi et al. [26], and Piroddi et al. [27]). The system is composed of two robots (R1 and R2; each robot can hold a part at a time) and four machines (M1, M2, M3, and M4; each machine can process one part at a time). There are two loading buffers (I1 and I2) and two unloading buffers (O1 and O2). PA and PB are considered in the system. The model of Petri net for this case study is shown in Figure 9(b).Figure 9
(a) Production sequence and (b) Petri net model of case study 4.
(a)
(b)The main parameters of all case studies are presented in Table6 such as number of places, number of transitions, set partition, SMS, dependent siphons, elementary siphons, reachable markings, FBMs, legal markings, M
F
B
M
∗, and M
L
∗. Table 7 illustrates the supervisor performance of applied algorithms for all case studies with respect to the numbers of monitors, arcs, and reachable states.Table 6
Main parameters of all case studies.
Parameter
Case study
1
2
3
4
Number of  places
26
26
20
19
Number of  transitions
20
20
16
14
Set partition
P
0
=
{
p
1
,
p
25
,
p
26
}
P
R
=
{
p
18
–
p
24
}
P
A
=
{
p
2
,
…
,
p
17
}
P
0
=
{
p
1
,
p
10
,
p
14
}
P
R
=
{
p
20
,
…
,
p
26
}
P
A
=
{
p
2
,
…
,
p
4
,
p
6
,
…
,
p
13
,
p
15
,
…
,
p
19
}
P
0
=
{
p
1
,
p
20
}
P
R
=
{
p
14
,
…
,
p
19
}
P
A
=
{
p
2
,
…
,
p
13
}
P
0
=
{
p
1
,
p
19
}
P
R
=
{
p
13
,
…
,
p
18
}
P
A
=
{
p
2
,
…
,
p
12
}
SMS
11
18
12
5
Dependent siphons
6
9
7
2
Elementary siphons
5
9
5
3
Reachable markings
1492
26750
836
282
FBMs
388
4211
156
54
Legal markings
1072
21581
656
205
M
FBM
∗
9
34
7
8
M
L
∗
92
393
56
26Table 7
Supervisor performance of applied algorithms for all case studies.
Case study
Parameter
Algorithm2
Algorithm8
Algorithm9
Algorithm10
1
Monitors number
11
5
3
3
Arcs number
66
23
14
31
Reachable states number
1072
1072
1072
1072
2
Monitors number
18
9
6
6
Arcs number
106
50
45
59
Reachable states number
6287
6287
21581
21581
3
Monitors number
12
5
4
4
Arcs number
61
25
21
21
Reachable states number
436
489
656
656
4
Monitors number
5
3
2
2
Arcs number
21
13
15
12
Reachable states number
182
205
205
205From Table7, Algorithms 9 and 10 obtain fewer numbers of monitors than Algorithms 2 and 8 for all case studies while Algorithm 9 provides less or equal number of arcs than the other algorithms in case studies 1, 2, and 3. In case study 4, Algorithm 10 obtains less number of arcs than the other algorithms. As for the reachable states, all algorithms provide the same number of reachable states in case study 1, which is 1072 while both Algorithms 2 and 8 have the same number of reachable states, which is 6287 in case study 2. Moreover, in case study 2, both Algorithms 9 and 10 provide the same number of reachable states, which is 21581. Moreover, in case study 3, both Algorithms 9 and 10 outperform Algorithms 2 and 8 in number of reachable states, which have 656 reachable states. Finally, in case study 4, Algorithms 8, 9, and 10 provide better reachable states than Algorithm 2, which is 205. The required monitors using applied algorithms for all case studied are shown in Tables 8, 9, 10, and 11.Table 8
Required monitors using applied algorithms for case study 1.
Algorithm
i
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i)
Algorithm2
1
S
1
t
5
,
t
11
,
t
18
,
t
19
t
1, t
7, t
13
6
2
S
2
t
5
,
t
11
,
t
15
,
t
18
t
1, t
7, t
13, t
16
5
3
S
3
t
5
,
t
11
,
t
15
t
1, t
9, t
13
4
4
S
4
t
3
,
t
9
,
t
18
,
t
19
t
1, t
7, t
15
3
5
S
5
t
5
,
t
11
,
t
18
,
t
19
t
3, t
7, t
13
5
6
S
6
t
5
,
t
11
,
t
15
,
t
18
t
3, t
7,  t
13, t
16
4
7
S
7
t
5
,
t
11
,
t
15
t
3, t
9, t
13
3
8
S
8
t
9
,
t
18
,
t
19
t
7, t
15
2
9
S
9
t
3
,
t
9
,
t
18
t
1, t
7, t
16
2
10
S
10
t
3
t
1
1
11
S
11
t
9
,
t
18
t
7,  t
16
1
Algorithm8
1
S
3
t
5
,
t
11
,
t
15
t
1, t
9, t
13
4
2
S
7
t
5
,
t
11
,
t
15
t
3, t
9, t
13
3
3
S
8
t
9
,
t
18
,
t
19
t
7, t
15
2
4
S
10
t
3
t
1
1
5
S
11
t
9
,
t
18
t
7,  t
16
1
Algorithm9
1
t
5
,
t
11
,
t
15
t
3, t
9, t
13
3
2
2
t
9
,
t
19
,
2
t
18
2t
7,  t
15,  t
16
3
3
t
3
t
1
1
Algorithm10
1
t
5
,
5
t
10
,
t
11
,
6
t
18
,
3
t
19
t
4,  6t
7,  t
14,  2t
15,  3t
16
11
2
t
2
,
11
t
4
,
t
5
,
t
8
,
t
10
,
t
11
,
4
t
14
,
t
15
,
t
16
,
t
17
11t
1,  2t
3,  t
7,  2t
9,  6t
13
20
3
t
5
,
t
11
,
t
15
t
4,  t
9,  t
13
3Table 9
Required monitors using applied algorithms for case study 2.
Algorithm
i
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
Algorithm2
1
S
1
t
5
,
t
10
,
t
13
,
t
19
t
1
,
t
11
,
t
15
10
2
S
2
t
5
,
t
10
,
t
13
,
t
18
t
3
,
t
7
,
t
11
,
t
15
7
3
S
3
t
5
,
t
10
,
t
13
,
t
17
t
3
,
t
8
,
t
11
,
t
15
5
4
S
4
t
2
,
t
10
,
t
16
t
9
,
t
15
2
5
S
5
t
4
,
t
9
,
t
13
,
t
19
t
1
,
t
11
,
t
16
9
6
S
6
t
4
,
t
9
,
t
13
,
t
18
t
3
,
t
7
,
t
11
,
t
16
6
7
S
7
t
4
,
t
9
,
t
13
,
t
17
t
3
,
t
8
,
t
11
,
t
16
4
8
S
8
t
4
,
t
8
,
t
13
,
t
19
t
1
,
t
11
,
t
17
7
9
S
9
t
4
,
t
8
,
t
13
,
t
18
t
3
,
t
7
,
t
11
,
t
17
4
10
S
10
t
4
,
t
7
,
t
13
t
3
,
t
11
2
11
S
11
t
3
,
t
10
,
t
19
t
1
,
t
15
8
12
S
12
t
2
,
t
10
,
t
18
t
7
,
t
15
5
13
S
13
t
2
,
t
10
,
t
17
t
8
,
t
15
3
14
S
14
t
3
,
t
8
,
t
19
t
1
,
t
17
5
15
S
15
t
2
,
t
8
,
t
18
t
7
,
t
17
2
16
S
16
t
3
,
t
9
,
t
19
t
1
,
t
15
7
17
S
17
t
2
,
t
9
,
t
18
t
7
,
t
16
4
18
S
18
t
2
,
t
9
,
t
17
t
8
,
t
16
2
Algorithm8
1
S
1
t
5
,
t
10
,
t
13
,
t
19
t
1
,
t
11
,
t
15
10
2
S
3
t
5
,
t
10
,
t
13
,
t
17
t
3
,
t
8
,
t
11
,
t
15
5
3
S
4
t
2
,
t
10
,
t
16
t
9
,
t
15
1
4
S
10
t
4
,
t
7
,
t
13
t
3
,
t
11
2
5
S
11
t
3
,
t
10
,
t
19
t
1
,
t
15
8
6
S
14
t
3
,
t
8
,
t
19
t
1
,
t
17
5
7
S
15
t
2
,
t
8
,
t
18
t
7
,
t
17
1
8
S
17
t
2
,
t
9
,
t
18
t
7
,
t
16
4
9
S
18
t
2
,
t
9
,
t
17
t
8
,
t
16
1
Algorithm9
1
17
t
5
,
50
t
10
,
15
t
13
,
49
t
17
,
2
t
19
3
t
1
,
14
t
3
,
44
t
8
,
3
t
9
,
15
t
11
,
50
t
15
,
t
18
196
2
t
5
,
24
t
8
,
3
t
10
,
t
13
,
18
t
18
t
3
,
27
t
7
,
t
11
,
6
t
15
,
3
t
16
,
9
t
17
71
3
6
t
3
,
t
5
,
5
t
8
,
t
9
,
6
t
19
6
t
1
,
t
4
,
5
t
15
,
4
t
17
,
t
18
34
4
t
4
,
t
13
t
3
,
t
11
2
5
t
9
,
t
17
t
8
,
t
16
2
6
t
10
,
t
16
t
9
,
t
15
2
Algorithm10
1
9
t
5
,
50
t
8
,
25
t
10
,
8
t
13
,
74
t
17
,
t
19
2
t
1
,
7
t
3
,
73
t
7
,
8
t
11
,
50
t
15
,
25
t
16
196
2
7
t
5
,
20
t
9
,
19
t
10
,
6
t
13
,
39
t
17
,
t
19
t
1
,
6
t
3
,
38
t
8
,
6
t
11
,
20
t
15
,
19
t
16
,
t
18
71
3
7
t
5
,
t
8
,
27
t
10
,
6
t
13
,
19
t
16
,
8
t
17
,
t
19
t
1
,
6
t
3
,
27
t
9
,
6
t
11
,
27
t
15
,
t
18
34
4
t
4
,
t
13
t
3
,
t
11
2
5
6
t
3
,
t
5
,
23
t
8
,
t
10
,
18
t
18
,
5
t
19
6
t
1
,
t
4
,
17
t
7
,
t
9
,
t
15
,
22
t
17
2
6
t
3
,
t
7
,
t
19
t
1
,
t
17
2Table 10
Required monitors using applied algorithms for case study 3.
Algorithm
i
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
Algorithm2
1
S
1
t
7
,
t
14
,
t
15
t
1
,
t
9
6
2
S
2
t
6
,
t
14
,
t
15
t
1
,
t
9
5
3
S
3
t
7
,
t
11
,
t
14
t
1
,
t
9
,
t
12
5
4
S
4
t
6
,
t
11
,
t
14
t
1
,
t
9
,
t
12
4
5
S
5
t
4
,
t
5
,
t
14
,
t
15
t
1
,
t
9
3
6
S
6
t
4
,
t
5
,
t
14
t
1
,
t
12
2
7
S
7
t
7
,
t
14
,
t
15
t
1
,
t
9
5
8
S
8
t
7
,
t
11
t
1
,
t
9
3
9
S
9
t
7
,
t
10
t
6
,
t
9
2
10
S
10
t
6
,
t
14
,
t
15
t
1
,
t
9
4
11
S
11
t
6
,
t
11
t
4
,
t
5
,
t
9
2
12
S
12
t
4
,
t
14
,
t
15
t
2
,
t
11
2
Algorithm8
1
S
5
t
4
,
t
5
,
t
14
,
t
15
t
1
,
t
9
3
2
S
6
t
4
,
t
5
,
t
14
t
1
,
t
12
2
3
S
9
t
7
,
t
10
t
6
,
t
9
2
4
S
11
t
6
,
t
11
t
4
,
t
5
,
t
9
2
5
S
12
t
4
,
t
14
,
t
15
t
2
,
t
11
2
Algorithm9
1
t
4
,
t
14
,
t
15
t
2
,
t
11
2
2
t
6
,
t
14
t
1
,
t
12
2
3
2
t
7
,
t
10
,
t
11
t
4
,
t
5
,
t
6
,
2
t
9
5
4
t
6
,
t
11
t
4
,
t
5
,
t
10
2
Algorithm10
1
t
4
,
t
5
,
t
14
t
1
,
t
12
2
2
t
6
,
t
7
,
2
t
11
2
t
4
,
2
t
5
,
t
9
,
t
10
5
3
t
4
,
t
14
,
t
15
t
2
,
t
11
2
4
t
7
,
t
10
t
6
,
t
9
2Table 11
Required monitors using applied algorithms for case study 4.
Algorithm
i
Siphon
•
V
S
i
V
S
i
•
M
o
A
(
V
S
i
)
Algorithm2
1
S
1
t
7
,
t
13
t
1
,
t
9
5
2
S
2
t
4
,
t
5
,
t
13
t
1
,
t
11
2
3
S
3
t
3
,
t
7
,
t
13
t
1
,
t
9
4
4
S
4
t
7
,
t
11
t
1
,
t
9
3
5
S
5
t
4
,
t
13
t
2
,
t
11
1
Algorithm8
1
S
2
t
4
,
t
5
,
t
13
t
1
,
t
11
2
2
S
4
t
7
,
t
11
t
1
,
t
9
3
3
S
5
t
4
,
t
13
t
2
,
t
11
1
Algorithm9
1
3
t
4
,
5
t
6
,
t
12,
7
t
13
4
t
1
,
4
t
2
,
t
5,
t
9
,
7
t
11
14
2
2
t
7
,
3
t
11
t
1
,
t
2
,
t
5
,
3
t
9
9
Algorithm10
1
t
4
,
2
t
4
,
2
t
13
t
1
,
t
12
,
2
t
11
3
2
2
t
7
,
3
t
11
t
1
,
t
2
,
t
5
,
3
t
9
9


## 6. Computational Results and Analysis

This section presents that the computational results and analysis of the applied methods are conducted for four AMSs case studies. All cases have been modeled using MATLAB software. The simulation is done for 24 time units. After running and simulating the case studies, the results of MATLAB simulation in terms of the utilization resources and throughput can be summarized as follows. For case study 1, Figures10 and 11 show the resources utilization and throughput of case study 1, respectively. From the figures, it can be found that all applied Algorithms 8, 9, and 10 obtain the same utilization for all resources, while Algorithm 2 obtains utilization better than Algorithms 8, 9, and 10 at M1, M2, M5, and R1, and same utilization at M4 and R2. For the throughput, Algorithm 2 obtains greater produced number of part A and part C than Algorithms 8, 9, and 10. Moreover, Algorithms 8, 9, and 10 provide the same throughput for all part types. For case study 2, Figures 12 and 13 show the resources utilization and throughput of the case study 2, respectively.Figure 10
Utilization of resources for the Petri net model in case study 1.Figure 11
Throughput of the system for the Petri net model in case study 1.Figure 12
Utilization of resources for the Petri net model in case study 2.Figure 13
Throughput of the system for the Petri net model in case study 2.The figures indicate that both applied Algorithms9 and 10 have the same utilization for all resources and have better results than Algorithms 2 and 8 at M1, M2, M4, R1, and R2. Algorithm 2 obtains utilization better than Algorithms 8, 9, and 10 at M3 and R3. For the throughput, Algorithm 2 obtains greater produced number of part C than Algorithms 8, 9, and 10, while Algorithms 9 and 10 have greater produced number of part A than Algorithms 2 and 8. Moreover, Algorithm 8 obtains a greater produced number of part B than Algorithms 2, 9, and 10. For case study 3, Figures 14 and 15 show the resources utilization and throughput of case study 3, respectively. The figures indicate that both applied Algorithms 9 and 10 have the same utilization of all resources and obtain better results than Algorithms 2 and 8 at M1, M3, and R2. Both Algorithms 2 and 8 obtain the same utilization for all resources and provide utilization better than Algorithms 9 and 10 at M2, M4, and R1. For the throughput, Algorithms 2 and 8 have greater produced number of part B than Algorithms 9 and 10, while Algorithms 9 and 10 obtain greater produced number of part A than Algorithms 2 and 8. Finally, for case study 4, Figures 16 and 17 show the resources utilization and throughput of case study 4, respectively. From the figures, it can be found that both applied Algorithms 9 and 10 obtain the same utilization of all resources and obtain better results than Algorithms 2 and 8 at M1, M2, R1, and R2. Both Algorithms 2 and 8 obtain the same utilization of all resources and obtain utilization better than Algorithms 9 and 10 at M3 and M4. For the throughput, Algorithms 9 and 10 obtain greater produced number of parts A and B than Algorithms 2 and 8.Figure 14
Utilization of resources for the Petri net model in case study 3.Figure 15
Throughput of the system for the Petri net model in case study 3.Figure 16
Utilization of resources for the Petri net model in case study 4.Figure 17
Throughput of the system for the Petri net model in case study 4.Based on the above computational results for all case studies, it is shown that four applied deadlock prevention policies may not imply high resource utilization and plant productivity which has been shown theoretically in previous publications, since the utilization of any resource at case studies does not exceed 50% and there are several resources that have utilization less than 20%. Moreover, it is found that the resource utilization and plant productivity are different for case studies by using applied policies. The main reason of the occurrence of this difference is a conflict situation in places. When a control place enables more than one transition at the same time, only one transition can fire. For instance, in case study 1, the number of control places using Algorithm2 are 11 and more than one transition is enabled at the same time; that is, several transitions can be fired. While Algorithm 10 reduces the control places into 3 places and enables more than one transition at the same time, few transitions can be fired compared with Algorithm 2. Therefore, the performance is different for different cases by using applied policies. However, we can introduce the comparison between applied policies based on the above computational results, from the viewpoint of behavior permissiveness. Both Algorithms 9 and 10 can provide better behavioral permissiveness than Algorithms 2 and 8 for small size systems (case studies 3 and 4). For the large systems size (case studies 1 and 2), Algorithm 2 leads to better behavioral permissiveness than the other algorithms. The supervisor performance of applied algorithms such as the number of monitors, arcs, and reachable states as averages values is summarized. Figures 18, 19, and 20 show the summarized supervisor performance of all algorithms. From the figures, both Algorithms 9 and 10 obtain a supervisor with structural complexity and computational complexity compared to Algorithms 2 and 8.Figure 18
Average of monitors for all cases.Figure 19
Average of arcs for all cases.Figure 20
Average of reachable states for all cases.


## 7. Conclusion and Future Work

This paper presents four applied deadlock prevention policies, two and two of which are iterative methods and siphon control methods, respectively. Four applied deadlock control methods are used to design a liveness-enforcing supervisor for four automated manufacturing system case studies. The controlled case studies are modeled and simulated using MATLAB software (Petri net toolbox) to analyze and evaluate the performance of selected methods such as utilization of resources and throughput; the computational results can be summarized as follows.The applied deadlock prevention policies may not imply high resource utilization and plant productivity which has been shown theoretically in previous publications. Moreover, it is found that the resource utilization and plant productivity are different for case studies by using applied policies. The main reason for this difference is a conflict situation in places. When a control place enables more than one transition at the same time, only one transition can fire. For instance, in case study 1, the number of control places using Algorithm2 are 11 and more than one transition is enabled at the same time; that is, several transitions can be fired. While Algorithm 10 reduces the control places into 3 places and enables more than one transition at the same time, few transitions can be fired compared with Algorithm 2. Therefore, the performance is different for different cases by using applied policies. However, for all automated manufacturing systems, with respect to structural complexity and computational complexity, the selected iterative methods can always lead to structurally complicated and computationally expensive liveness-enforcing net supervisors compared to the siphon control methods. From the aspect of behavioral permissiveness, the selected iterative methods can provide better behavioral permissiveness than siphon control methods for small size systems. For large systems size, strict minimal siphons control method leads to better behavioral permissiveness than the other methods.Real-world AMSs can suffer from impacts of unreliable resources (resources with failures) under the supervisory control of deadlocks. Therefore, the need for new effective deadlock control policies based on Petri nets becomes increasingly more important. Thus, the future research direction involves designing new effective deadlock prevention policies for automated manufacturing systems with unreliable resources [8]. Then, a simulation will be used to measure the performance of these policies. Different and complex automated manufacturing systems are required and should be considered as a benchmark for these deadlock prevention policies under a variety of control specifications. Optimal deadlock-free scheduling with high time performance will also be interesting.



---

*Source: 537893-2015-09-16.xml*