Sage Journals: Discover world-class research

Abstract

This article presents an efficient integrated approach on designing a non-blocking supervisor for the most general classes of Petri nets, called G-systems that allow multiple resource acquisitions. This work mainly focuses on developing a deadlock prevention policy with a polynomial computational complexity. First, an extraction algorithm of liveness requirement constraints is presented according to the concept of resource partial orders. By considering the different resource requirements of various processes, monitors are added for the uncontrolled G-system on the basis of those precise linear inequality constraints. Afterward, we explore an iterative control policy by utilizing the traditional mathematical programming method, which can ensure the liveness of the resultant controlled system. Comparing with the existing deadlock control policies reported in the literature, the proposed method can achieve a non-blocking controlled G-system with simple structure and high computational efficiency. Finally, a benchmark G-system example is used to substantiate the efficiency of the new method.

Keywords

Petri net supervisory control resource partial orders mixed integer programming

Introduction

Nowadays, deadlocks can cause the part or the whole stoppage in highly automated manufacturing systems, even leading to catastrophic results. Over the last two decades, a great deal of research has been focused on solving deadlock problems in a flexible manufacturing systems (FMS), receiving an enormous attention from both academic and industrial communities.^1–3 The family of Petri net formalisms is a good choice for a flexible manufacturing system environment and has proven to be very useful in the modeling, analysis, simulation, and control of an FMS.^4–6

Deadlock solution methods under the frame of Petri nets can be divided into three major categories: deadlock detection and recovery,⁷ deadlock avoidance,^8–12 and deadlock prevention.^13–22 The first strategy is an online mechanism, which permits the occurrence of deadlock. If a system enters into a deadlock state, a recovery mechanism must be executed by reallocating the resources such that the deadlock is resolved. Due to the requirement of a large amount of data, the first one is usually used under the instances where deadlock phenomenon is not serious. Deadlock avoidance mainly focuses on keeping the system away from deadlock states. When a resource is allocated to a process, an online control policy at each system state is used to make a correct decision such that the forthcoming state is safe. The main purpose of deadlock prevention is to control requests for resources to ensure that the resultant system can no longer reach deadlock states, which is usually achieved by adding monitors (control places) and directed arcs to its uncontrolled model.²³ By contrast, deadlock prevention for FMS is widely acknowledged as one of the most effective deadlock resolution, leading to a vast stock of results.^{24–28,29,30,31}

The deadlock prevention policies on the basis of structural analysis are typical application of Petri net techniques. Especially, since most deadlock control policies are developed according to the relationship between liveness and siphons,³² the siphon-based methods play a prominent role in the development of liveness-enforcing supervisors (LES).^33–39,49 Unfortunately, a siphon-based control method always suffers from the issues of complicated structure and high computational complexity when designing a controller. To alleviate the problem of structural complexity, Li and Zhou^40–42 pioneer the theory of elementary siphons, which provide a full-blown avenue for designing a structurally simple supervisor. However, the computational complexity of supervisor designed by elementary siphons theory remains high since the complete siphon enumeration cannot be avoided. The computational efforts for a supervisor based on elementary siphons are lowered by utilizing the traditional MIP (mixed integer programming)-based deadlock detection method.³³ Based on the MIP method, the iterative deadlock prevention policies are explored in our previous work ^43,44 for generalized Petri nets. Those MIP-based approaches to a large extent reduce the computational cost to design an LES. However, it is not surprising that the solvent of MIP problem is still NP-hard in theory. Therefore, how to lower the computational complexity of supervisor has been an interesting and significant problem in both practice and theory.

In order to develop a computationally efficient deadlock control policy, a deadlock avoidance policy of polynomial complexity is proposed in Park.⁴⁵ Motivated by the seminar work in Park⁴⁵ and Zhao et al.,⁴⁴ an extraction method of liveness control specifications is first expounded for the most general class of Petri nets in the literature, called G-systems. The proposed method aims to achieve the reasonable resource configuration among parallel execution and competing processes according to the liveness requirements. The main contribution of this algorithm lies in the fact that its computational complexity is polynomial and potentially redundant constraints are eliminated. By combining the concept of resource partial orders and MIP-based method, we propose an iterative method to design a non-blocking supervisor with precise monitors added at each iteration. A case study indicates that the proposed policy can usually generate a structurally compact supervisor with more permissive behavior.

The rest of the article is organized as follows. Section “LICs extraction method for G-systems” establishes a method of computing linear inequality constraints (LICs) for G-systems with respect to the concept of resource partial orders. Section “Deadlock control policy based on MIP method” develops an iterative control method for G-systems by combining the MIP-based deadlock detection method with the results provided in section “LICs extraction method for G-systems.” A typical G-system example is illustrated in section “The application of the proposed policy” to validate the results in sections “LICs extraction method for G-systems” and “Deadlock control policy based on MIP method,” and some comparison and discussion among different deadlock control policies for G-systems are made subsequently. While section “Conclusion” concludes the article and suggests some directions for future research. Some fundamental concepts of Petri nets and G-systems used throughout this article are listed in Appendices 1 and 2.

LICs extraction method for G-systems

This work considers deadlock problems for a class of manufacturing-oriented Petri nets, namely, G-systems first proposed in Barkaoui et al.⁴⁶ For more details, the preliminaries of Petri nets and the definitions of G-systems can refer to the previous work in Zhao and Hou.⁴⁷

First, this section presents an extraction algorithm of LICs under given resource partial orders for a G-system configuration. As known, a G-system net with concurrent processes may fall into permanent blocking since the circular wait of shared resources may occur among multiple processes. In order to eliminate deadlocks, it is necessary to prevent the occurrence of problematic states effectively. To achieve this, a deadlock avoidance policy in polynomial complexity is proposed in Park ⁴⁵ for an S⁴PR in terms of resource requirement partial orders. Inspired by the method in Park,⁴⁵ we first extend this notion to G-systems that is a more general class of Petri nets than S⁴PR. After that, the redundant LICs are removed by the proposed algorithm, and the liveness of the controlled system would not be changed due to their removal. It means that a more compact structure of the resultant supervisor can be obtained by the proposed method.

Under different resource requirement partial orders, the supervisor should appropriately restrict the system resources allocation of various requested operations such that the presence of illegal states can be permanently prevented. The proposed method aims to design a non-blocking controlled system by properly supervising resources allocation among multiple concurrent processes. Consequently, the resulting controlled system is the synchronous synthesis of a G-system net model and its supervisor via shared transitions, which is defined as follows.

Definition 1

Let $(N_{1}, M_{1})$ and $(N_{2}, M_{2})$ be two G-system net models with $N_{i} = (i_{i} \cup o_{i} \cup P_{A_{i}} \cup P_{R_{i}}, T_{i}, F_{i}, W_{i}) (i = 1, 2)$ . Their synchronous synthesis net $(N, M)$ resulting from the merge of $(N_{1}, M_{1})$ and $(N_{2}, M_{2})$ , denoted by $N = (N_{1}, M_{1}) \otimes (N_{2}, M_{2}) = (P_{0} \cup P_{A} \cup P_{R}, T, F, W)$ , is defined as follows:

$P_{0} = {i_{1}, i_{2}, o_{1}, o_{2}}, P_{A} = P_{A_{1}} \cup P_{A_{2}},$ and $P_{R} = P_{R_{1}} \cup P_{R_{2}}$ ;

$T = T_{1} \cup T_{2}$ ;

$F = F_{1} \cup F_{2}$ ;

$W (f) = W_{i} (f)$ , if $f \in F_{i}$ , $i = 1, 2$ ;

$\forall p \in i_{1} \cup o_{1} \cup P_{A_{1}} \cup P_{R_{1}}, M (p) = M_{1} (p),$ and $\forall p \in i_{2} \cup o_{2} \cup P_{A_{2}} \cup P_{R_{2}}, M (p) = M_{2} (p)$ .

Definition 2

Let $GS = (N_{S}, M_{S_{0}}, M_{S_{F}})$ be a G-system compounded by n subsystems $G S_{j} = (N_{S_{j}}, M_{S_{0 j}}, M_{S_{Fj}})$ , where $N_{S_{j}} = (P_{0_{j}} \cup P_{A_{j}} \cup P_{R_{j}}, T_{j}, F_{j} \cup F_{R_{j}}, W_{j} \cup W_{R_{j}})$ , and $j \in ℕ_{n}$ . Then,

Let $p_{j, k}$ be an operation place and $J_{j}$ be the set of operation places in $N_{S}$ . $J_{j}$ is called an operation process with predefined partial orders, which is denoted as $J_{j} = {p_{j, k} \in P_{A_{j}} | j \in ℕ_{n}, k \in ℕ_{| P_{A_{j}} |}}$ . The set of operation processes in a G-system is denoted as $J = {J_{j} | j \in ℕ_{n}}$ .

Let r be a resource and $P_{R}$ be the set of all resource places in $N_{S}$ . $\forall r_{i} \in P_{R}$ , a positive integer $C_{r_{i}}$ is called the resource capacity in $r_{i}$ , where $C_{r_{i}} \equiv M_{0} (r_{i}) = \sum_{p \in ∥ I_{r_{i}} ∥} I_{r_{i}} (p) M (p)$ .

Let $o_{j}$ be a sink place in a subsystem $G S_{j} = (N_{S_{j}}, M_{S_{0 j}}, M_{S_{Fj}})$ . $P_{T} = {^{• •} o_{j} | o_{j} \in P_{0_{j}}, j \in ℕ_{n}}$ is called the set of terminal operation places, which represents the end of the processing stage.

Example

Taking the G-system net in Figure 1(a) as an example, we have $i_{1} = p_{8}$ , $o_{1} = p_{9}$ , $i_{2} = p_{13}$ , and $o_{2} = p_{14}$ . The corresponding augmented version is then obtained after two transitions $t_{1}^{*}$ and $t_{2}^{*}$ are added, where ${}^{•}{i_{1}} = {o_{1}}^{•} = {t_{1}^{*}}$ and ${}^{•}{i_{2}} = {o_{2}}^{•} = {t_{2}^{*}}$ , which is shown in Figure 1(b). From the definitions of G-systems in Zhao and Hou,⁴⁷ we have $P_{0} = {p_{8}, p_{9}, p_{13}, p_{14}}$ , $P_{A} = {p_{1} - p_{7}, p_{10} - p_{12}}$ , and $P_{R} = {p_{15} - p_{17}}$ . From Definition 2(1), we have two job types $J_{1}$ and $J_{2}$ with $J_{1} = {p_{1} - p_{7}}$ and $J_{2} = {p_{10}, p_{11}, p_{12}}$ . The net has three resource places $p_{15}$ , $p_{16}$ , and $p_{17}$ , then we have $P_{R} = {p_{15}, p_{16}, p_{17}}$ , $C_{p_{15}} = 2$ , $C_{p_{16}} = 2$ , and $C_{p_{17}} = 3$ due to Definition 2(2). From Definition 2(3), $P_{T} = {p_{4}, p_{12}}$ . $◇$

Figure 1.

(a) A G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ and (b) the augmented G-system net $(N_{S}^{*}, M_{S_{0}}, M_{S_{F}})$ .

Definition 3

Let $r_{i}$ be a resource place in a G-system $GS = (N_{S}, M_{S_{0}}, M_{S_{F}})$ . The holder of $r_{i}$ is defined as $H (r_{i}) = I_{r_{i}} - r_{i}$ , where $I_{r_{i}}$ and $r_{i}$ are two multisets.

A resource place in a net system is modeled with a singleton place whose token capacity represents the ability of processing raw parts concurrently.

Example

From the definition of a G-system, there are four minimal P-semiflows that can be computed in Figure 1(b) shown as below, which is associated with resource places $p_{15} - p_{17}$ , respectively

I_{p_{15}} = 2 p_{1} + p_{12} + p_{15}, H (p_{15}) = 2 p_{1} + p_{12}

I_{p_{15}}^{'} = 2 p_{5} + p_{12} + p_{15}, H {(p_{15})}^{'} = 2 p_{5} + p_{12}, M_{0} (p_{15}) = 2

I_{p_{16}} = p_{2} + p_{6} + p_{11} + p_{16}, H (p_{16}) = p_{2} + p_{6} + p_{11}, M_{0} (p_{16}) = 2

I_{p_{17}} = p_{3} + p_{4} + p_{7} + p_{10} + p_{17}, H (p_{17}) = p_{3} + p_{4} + p_{7} + p_{10}, M_{0} (p_{17}) = 3

Definition 4

Let $p_{j, k}$ be an operation place of $J_{j}$ in $GS = (N_{S}, M_{S_{0}}, M_{S_{F}})$ . The resource allocation requirement of $p_{j, k}$ is defined as a $| P_{R} |$ -dimensional vector $a_{p_{j, k}} = (a_{p_{j, k}} [r_{1}], \dots, a_{p_{j, k}} [r_{| P_{R} |} {])}^{T}$ . $a_{p_{j, k}} [r_{i}] = I_{r_{i}} (p_{j, k})$ indicates how many units of $r_{i}$ are needed in the operation $p_{j, k}$ .

Example

Take the net shown in Figure 1(b) as an example. For operation place $p_{4}$ , $p_{4}$ is only included in P-semiflow $I_{p_{17}}$ , that is to say, resource place $p_{17}$ can support $p_{4}$ , then $a_{p_{4}} = (0, 0, 1)^{T}$ can be derived. Similarly, the net has two job types $J_{1} = {p_{1} - p_{7}}$ and $J_{2} = {p_{10} - p_{12}}$ . From above minimal P-semiflows, $\forall p_{i} \in P_{A}$ , its related resources requirements $a_{p_{i}}$ in $J_{1}$ and $J_{2}$ can be computed as shown in Table 1.

Table 1.

The resources requirements in P_A for the net system in Figure 1(b).

$P_{R}$	$a_{p_{1}}$	$a_{p_{2}}$	$a_{p_{3}}$	$a_{p_{4}}$	$a_{p_{5}}$	$a_{p_{6}}$	$a_{p_{7}}$	$a_{p_{10}}$	$a_{p_{11}}$	$a_{p_{12}}$
$p_{15}$	2	0	0	0	2	0	0	0	0	1
$p_{16}$	0	1	0	0	0	1	0	0	1	0
$p_{17}$	0	0	1	1	0	0	1	1	0	0

By considering a G-system under different resource requirements, monitors should be added to the net system in order to prevent the controlled system entering into the forbidden markings, the policy under resource partial orders is presented as follows.

Definition 5

Let $o_{i} \equiv O (r_{i})$ , $O : P_{R} \to ℕ_{| P_{R} |}$ be any partial order imposed on the resource places set $P_{R}$ . Given an operation place $p_{j, k} \in P_{A_{j}}$ , where $j \in ℕ_{n}, k \in ℕ_{| P_{A_{j}} |}$ , let

ρ_{p_{j, k}}^{m a x} = (\begin{array}{l} m a x {o_{i} | a_{p_{j, k}} [i] > 0, i \in ℕ_{| P_{R} |}} & i f \exists r \in P_{R}, p_{j, k} \in ∥ H (r) ∥ \\ 0 & o t h e r w i s e \end{array}

(1)

and

ρ_{p_{j, k}}^{\min} = (\begin{array}{l} m a x {o_{i} | a_{p_{j, k}} [i] > 0 i \in ℕ_{| P_{R} |}} & i f \exists r \in P_{R}, p_{j, k} \in ∥ H (r) ∥ \\ 0 & o t h e r w i s e \end{array}

(2)

Let $L_{p_{j, k}} = {q | q \in {p_{j, k}}^{• •} \cap P_{A_{j}} \land ρ_{q}^{\max} = mi n_{v \in {p_{j, k}}^{• •} \cap P_{A_{j}}} ρ_{v}^{\max}}$ , by convention, $L_{p_{j, k}} = \emptyset$ if ${p_{j, k}}^{• •} \cap P_{0} \neq \emptyset$ . Then,

The neighborhood set $N_{p_{j, k}}$ of $p_{j, k} \in P_{A_{j}}$ is defined recursively by the following equation

N_{p_{j, k}} = {p_{j, k}} \cup {q | q \in \cup_{v \in L_{p_{j, k}}} N_{v} \land ρ_{p_{j, k}}^{\min} \leq ρ_{q}^{\max}}

$\forall p_{j, k} \in P_{A_{j}}$ , the adjusted resource requirement ${\hat{a}}_{p_{j, k}}$ is defined as an non-negative $| P_{R} |$ -dimensional vector due to $O (r_{i})$ , which is computed as below

{\hat{a}}_{p_{j, k}} [i] = {\begin{matrix} \max {a_{q} [i] | q \in N_{p_{j, k}}} \\ 0 \end{matrix} \begin{matrix} if o_{i} \geq ρ_{p_{j, k}}^{\min}, i \in ℕ_{| P_{R} |} \\ otherwise \end{matrix}

(3)

Definition 5 formalizes the liveness control specification of resources requirements, which can be expressed by a set of generalized mutual exclusion constraints (GMECs). The neighborhood set $N_{p_{j, k}}$ of an operation place $p_{j, k}$ is defined at Definition 5(1), which indicates that the maximum resource order of the resources used by an operation q in $N_{p_{j, k}}$ is no less than the minimum one used by $p_{j, k}$ . Under a certain resources partial order, Definition 5(2) presents a formalized method on computing the adjusted resource requirements of operation places, which indicates that the appropriate adjustment of system resources should be carried out such that each operation in its neighborhood set are properly allocated.

Example

Consider the net shown in Figure 1(b) as an example and assume that the given resource partial order is $o_{1} = 2$ , $o_{2} = 3$ , and $o_{3} = 1$ . From Definition 5, $\forall p_{j, k} \in P_{A}$ , its related neighborhood sets can be stepwise computed beginning with the terminal operation places. Taking $p_{4}$ as an example, $p_{4}$ uses resource $p_{17}$ . Due to $O (p_{17}) = 1$ , we have $ρ_{p_{4}}^{\max} = 1$ , $ρ_{p_{4}}^{\min} = 1$ . In addition, since $p_{4}$ is a terminal operation place, $L_{p_{4}} = \emptyset$ by $p_{4}^{• •} \cap P_{0} \neq \emptyset$ . From Definition 5, $N_{p_{4}} = {p_{4}}$ is obtained. Table 2 depicts the results of the neighborhood sets and its related parameters in detail.

Table 2.

The computation of the neighborhood sets for the net system in Figure 1(b).

$p_{j, k}$	$ρ_{p_{j, k}}^{\max}$	$ρ_{p_{j, k}}^{\min}$	$L_{p_{j, k}}$	$N_{p_{j, k}}$
$p_{1}$	2	2	$p_{2}$ , $p_{6}$	$p_{1}$ , $p_{2}$ , $p_{6}$
$p_{2}$	3	3	$p_{3}$	$p_{2}$
$p_{3}$	1	1	$p_{4}$	$p_{3}$ , $p_{4}$
$p_{4}$	1	1	$\emptyset$	$p_{4}$
$p_{5}$	2	2	$p_{2}$ , $p_{6}$	$p_{2}$ , $p_{5}$ , $p_{6}$
$p_{6}$	3	3	$p_{7}$	$p_{6}$
$p_{7}$	1	1	$p_{4}$	$p_{4}$ , $p_{7}$
$p_{10}$	1	1	$p_{11}$	$p_{10}, p_{11}$
$p_{11}$	3	3	$p_{12}$	$p_{11}$
$p_{12}$	2	2	$\emptyset$	$p_{12}$

By utilizing Definition 5, the adjusted resource allocation requirements can be derived as shown in Table 3.

Table 3.

The adjusted resources requirements in $P_{A}$ for the net system in Figure 1(b).

$P_{R}$	${\hat{a}}_{p_{1}}$	${\hat{a}}_{p_{2}}$	${\hat{a}}_{p_{3}}$	${\hat{a}}_{p_{4}}$	${\hat{a}}_{p_{5}}$	${\hat{a}}_{p_{6}}$	${\hat{a}}_{p_{7}}$	${\hat{a}}_{p_{10}}$	${\hat{a}}_{p_{11}}$	${\hat{a}}_{p_{12}}$
$p_{15}$	2	0	0	0	2	0	0	0	0	1
$p_{16}$	1	1	0	0	1	1	0	1	1	0
$p_{17}$	0	0	1	1	0	0	1	1	0	0

In order to prevent the system entering into deadlock states, another set of linear LICs should be computed according to the adjusted resource allocation requirements ${\hat{a}}_{p_{j, k}}$ . Consequently, a set of linear LICs is implemented by additional monitors $V_{R} = {V_{1}, V_{2}, \dots, V_{m}}$ . It implies that an LES can be obtained after the resource utilization of all operation places is supervised.

Definition 6

Let ${\hat{a}}_{p_{i}} (i \in ℕ_{| P_{A} |})$ be the adjusted resource allocation requirement associated with $p_{i}$ and ${\hat{A}}_{p} = [{\hat{a}}_{p_{1}} | {\hat{a}}_{p_{2}} | \dots | {\hat{a}}_{p_{n}}] (n = | P_{A} |)$ be its matrix form in GS. Let $M_{P}$ be the restriction vector on M with respect to operation places and $f_{p}$ be the resource capacity vector, where $f_{p} [j] = C_{r_{j}}$ , $j \in ℕ_{| P_{R} |}$ . Then, the liveness control specification is defined as a set of LICs in the matrix form as follows

{\hat{A}}_{p} \cdot M_{P} \leq f_{p}

(4)

Example

From Definition 6, the following results are obtained for the net in Figure 1(b)

(\begin{matrix} 2 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \end{matrix}) \cdot (\begin{matrix} M (p_{1}) \\ M (p_{2}) \\ M (p_{3}) \\ M (p_{4}) \\ M (p_{5}) \\ M (p_{6}) \\ M (p_{7}) \\ M (p_{10}) \\ M (p_{11}) \\ M (p_{12}) \end{matrix}) \leq (\begin{matrix} 2 \\ 2 \\ 3 \end{matrix}) ◇

$\forall p \in P_{0} \cup P_{R}$ , ${\hat{A}}_{p}$ and $M_{P}$ are extended by adding zero column vectors, which leads to an augmented matrix $\hat{A}$ and marking $M \in R (N, M_{0})$ . As a sequel, the liveness requirement constraints are rewritten as

\hat{A} \cdot M \leq f_{p}

(5)

In Figure 1(b), when assuming that the places are ordered in the incidence matrix according to the sequence $〈 p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}, p_{7}, p_{10}, p_{11}, p_{12}, p_{8}, p_{9}, p_{13}, p_{14}, p_{15}, p_{16}, p_{17} 〉$ , the following specific form depicts the liveness requirement represented by $\hat{A} \cdot M \leq f_{p}$

(\begin{matrix} \begin{matrix} 2 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 1 & | \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & | \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & | \end{matrix} & \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \end{matrix}) \cdot (\begin{matrix} M (p_{1}) \\ M (p_{2}) \\ M (p_{3}) \\ M (p_{4}) \\ M (p_{5}) \\ M (p_{6}) \\ M (p_{7}) \\ M (p_{10}) \\ M (p_{11}) \\ M (p_{12}) \\ - - - - \\ M (p_{8}) \\ M (p_{9}) \\ M (p_{13}) \\ M (p_{14}) \\ M (p_{15}) \\ M (p_{16}) \\ M (p_{17}) \end{matrix}) \leq (\begin{matrix} 2 \\ 2 \\ 3 \end{matrix})

Definition 7

Let $(N, M_{0})$ be a Petri net, it is deadlock-free if $\forall M \in R (N, M_{0})$ , $\exists t \in T$ such that $M [t 〉$ holds.⁴⁷ $(N, M_{0})$ is live if $\forall t \in T$ , t is live at $M_{0}$ .

Definition 7 is widely used in the deadlock control and analysis area of Petri nets. Note that a live Petri net guarantees deadlock-freedom no matter what firing sequence is chosen but the converse is not true. Therefore, deadlock resolution methods mainly aim to obtain an LES for a Petri net model prone to deadlocks.

Definition 8

A G-system GS is well-formed if there exists an initial marking $M_{S_{0}}$ such that $\forall M \in R (N_{S}, M_{S_{0}})$ , $M_{S_{F}} \in R (N_{S}, M)$ , where $M_{S_{0}}$ and $M_{S_{F}}$ denote the initial marking and the final marking of $N_{S}$ , respectively.

Definition 9

A G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ is non-blocking if $\forall M \in R (N_{S}, M_{S_{0}})$ , there exists a sequence of transitions $σ$ such that $M [σ 〉 M_{S_{F}}$ holds.⁴⁷

Remark 1

Note that the concepts of liveness and non-blockingness are totally different. The concept of non-blockingness is originally defined based on the theory of automata and formal language. Actually, in the frame of Petri nets, there is no standard definition of non-blockingness of deadlock control in the existing literature. In the article, Definition 9 first gives its formal definition for the most general class of Petri nets, called G-system. Note that the non-blockingness is an important property of a controlled G-system, which indicates that the system can always reach a final marking from any reachable state. In particular, the net structure of a G-system GS is different from that of other generalized Petri net classes. Since a G-task GT is circuit-free, that is, it is inadmissible to have loops in a G-task. As a result, a G-system GS is not strongly connected. To analyze the liveness of the given G-system, its corresponding augmented G-system $G S^{*}$ is then defined by adding transition $t^{*}$ , which leads to a strongly connected G-system. Thus, it can be concluded that a controlled G-system is non-blocking if $\forall M \in R (N_{S}, M_{S_{0}})$ , the controlled system can always reach the final marking $M_{S_{F}}$ , which indicates that all resources are released and all job parts are completed and stored in sink places. By considering the definition of an augmented net, if a well-formed G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ is non-blocking, its augmented G-system is live since every G-task $(N_{j}, M_{0_{j}}, M_{F_{j}})$ in GS is augmented by adding $t_{j}^{*}$ such that $N_{j}^{*}$ with $o_{j}^{•} =^{•} i_{j} = {t_{j}^{*}}$ and $W (o_{j}, t_{j}^{*}) = W (t_{j}^{*}, i_{j}) = n$ is strongly connected.⁴⁷ In a word, the liveness of an augmented G-system is equivalent to the non-blockingness of its original well-formed G-system GS.

Proposition 1

Let $GS = (N_{S}, M_{S_{0}}, M_{S_{F}})$ be a G-system and ${\hat{A}}_{p} \cdot M_{P} \leq f_{p}$ be a set of inequality constraints on liveness specification under a resource partial order $O (\cdot)$ . The resulting net $G S^{c} = (N_{S}^{c}, M_{S_{0}}^{c}, M_{S_{F}}^{c})$ is non-blocking if the set of GMECs $({\hat{A}}_{p}, f_{p})$ are imposed on a G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ such that $R (N_{S}^{c}, M_{S_{0}}^{c}) \subseteq ℳ ({\hat{A}}_{p}, f_{p})$ , where $ℳ ({\hat{A}}_{p}, f_{p}) = {M_{P} \in ℕ_{| P_{A} |} | {\hat{A}}_{p} \cdot M_{P} \leq f_{p}}$ .

Proof

From Definition 5(2), the policy-imposed constraints on the system operations are expressed by the requirements that no resource is over-allocated with respect to the adjusted resource allocation represented by ${\hat{a}}_{p} [i]$ . Meanwhile, from equation (4), the legal markings set is defined as $ℳ ({\hat{A}}_{p}, f_{p}) = {M_{P} \in ℕ_{| P_{A} |} | {\hat{A}}_{p} \cdot M_{P} \leq f_{p}}$ . By contrast, the illegal markings are also called forbidden markings, and all additional monitors can achieve the control specification. Since monitors minimally restrict the behavior of $(N_{S}^{c}, M_{S_{0}}^{c})$ , and in a certain sense, the forbidden markings could not be generated due to those constraints, thus $R (N_{S}^{c}, M_{S_{0}}^{c}) \subseteq ℳ ({\hat{A}}_{p}, f_{p})$ holds. Consequently, it can be concluded that the deadlock-freeness of the resultant controlled net can be ensured. In other words, $\forall M \in R (N_{S}^{c}, M_{S_{0}}^{c})$ , there is a sequence of transitions $σ = t_{0} t_{1} \dots t_{n}$ such that $M [σ 〉 M_{S_{F}}$ holds. From Definition 9, it can be concluded that the resulting controlled system $G S^{c} = (N_{S}^{c}, M_{S_{0}}^{c}, M_{S_{F}}^{c})$ is non-blocking. $◇$

After the liveness requirement constraints are established, the resource requirements of operations are then reallocated according to those constraints. Next, the precise LICs extraction algorithm is summarized as follows.

Algorithm 1. LICs extraction for a G-system $GS = (N_{S}, M_{S_{0}}, M_{S_{F}})$
Input: a G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ with $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$
Output: $C$ , the precise LICs
1: $P_{R} : = {r_{1}, r_{2}, \dots, r_{m}}$ , $O : = {o_{1}, o_{2}, \dots, o_{m}}$ , $J_{j} : = {J_{1}, J_{2}, \dots, J_{n}}$ , $C : = \emptyset$ .
2: for ( $i = 1$ to m) do
3: $\forall r_{i} \in P_{R}$ , compute minimal P-semiflows $I_{r_{i}}$ .
4: end for
5: for ( $j = 1$ to n) do
6: $\forall p_{j, k} \in P_{A} \cap J_{j}$ , compute resource requirements $a_{p_{j, k}}$ due to all minimal P-semiflow $I_{r_{i}}$
7: end for
8: $i : = 1$ , $j : = 1$ .
9: while $(j \leq n)$ do
10: $\forall p_{j, k} \in P_{A} \cap J_{j}$ , compute $ρ_{p_{j, k}}^{\max}$ , $ρ_{p_{j, k}}^{\min}$ , $L_{p_{j, k}}$ , and $N_{p_{j, k}}$ under a partial order O from Definition 5;
11: $\forall p_{j, k} \in P_{A} \cap J_{j}$ , compute adjusted resource requirements ${\hat{a}}_{p_{j, k}}$ due to Definition 5;
12: $j : = j + 1$ .
13: end while
14: while $(i \leq m)$ do
15: $c_{i} : = \sum_{p_{j, k} \in P_{A}} {\hat{a}}_{p_{j, k}} [i] M (p_{j, k}) \leq M_{0} (r_{i})$
16: $A : = {\hat{A}}_{p} [i, \cdot] - A_{p} [i, \cdot]$
17: if $(A \neq 0)$ then
18: $C : = C \cup c_{i}$
19: $i : = i + 1$
20: end if
21: end while
22: return $C$

Remark 2

Based on the concept of resource partial orders, Algorithm 1 presents an extraction method of the precise LICs. Note that the key point of Algorithm 1 is to derive the adjusted resource requirements. According to the definition of partial orders, the priority of resources occupied or released by operation places may be different. Therefore, it is crucial to properly adjust the resource allocation when considering the certain resource partial orders. Furthermore, it is worth noting that some variables in Algorithm 1 can be derived by utilizing some domestically developed softwares, such as INA and MIPA, which are useful in shortening the computation time of LICs and supervisors synthesis.

Let $C = {c_{i} | i \in ℕ_{n}, n \leq m}$ be the set of LICs computed by Algorithm 1 in terms of $P_{R} = {r_{1}, r_{2}, \dots, r_{m}}$ . The liveness requirements in a GS can be expressed by a set of GMECs.

For more details, all original and adjusted resources requirements are represented by conjunction sets of GMECs, $A_{p} \cdot M_{P} \leq f_{p}$ and ${\hat{A}}_{p} \cdot M_{P} \leq f_{p}$ , respectively. Since $\sum_{p \in P_{A}} a_{p} [i] p + r_{i}$ and $\sum_{p \in P_{A}} {\hat{a}}_{p} [i] p + r_{i}$ are P-semiflows related to $r_{i}$ in the net model, when the adjusted resource requirement vector ${\hat{A}}_{p} [i, \cdot]$ equals to the initial resource requirement vector $A_{p} [i, \cdot]$ with respect to resource place $r_{i}$ , that is, ${\hat{A}}_{p} [i, \cdot] = A_{p} [i, \cdot]$ , which means that $\sum_{p \in P_{A}} a_{p} [i] p + r_{i}$ and $\sum_{p \in P_{A}} {\hat{a}}_{p} [i] p + r_{i}$ are the same P-semiflows, the inequality constraint ${\hat{A}}_{p} \cdot M_{P} \leq f_{p}$ is certainly redundant. That is to say, resource place $r_{i}$ has already met the liveness requirement of the corresponding operation under the given resource partial order. It indicates that the removal of redundant constraints does not change the performance of controlled systems.

Example

Taking the net in Figure 1(b) as an example, the LICs $c_{1} - c_{3}$ can be derived by Algorithm 1 in order to properly allocate three resource requirements for each job operation as below

{\begin{matrix} c_{1} : 2 M (p_{1}) + 2 M (p_{5}) + M (p_{12}) \leq 2 \\ c_{2} : M (p_{1}) + M (p_{2}) + M (p_{5}) + M (p_{6}) + M (p_{11}) + M (p_{12}) \leq 2 \\ c_{3} : M (p_{3}) + M (p_{4}) + M (p_{7}) + M (p_{10}) \leq 3 \end{matrix}

Subsequently, the potential redundancy of those constraints can be further systematically removed by Algorithm 1 such that a structurally simple LES can be derived. For more details, we have ${\hat{A}}_{p} [1, \cdot] = A_{p} [1, \cdot] = (2, 0, 0, 0, 2, 0, 0, 0, 0, 1)^{T}$ , ${\hat{A}}_{p} [3, \cdot] = A_{p} [3, \cdot] = (0, 0, 1, 1, 0, 0, 1, 1, 0, 0)^{T}$ , ${\hat{A}}_{p} [2, \cdot] = (1, 1, 0, 0, 1, 1, 0, 1, 1, 0)^{T}$ , and $A_{p} [2, \cdot] = (0, 1, 0, 0, 0, 1, 0, 0, 1, 0)^{T}$ . Thus, it can be concluded that $c_{1}$ and $c_{3}$ are redundant. Consequently, the set of precise inequality constraints $C = {c_{2}}$ is derived. $◇$

Theorem 1

Given a G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ , where $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$ , the time complexity of Algorithm 1 is polynomial.

Proof

Give any G-system, LICs can be derived by Algorithm 1 in polynomial time, whose complexity is established from the following statements: (1) $\forall p_{j, k} \in J_{j}$ , the computation of $ρ_{p_{j, k}}^{\max}$ and $ρ_{p_{j, k}}^{\min}$ requires $O (| P_{A_{j}} | \cdot | P_{R} |)$ times; (2) the calculation of $N_{p_{j, k}}$ requires $1 + 2 + \dots + | P_{A_{j}} | \Rightarrow O (| P_{A_{j}} |^{2})$ times at most; (3) the computation of ${\hat{a}}_{p_{j, k}}$ requires $O (| P_{R} | \cdot | P_{A_{j}} |^{2})$ times. That is to say, the complexity of $F_{V} : (V_{R} \times T) \cup (T \times V_{R}) \to ℕ$ is less than $O (n \cdot | P_{R} | \cdot \max_{j = 1}^{n} | P_{A_{j}} |^{2})$ , where n is the number of job types. $◇$

Deadlock control policy based on MIP method

Although the liveness control specification is represented by a set of GMECs with respect to the ordering imposed on the resource set for any G-system net model, it is still a point solution to the underlying control problem. As is well known, deadlock occurs directly due to insufficiently marked siphons in generalized Petri nets. Thus, siphon-based control method requires the siphon enumeration, which is a task of nonpolynomial complexity as the number of net places increases. Fortunately, for the class of structurally bounded generalized net, the work in Chu and Xie³³ presents an additional sufficient condition of potential liveness that takes the convenient form of an MIP formulation of polynomial size with respect to the net elements shown as follows. It indicates that the aforementioned liveness sufficiency condition essentially provides an automatic correctness verification tool of deadlock control policy.

Definition 10

Let $(N, M_{0})$ be a structurally bounded net, and $B (p)$ be the structural bound of place p in N. Let $v_{p} \geq (M (p) - W (p, t) + 1) / B (p)$ , where $B (p) = \max {M (p) | M = M_{0} + [N] Y, M \geq 0, Y \geq 0}$ .

By considering the traditional linear programming method shown in Chu and Xie,³³ a siphon S in a structurally bounded net can be determined by solving an MIP problem based on two binary variables $v_{p}$ and $z_{t}$ , which are denoted as the following Notation.

Notation 1

$\forall p \in P$ , $\forall t \in T$ , $\forall W (p, t) > 0$ , the expression $v_{p} = 1 {p \notin S}$ (resp. $z_{t} = 1 {t \notin S^{•}}$ ) is equivalent to the condition that place p (resp. transition t) can be removed at each iteration of siphon extraction.

Due to Notation 1, it is shown that any p with $v_{p} = 1$ and any t with $z_{t} = 1$ can be removed from the net. Since S is a siphon, it indicates that $\forall t \in p^{•}$ , $v_{p} = 0$ implies $z_{t} = 0$ and $\forall p \in t^{•}$ , $z_{t} = 1$ implies the truth of $v_{p} = 1$ . Then, the following theorem is obtained.

Theorem 2

Let $(N_{S}, M_{S_{0}})$ be a structurally bounded G-system.⁴⁴ $\forall M \in R (N_{S}, M_{S_{0}})$ , the maximal deadly marked siphon S under M is determined by

S = {p_{i} | p_{i} \in P \land v_{p_{i}} = 0, i = 1, 2, \dots, | P |}

where $v_{p}, p \in P$ is obtained through the following MIP formulation

G^{MIP} (M) = \min \sum_{p \in P} v_{p}

s.t.

z_{t} \geq \sum_{p \in^{•} t} v_{p} - |^{•} t | + 1, \forall t \in T

(6)

v_{p} \geq z_{t}, \forall (t, p) \in F

(7)

v_{p} \geq (M (p) - W (p, t) + 1) / B (p), \forall p \in P, \forall W (p, t) > 0

(8)

M = M_{0} + [N] Y

(9)

v_{p}, z_{t} \in {0, 1}, \forall p \in P, \forall t \in T

(10)

M \geq 0, Y \geq 0

(11)

Proof

In order to understand the formulation of this theorem, notice that equations (6) and (9) imply that any fireable transition t at M has $z_{t} = 1$ . Furthermore, equation (7) implies that any place $p \in t^{•}$ for some t with $z_{t} = 1$ has $v_{p} = 1$ . Finally, the result that no additional place p (resp., transition t) has $v_{p} = 1$ (resp., $z_{t} = 1$ ), it is guaranteed by the specification of the objective function in the above formulation. Conversely, for any solution of the linear system, let $S = {p \in P | v_{p} = 0}$ . For any $t \in^{•} S$ , from equation (7), $z_{t} = 0$ can be obtained. From equation (6), we have $\sum_{p \in^{•} t} v_{p} \leq |^{•} t | - 1$ , which implies that $v_{p} = 0$ , that is, $p \in S$ , at least one place $p \in^{•} t$ . As a result, there exists a maximal deadly siphon S if $G^{MIP} (M) < | P |$ . $◇$

Theorem 3

Let $(N_{S}, M_{S_{0}}, M_{S_{F}})$ be a G-system, where $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$ . $\forall M \in R (N_{S}, M_{S_{0}})$ , if the optimal solution of the MIP formulation in Theorem 2 satisfies $G^{MIP} (M) = | P_{0} | + | P_{A} | + | P_{R} |$ , it can be concluded that $N_{S}$ will have no potential deadlock.

Proof

If $G^{MIP} (M) = | P_{0} | + | P_{A} | + | P_{R} |$ holds, there is no maximal deadly marked siphon in $N_{S}$ due to Theorem 2. Obviously, it can be concluded that the net has no deadlock state. $◇$

Given a bounded Petri net prone to deadlocks, the MIP-based method can provide an efficient and rapid deadlock detection approach to compute the deadly marked siphons. Next, monitors should be added to those insufficiently marked siphons such that the liveness of the controlled systems is ensured. In the frame of Petri nets, the LES consists of a set of monitors and a set of transitions, which is a subset of the set of transitions in the plant net model.

Definition 11

Let $(N_{S}, M_{S_{0}}, M_{S_{F}})$ be a G-system. $(N_{V}, M_{V_{0}}, M_{V_{F}})$ with $N_{V} = (V_{R}, T_{V}, F_{V}, W_{V})$ is the net supervisor of $(N_{S}, M_{S_{0}}, M_{S_{F}})$ if it satisfies:

Let $V_{R} = {V_{i} | i \in | C |}$ be the set of monitors, where a bijective mapping between $V_{R}$ and $| C |$ exists. $\forall V_{i} \in V_{R}$ , $∥ I_{V_{i}} ∥ \cap V_{R} = {V_{i}}$ , $∥ I_{V_{i}} ∥ \cap P_{R} = \emptyset$ , $∥ I_{V_{i}} ∥ \cap P_{0} = \emptyset$ , $∥ I_{V_{i}} ∥ \cap P_{A} \neq \emptyset$ ;

Additional monitors satisfy the following conditions: $\forall t \in T_{V}$ , let ${p} =^{•} t \cap (P_{A} \cup P_{0})$ , ${q} = t^{•} \cap (P_{A} \cup P_{0})$ , and $F_{V} = F_{V}^{1} \cup F_{V}^{2}$ , where

(a) $F_{V}^{1} = {(V_{i}, t) | {\hat{a}}_{q} [i] - {\hat{a}}_{p} [i] > 0}$ , $W (V_{i}, t) = {\hat{a}}_{q} [i] - {\hat{a}}_{p} [i]$ ;

(b) $F_{V}^{2} = {(t, V_{i}) | {\hat{a}}_{q} [i] - {\hat{a}}_{p} [i] < 0}$ , $W (t, V_{i}) = {\hat{a}}_{p} [i] - {\hat{a}}_{q} [i]$ ;

(c)if ${\hat{a}}_{q} [i] = {\hat{a}}_{p} [i]$ , $W (V_{i}, t) = W (t, V_{i}) = 0$ .

$M_{V_{0}}$ is defined as follows: (a) $\forall p \in P_{0} \cup P_{A} \cup P_{R}$ , $M_{V_{0}} (p) = M_{S_{0}} (p)$ and (b) $\forall V_{i} \in V_{R}$ , $M_{V_{0}} (V_{i}) = M_{S_{0}} (r_{i}) \equiv C_{r_{i}}$ .

Proposition 2

Let $(N_{S}, M_{S_{0}}, M_{S_{F}})$ be a G-system, where $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$ . Then, $\forall r_{i} \in P_{R}$ , a minimal P-semiflow $I_{r_{i}}$ can be derived such that $∥ I_{r_{i}} ∥ \cap P_{R} = {r_{i}}$ . Let $V_{i}$ be a monitor for inequality constraint $c_{i}$ in $(N_{V}, M_{V_{0}}, M_{V_{F}})$ . Then, $V_{i}$ is added to $(N_{S}, M_{S_{0}}, M_{S_{F}})$ by the enforcement that $\forall c_{i} \in C$ , $V_{i} + \sum_{p_{j, k} \in P_{A}} {\hat{a}}_{p_{j, k}} [i] p_{j, k}$ is also a P-semiflow of $N_{V}$ , where $N_{V} = (V_{R}, T_{V}, F_{V}, W_{V})$ .

Proof

Note that permanent blocking may occur in some operations if each process requires further continuation of shared resources currently held by some other processes. To avoid it, the proper resource allocation is needed under any given resource partial order. To achieve it, each additional monitor $V_{i}$ is designed to restrict the resource requirements of operation places in $H (V_{i})$ , where $M_{0} (V_{i}) = C_{r_{i}}$ . From Definition 11, it can be verified that $V_{i} + \sum_{p_{j, k} \in P_{A}} {\hat{a}}_{p_{j, k}} [i] p_{j, k}$ is a P-semiflow of $N_{V}$ . $◇$

The compound of a G-system model and its supervisor is called the controlled G-system, which is the synchronous synthesis net defined as follows.

Definition 12

Let $(N_{S}, M_{S_{0}}, M_{S_{F}})$ with $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$ be a G-system, and $(N_{V}, M_{V_{0}}, M_{V_{F}})$ with $N_{V} = (V_{R}, T_{V}, F_{V}, W_{V})$ be its supervisor, where $T_{V} \subseteq T$ . $(N^{c}, M_{0}^{c}, M_{F}^{c})$ is called the controlled G-system of $(N_{S}, M_{S_{0}}, M_{S_{F}})$ if $(N^{c}, M_{0}^{c}, M_{F}^{c}) = (N_{S}, M_{S_{0}}, M_{S_{F}}) \otimes (N_{V}, M_{V_{0}}, M_{V_{F}})$ .

Corollary 1

Let $(N^{c}, M_{0}^{c}, M_{F}^{c})$ be the controlled G-system of $(N_{S}, M_{S_{0}}, M_{S_{F}})$ , where $N^{c} = (P_{A} \cup P_{0} \cup P_{R} \cup V_{R}, T, F \cup F_{V}, W \cup W_{V})$ . Then, $N^{c}$ is live iff $G^{MIP} (M_{0}^{c}) = | P_{0} | + | P_{A} | + | P_{R} | + | V_{R} |$ , where $V_{R}$ is the set of additional monitors.

Next, we establish an iterative algorithm such that the non-blocking controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ for a G-system can be synthesized.

Algorithm 2. A non-blocking controlled system design for a G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$
Input: a G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ with $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$
Output: the controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$
1: begin;
2: $\forall p \in P_{A}$ , compute the set of LICs $C = {c_{i} \| i \in ℕ_{n}}$ by Algorithm 1.
3: $i : = 1$ , $V_{R} : = \emptyset$ .
4: repeat
5: if $(G^{MIP} (M_{S_{0}}) < \| P_{0} \| + \| P_{A} \| + \| P_{R} \| + \| V_{R} \| and i \leq n)$ then
6: add a monitor $V_{i}$ for $c_{i}$ to $(N, M_{0})$ due to Proposition 2 and Definition 11.
7: $V_{R} : = V_{R} \cup V_{i}$
8: $i : = i + 1$
9: end if
10: until $G^{MIP} (M_{S_{0}}) = \| P_{0} \| + \| P_{A} \| + \| P_{R} \| + \| V_{R} \|$
11: obtain $N^{c} = (P_{A} \cup P_{0} \cup P_{R} \cup V_{R}, T, F \cup F_{V}, W \cup W_{V})$
12: return $(N^{c}, M_{0}^{c}, M_{F}^{c})$
13: end.

Remark 3

By utilizing the MIP-based detection method, Algorithm 2 proposes an iterative policy for designing non-blocking controlled systems. Note that the MIP provides a highly computational efficiency throughout the iterations. Based on place-invariant (PI) control method, a monitor is added to enforce the controllability constraints derived by Algorithm 1 at each step. When the condition in Theorem 3 holds, the iterations would be completed. That is to say, the resultant net system would not generate the deadly marked siphons, which implies the resultant net system is non-blocking. Subsequently, the non-blocking controlled G-system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ can be derived with all necessary monitors.

Example

Considering the net in Figure 1(b) as an example, a monitor $V_{2}$ is added for enforcing the precise constraint $c_{2}$ , where we have ${(V_{2}, t_{1}), (V_{2}, t_{9})} \subseteq F_{V}^{1}$ , and ${(t_{3}, V_{2}), (t_{7}, V_{2}), (t_{11}, V_{2})} \subseteq F_{V}^{2}$ . $\forall F \in F_{V}$ , $W (V_{2}, t) = W (t, V_{2}) = 1$ , and $M_{0}^{c} (V_{2}) = M_{0} (r_{2}) = 2$ . Consequently, the controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ is obtained with $N^{c} = (P_{A} \cup P_{0} \cup P_{R} \cup V_{2}, T, F \cup F_{V}, W \cup W_{V})$ . $◇$

Proposition 3

Algorithm 2 always terminates and its termination gives a non-blocking controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ , where $N^{c} = (P_{A} \cup P_{0} \cup P_{R} \cup V_{R}, T, F \cup F_{V}, W \cup W_{V})$ .

Proof

To properly allocate shared resources, the maximal resource requirements of job operations should be adjusted in terms of a given resource partial order. When an uncontrolled G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ is considered, the set of precise constraints on liveness specifications can be derived according to Algorithm 1, which is usually transformed into the set of GMECs. Furthermore, each monitor is added to achieve the constraint from Algorithm 2, and minimally restricts the permissive behavior of the controlled G-system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ , which indicates that it prevents only transition firings that yield forbidden markings. Meanwhile, each additional monitor $V_{i}$ does not contribute to illegal states in $(N^{c}, M_{0}^{c}, M_{F}^{c})$ , which indicates that the deadlock situations in $(N^{c}, M_{0}^{c}, M_{F}^{c})$ never occur. Consequently, due to Proposition 2 and Corollary 1, the liveness of the resulting G-system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ can be achieved. Due to the special net structure, the liveness of an augmented G-system is equivalent to the non-blockingness of its original well-formed G-system GS, it has been proven in the work.⁴⁸ That is to say, a non-blocking controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ can be obtained by Algorithm 2. $◇$

The computational complexity of the proposed algorithms is analyzed as follows.

Theorem 4

Let $(N_{S}, M_{S_{0}}, M_{S_{F}})$ with $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$ be a G-system and $(N^{c}, M_{0}^{c}, M_{F}^{c})$ with $N^{c} = (P_{0} \cup P_{A} \cup P_{R} \cup {V_{R}}, T, F \cup F_{R} \cup F_{V}, W \cup W_{R} \cup W_{V})$ be its corresponding live controlled system obtained by Algorithm 2. Then, $| V_{R} | \leq | P_{R} |$ , and the imposing restriction is of size $O (| P_{A} | + | P_{R} |)$ at worst.

Proof

From Algorithm 1, it is worth noting that the number of LICs set is no more than that of resource places, that is, $| C | \leq | P_{R} |$ . Based on MIP-based detection method in Algorithm 2, we need at most $| C |$ iterative steps to obtain a live controlled system. Consequently, the number of control places in the controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ is no greater than that of system resources, that is, $| V_{R} | \leq | P_{R} |$ , and the computational complexity is $O (| P_{R} |)$ times. Generally, the number of adjusted operation places is $| P_{A} |$ at most. Therefore, the imposing constraints is of size $O (| P_{A} | + | P_{R} |)$ at worst. $◇$

The application of the proposed policy

A G-system example

Take the augmented G-system in Figure 2 as an illustrative example. Obviously, the given G-system contains three processes $J_{1}$ , $J_{2}$ , and $J_{3}$ with $J_{1} = {p_{1} - p_{7}}$ , $J_{2} = {p_{12} - p_{16}}$ , and $J_{3} = {p_{8} - p_{10}}$ . There are three source places $i_{1}$ $(p_{18})$ , $i_{2}$ $(p_{17})$ , and $i_{3}$ $(p_{11})$ ; three sink places $o_{1}$ $(p_{19})$ , $o_{2}$ $(p_{21})$ , and $o_{3}$ $(p_{20})$ ; and six resource places $P_{R} = {p_{22} - p_{27}}$ with $C_{p_{22}} = 2$ , $C_{p_{23}} = 2$ , $C_{p_{24}} = 2$ , $C_{p_{25}} = 3$ , $C_{p_{26}} = 3$ , and $C_{p_{27}} = 3$ . Furthermore, all minimal P-semiflows with respect to the system resources $p_{22} - p_{27}$ are derived as follows

I_{p 22} = p_{1} + p_{16} + p_{22}; I_{p 22}^{'} = p_{5} + p_{16} + p_{22}; M_{0} (p_{22}) = 2

I_{p 23} = p_{1} + p_{15} + p_{23}; I_{p 23}^{'} = p_{5} + p_{15} + p_{23}; M_{0} (p_{23}) = 2

I_{p 24} = p_{2} + p_{6} + p_{14} + p_{24}; M_{0} (p_{24}) = 2

I_{p 25} = p_{4} + p_{12} + p_{13} + p_{25}; M_{0} (p_{25}) = 3

I_{p 26} = p_{3} + p_{7} + p_{8} + p_{10} + p_{13} + p_{26}; M_{0} (p_{26}) = 3

I_{p 27} = p_{4} + 2 p_{8} + 2 p_{9} + p_{27}, M_{0} (p_{27}) = 3

Figure 2.

An augmented G-system $(N_{S}^{*}, M_{S_{0}}, M_{S_{F}})$ .

Afterwards, Table 4 lists the resource requirements of all operation places due to Definition 4.

Table 4.

The resource requirements in $P_{A}$ for the net system in Figure 2.

$P_{R}$	$a_{p_{1}}$	$a_{p_{2}}$	$a_{p_{3}}$	$a_{p_{4}}$	$a_{p_{5}}$	$a_{p_{6}}$	$a_{p_{7}}$	$a_{p_{8}}$	$a_{p_{9}}$	$a_{p_{10}}$	$a_{p_{12}}$	$a_{p_{13}}$	$a_{p_{14}}$	$a_{p_{15}}$	$a_{p_{16}}$
$p_{22}$	1	0	0	0	1	0	0	0	0	0	0	0	0	0	1
$p_{23}$	1	0	0	0	1	0	0	0	0	0	0	0	0	1	0
$p_{24}$	0	1	0	0	0	1	0	0	0	0	0	0	1	0	0
$p_{25}$	0	0	0	1	0	0	0	0	0	0	1	1	0	0	0
$p_{26}$	0	0	1	0	0	0	1	1	0	1	0	1	0	0	0
$p_{27}$	0	0	0	1	0	0	0	2	2	0	0	0	0	0	0

Consider all processes executed under the resource partial order $o_{p_{22}} = 1$ , $o_{p_{23}} = 2$ , $o_{p_{24}} = 2$ , $o_{p_{25}} = 1$ , $o_{p_{26}} = 3$ , and $o_{p_{27}} = 2$ . First, for job type $J_{1}$ , the following results are obtained:

$ρ_{p_{4}}^{\max} = 2, ρ_{p_{4}}^{\min} = 1, L_{p_{4}} = \emptyset$ by ${(p_{4}^{•})^{•} \cap P_{0}} \neq \emptyset$ and $N_{p_{4}} = {p_{4}}$ ;

$ρ_{p_{3}}^{\max} = 3, ρ_{p_{3}}^{\min} = 3, L_{p_{3}} = {p_{4}}$ and $N_{p_{3}} = {p_{3}}$ ;

$ρ_{p_{2}}^{\max} = 2, ρ_{p_{2}}^{\min} = 2, L_{p_{2}} = {p_{3}}$ and $N_{p_{2}} = {p_{2}, p_{3}}$ ;

$ρ_{p_{1}}^{\max} = 2, ρ_{p_{1}}^{\min} = 1, L_{p_{1}} = {p_{2}, p_{6}}$ and $N_{p_{1}} = {p_{1}, p_{2}, p_{3}, p_{6}, p_{7}}$ ;

$ρ_{p_{7}}^{\max} = 3, ρ_{p_{7}}^{\min} = 3, L_{p_{7}} = {p_{4}}$ and $N_{p_{7}} = {p_{7}}$ ;

$ρ_{p_{6}}^{\max} = 2; ρ_{p_{6}}^{\min} = 2; L_{p 6} = {p_{7}}$ and $N_{p_{6}} = {p_{6}, p_{7}}$ ;

$ρ_{p_{5}}^{\max} = 2; ρ_{p_{5}}^{\min} = 1; L_{p_{5}} = {p_{2}, p_{6}}$ and $N_{p_{5}} = {p_{2}, p_{3}, p_{5}, p_{6}, p_{7}}$ .

For job type $J_{2}$ , we have

$ρ_{p_{16}}^{\max} = 1, ρ_{p_{16}}^{\min} = 1, L_{p_{16}} = \emptyset$ and $N_{p_{16}} = {p_{16}}$ ;

$ρ_{p_{15}}^{\max} = 2, ρ_{p_{15}}^{\min} = 2, L_{p_{15}} = {p_{16}}$ and $N_{p_{15}} = {p_{15}}$ ;

$ρ_{p_{14}}^{\max} = 2, ρ_{p_{14}}^{\min} = 2, L_{p_{14}} = {p_{15}}$ and $N_{p_{14}} = {p_{14}, p_{15}}$ ;

$ρ_{p_{13}}^{\max} = 3, ρ_{p_{13}}^{\min} = 1, L_{p_{13}} = {p_{14}}$ and $N_{p_{13}} = {p_{13}, p_{14}, p_{15}}$ ;

$ρ_{p_{12}}^{\max} = 1, ρ_{p_{12}}^{\min} = 1, L_{p_{12}} = {p_{13}}$ and $N_{p_{12}} = {p_{12}, p_{13}, p_{14}, p_{15}}$ .

For job type $J_{3}$ , we have

$ρ_{p_{10}}^{\max} = 3, ρ_{p_{10}}^{\min} = 3, L_{p_{10}} = \emptyset$ and $N_{p_{10}} = {p_{10}}$ ;

$ρ_{p_{9}}^{\max} = 2, ρ_{p_{9}}^{\min} = 2, L_{p_{9}} = {p_{10}}$ and $N_{p_{9}} = {p_{9}, p_{10}}$ ;

$ρ_{p_{8}}^{\max} = 3, ρ_{p_{8}}^{\min} = 2, L_{p_{8}} = {p_{9}}$ and $N_{p_{8}} = {p_{8}, p_{9}, p_{10}}$ .

Accordingly, the adjusted resource requirements ${\hat{a}}_{p}$ in terms of above partial order are computed as shown in Table 5.

Table 5.

The adjusted resource requirements in $P_{A}$ for the net system in Figure 2.

$P_{R}$	${\hat{a}}_{p_{1}}$	${\hat{a}}_{p_{2}}$	${\hat{a}}_{p_{3}}$	${\hat{a}}_{p_{4}}$	${\hat{a}}_{p_{5}}$	${\hat{a}}_{p_{6}}$	${\hat{a}}_{p_{7}}$	${\hat{a}}_{p_{8}}$	${\hat{a}}_{p_{9}}$	${\hat{a}}_{p_{10}}$	${\hat{a}}_{p_{12}}$	${\hat{a}}_{p_{13}}$	${\hat{a}}_{p_{14}}$	${\hat{a}}_{p_{15}}$	${\hat{a}}_{p_{16}}$
$p_{22}$	1	0	0	0	1	0	0	0	0	0	0	0	0	0	1
$p_{23}$	1	0	0	0	1	0	0	0	0	0	1	1	1	1	0
$p_{24}$	1	1	0	0	1	1	0	0	0	0	1	1	1	0	0
$p_{25}$	0	0	0	1	0	0	0	0	0	0	1	1	0	0	0
$p_{26}$	1	1	1	0	1	1	1	1	1	1	1	1	0	0	0
$p_{27}$	0	0	0	1	0	0	0	2	2	0	0	0	0	0	0

From Definition 5, the new set of LICs is computed and transformed into a matrix form as follows

(\begin{matrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) \cdot M = (\begin{matrix} 2 \\ 2 \\ 2 \\ 3 \\ 3 \\ 3 \end{matrix})

Consequently, three precise control constraints of the liveness requirement are derived as follows

(\begin{matrix} c_{1} : M (p_{1}) + M (p_{5}) + M (p_{12}) + M (p_{13}) + M (p_{14}) + M (p_{15}) \leq 2 \\ c_{2} : M (p_{1}) + M (p_{2}) + M (p_{5}) + M (p_{6}) + M (p_{12}) + M (p_{13}) + M (p_{14}) \leq 2 \\ c_{3} : M (p_{1}) + M (p_{2}) + M (p_{3}) + M (p_{5}) + M (p_{6}) + M (p_{7}) + M (p_{8}) + M (p_{9}) + M (p_{10}) \\ + M (p_{12}) + M (p_{13}) \leq 3 \end{matrix}

As previous results mentioned, each LIC is implemented by a monitor to ensure the liveness of the controlled system. To simplify the control constraints, Algorithm 2 is carried out further to design a structurally simple LES. As a result, it is shown that one monitor is only needed for the net model in Figure 2, whose related results are depicted in Table 6.

Table 6.

Monitors for the net model in Figure 2.

$V_{i}$	${}^{•}{V_{i}}$	$V_{i}^{•}$	$M_{0}^{c} (V_{i})$
$V_{1}$	$t_{2}$ , $t_{6}$ , $t_{17}$	$t_{1}$ , $t_{13}$	2

Comparison study

As is gradually recognized, the existing control policies developed by structural analysis technique are hard to achieve optimal performance in G-systems.^41,42 In order to dissect deeply deadlock control methods in the literature, we review and compare the proposed method with those in Zhao and collegues^41,47 through a typical G-system benchmark shown in Figure 2. It is easy to verify that the original net model has 123,595 reachable states. Among them, there are 123,060 legal markings.

From elementary siphon-based method in Li and Zhao,⁴¹ the net system consists of 13 strict minimal siphons (SMSs), 5 of which are elementary ones. The resultant supervisor including five additional monitors is computed only for elementary siphons, namely $V_{S_{1}}$ , $V_{S_{2}}$ , …, and $V_{S_{5}}$ , as shown in Table 7. Consequently, the resultant G-system contains 53,788 reachable states, which indicates that the non-blocking supervisor designed by the method in Li and Zhao⁴¹ provides 44% (53,788/123,060) of the maximally behavioral permissiveness.

Table 7.

Monitors added for the net system in Figure 2 due to Li and Zhao.⁴¹

$V_{S_{i}}$	${}^{•}{V_{S_{i}}}$	${V_{S_{i}}}^{•}$	$M_{0}^{c} (V_{S_{i}})$
$V_{S_{1}}$	$t_{4}$ , $t_{8}$ , $t_{14}$	$t_{1}$ , $t_{13}$	5
$V_{S_{2}}$	$t_{4}$ , $t_{8}$ , $2 t_{11}$	$t_{1}$ , $2 t_{9}$	5
$V_{S_{3}}$	$2 t_{2}$ , $2 t_{6}$ , $t_{17}$	$2 t_{1}$ , $t_{13}$	5
$V_{S_{4}}$	$t_{2}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{13}$	3
$V_{S_{5}}$	$t_{3}$ , $t_{7}$ , $t_{15}$	$t_{1}$ , $t_{13}$	1

Similarly, the method proposed in Zhao and Hou⁴⁷ is then applied to the net in Figure 2. As a result, three monitors depicted in Table 8 can be computed. It can be verified that the controlled G-system in Zhao and Hou⁴⁷ has 123,060 legal markings, which indicates that the corresponding supervisor affords maximally permissive behavior for the original G-system.

Table 8.

Monitors added for the net system in Figure 2 due to Zhao and Hou.⁴⁷

$V_{S}$	${}^{•}{V_{S_{i}}}$	${V_{S_{i}}}^{•}$	$M_{0}^{c} (V_{S_{i}})$
$V_{S_{1}}$	$t_{4}$ , $t_{8}$ , $t_{14}$	$t_{3}$ , $t_{7}$ , $t_{13}$	5
$V_{S_{2}}$	$t_{4}$ , $t_{8}$ , $2 t_{15}$	$t_{2}$ , $t_{6}$ , $t_{13}$ , $t_{14}$	7
$V_{S_{3}}$	$t_{2}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{15}$	3

As for the proposed method, one monitor $V_{1}$ is only designed as shown in Figure 3. Consequently, there are 88,896 legal markings included in the resulting controlled system. It can be concluded that the non-blocking supervisor offers 72% (88,896/123,060) of the maximally permissive behavior. Generally, three performance indicators served as the assessment criterion of supervisor control. In detail, the performance analysis and comparison among aforementioned deadlock control policies are presented as in Table 9.

Figure 3.

The controlled G-system net $(N^{c}, M_{0}^{c}, M_{F}^{c})$ .

Table 9.

Performance analysis and comparison of non-blocking supervisors.

Performance indicators	The policy in Li and Zhao⁴¹	The policy in Zhao and Hou⁴⁷	The proposed method
No. of reachable states	53,778	123,060	88,896
No. of additional monitors	5	3	1
No. of additional arcs	25	18	5
Computational complexity	Exponential	Exponential	Polynomial

In conclusion, although the concept of elementary siphon can usually lead to structurally simple liveness-enforcing monitor-based supervisors, the number of monitors designed by the proposed method is less than those of Zhao and colleagues.^41,47 Furthermore, the complete siphon enumeration-based methods would run into bottlenecks as the size of net model increases due to the problems of the computational complexity and behavioral permissiveness. By contrast, the method proposed in this article is more appropriate for large-scale systems.

Discussion

From the behavioral permissiveness point of view, the proposed deadlock prevention policy does not provide an optimal controlled system since it reduces the resource utilization to some extent, which indicates that some good states of the net model may be eliminated. On one hand, the behavioral permissiveness of the non-blocking supervisor depended on the selected resource partial orders. Based on the proposed method, the utilization of system resources may be limited due to different resource partial orders. Determining how to find an optimal resource partial ordering has been an interesting yet significant problem from view of the optimal trade-off between structural minimality and permissive behavioral maximality. On the other hand, since all output arcs of a monitor are led to the source transitions of the net system, which limits the number of workpieces being released into and processed by the system. Consequently, the proposed method is in general not optimal, from the behavioral permissiveness standpoint. Therefore, the key point of deriving a supervisor with the best behavioral permissiveness is to optimize the resource utilization and allocation. Furthermore, a designer always hopes to have a set of concise controllability constraints. To obtain a smaller set of monitors, the proposed method presents an MIP-iterative algorithm, which can remove redundant constraints such that the supervisor has more precise structure.

Taking the net in Figure 2 as an example, there are three precise inequality constraints, namely $c_{1} - c_{3}$ derived from Algorithm 1. Actually, $c_{2}$ and $c_{3}$ are still redundant after $V_{1}$ is added for controlling constraint $c_{1}$ . It means that $V_{1}$ is an essential monitor for the supervisor. The corresponding LES has 88,896 reachable states after one iteration. Suppose that in a scenario $c_{2}$ is chosen as the prior iteration, $V_{2}$ is first added for the net with ${}^{•}{V_{2}} = {t_{3}, t_{7}, t_{16}}$ and ${V_{2}}^{•} = {t_{1}, t_{13}}$ . After that, the resulting system is not live, further iteration is needed. If $c_{1}$ is selected, $V_{1}$ is added for the net with ${}^{•}{V_{1}} = {t_{2}, t_{6}, t_{17}}$ and ${V_{1}}^{•} = {t_{1}, t_{13}}$ . After two iterations, the resulting controlled system has 70,049 reachable states with two monitors $V_{1}$ and $V_{2}$ . It means the redundant monitors would restrict the behavioral permissiveness of the resulting net system. The research indicates that the MIP-iterative method may exist redundant monitors with respect to the selected orders of precise inequality constraints. An optimal iterative order should be found such that the LES is as structurally simple and more permissive as possible.

Conclusion

Existing deadlock prevention policies developed by siphons control always face the issues of high computational complexity and structural complexity since siphons enumeration is computationally expensive or impossible if the structural size of a plant model is large. To improve the computational efficiency and structural simplification of supervisors design, this article proposes an MIP-based iterative deadlock prevention policy under resource allocation orders for the most general classes of Petri nets.

Since resource allocation of multiple processes directly affects the dynamic property of a net system, an efficient control method is developed by properly supervising system resource requirements. By utilizing the concept of resource partial order, a set of LICs is computed and designated as the liveness requirements conditions, from which the precise control constraints are extracted by a polynomial algorithm. After that, we establish an MIP-based iterative algorithm to derive a non-blocking supervisor for G-systems. Finally, a case study is shown to demonstrate the proposed policy and used to compare them with the state-of-the-art methods. Followed by the discussion in this article, how to derive the LICs of key resources to design an LES with better performance should be considered in the future.

Footnotes

Appendix 1

Appendix 2

Academic Editor: Tatsushi Nishi

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China under Grant Nos 61563045 and 61104110.

References

Bai

. Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology. IEEE T Syst Man Cyb 2016; 46: 1456–1467.

Huang

Zhou

Zhang

. Speedup techniques for multiobjective integer programs in designing optimal and structurally simple supervisors of AMS. IEEE T Syst Man Cyb 2016, pp.1–12. DOI: 10.1109/TSMC.2016.2587671.

Wang

Wonham

WM.

Dynamic multiple-period reconfiguration of real-time scheduling based on timed DES supervisory control. IEEE T Ind Inform 2016; 12: 101–111.

Huang

Zhou

Zhang

GX.

Synthesis of Petri net supervisors for FMS via redundant constraint elimination. Automatica 2015; 61: 156–163.

Giua

Petri net controllers for generalized mutual exclusion constraints with floor operators. Automatica 2016; 74: 238–246.

Tong

Giua

On the equivalence of observation structures for Petri net generators. IEEE T Automat Contr 2016; 61: 2448–2462.

Fanti

Maione

Turchiano

Deadlock detection and recovery in flexible production systems with multiple capacity resources. In: Proceedings of the 8th Mediterranean Electrotechnical Conference, Bari, 13–16 May 1996, pp.237–241. New York: IEEE.

Kumaran

Chang

Cho

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

Zhou

MC.

Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles. IEEE T Syst Man Cy B 2005; 35: 1193–1202.

10.

Wysk

Yang

Josh

Resolution of deadlocks in flexible manufacturing systems: avoidance and recovery approaches. J Manuf Syst 1994; 13: 128–138.

11.

Xing

Chen

HX.

Deadlock avoidance policy for Petri-net modelling of flexible manufacturing systems with shared resources. IEEE T Automat Contr 1996; 41: 289–295.

12.

Xing

Zhou

Liu

. Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems. IEEE T Syst Man Cy A 2009; 39: 188–199.

13.

Chao

DY.

Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources. IET T Control Theory A 2008; 2: 168–179.

14.

Chao

DY.

MIP iteration-reductions for deadlock prevention of flexible manufacturing systems. Int J Adv Manuf Tech 2009; 41: 343–346.

15.

Ezpeleta

Colom

Martinez

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

16.

Fanti

Zhou

MC.

Deadlock control methods in automated manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 5–22.

17.

ZW.

Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources. Int J Adv Manuf Tech 2009; 40: 566–571.

18.

Huang

YS.

Deadlock prevention for flexible manufacturing systems in sequence resource allocation systems. J Inf Sci Eng 2007; 23: 215–231.

19.

Iordache

Antsaklis

PJ.

Synthesis of supervisors enforcing general linear vector constraints in Petri nets. IEEE T Automat Contr 2003; 48: 2036–2039.

20.

Iordache

Antsaklis

PJ.

Decentralized supervision of Petri nets. IEEE T Automat Contr 2006; 51: 376–381.

21.

Moody

Antsaklis

PJ.

Petri net supervisors for DES with uncontrollable and unobservable transitions. IEEE T Automat Contr 2000; 45: 462–476.

22.

Uzam

The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems. Int J Adv Manuf Tech 2004; 23: 204–219.

23.

Zhou

MC.

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

24.

Chen

Khalgui

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

25.

Chen

Zhou

MC.

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

26.

Chen

Barkaoui

New Petri net structure and its application to optimal supervisory control: interval inhibitor arcs. IEEE T Syst Man Cyb 2014; 44: 1384–1400.

27.

Chen

Barkaoui

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

28.

Chen

Barkaoui

. Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs. IEEE T Syst Man Cyb 2016; 47: 364–379.

29.

Chen

ZW.

Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica 2011; 47: 1028–1034.

30.

Huang

Pan

YL.

An improved maximally permissive deadlock prevention policy based on the theory of regions and reduction approach. IET T Control Theory A 2011; 5: 1069–1078.

31.

Huang

Pan

Zhou

Computationally improved optimal deadlock control policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2012; 42: 404–415.

32.

Zouari

Barkaoui

. Parameterized supervisor synthesis for a modular class of discrete event systems. In: Proceedings of IEEE international conference systems, man, and cybernetics, Washington, DC, 8 October 2003, pp.1874–1879. New York: IEEE.

33.

Chu

Xie

XL.

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

34.

Huang

Jeng

Xie

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

35.

Jeng

Xie

XL.

Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons. In: Zhou

Fanti

(eds) Deadlock resolution in computer-integrated systems. New York: Marcel Dekker, 2005, pp.233–281.

36.

Zhou

Jeng

MD.

A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE T Autom Sci Eng 2008; 5: 182–188.

37.

Liu

Jiang

Zhou

MC.

Two simple deadlock prevention policies for S³PR based on key-resource/operation-place pairs. IEEE T Autom Sci Eng 2010; 7: 945–957.

38.

Piroddi

Cordone

Fumagalli

Combined siphon and marking generation for deadlock prevention in Petri nets. IEEE T Syst Man Cy A 2009; 39: 650–661.

39.

Tricas

Ezpeleta

Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution. IEEE T Syst Man Cy A 2006; 36: 532–539.

40.

Zhou

MC.

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

41.

Zhao

On controllability of dependent siphons for deadlock prevention in generalized Petri nets. IEEE T Syst Man Cy A 2008; 38: 369–384.

42.

Zhao

ZW.

On deadlock control for a class of generalised Petri net models of flexible manufacturing systems. Int J Prod Res 2009; 47: 6085–6107.

43.

Zhao

Hou

Liu

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming. Int J Control 2010; 83: 2053–2066.

44.

Zhao

HS.

Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming. Int J Syst Sci 2010; 41: 1013–1026.

45.

Park

Structural analysis and control of resource allocation systems using Petri nets. Atlanta, GA: Georgia Institute of Technology, 2000.

46.

Barkaoui

Chaoui

Zouari

. Supervisory control of discrete event systems based on structure theory of Petri nets. In: Proceedings of IEEE international conference on systems, man, cybernetics, computational cybernetics and simulation, Orlando, FL, 12–15 October 1997, pp.3750–3755. New York: IEEE.

47.

Zhao

Hou

YF.

An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming. Discrete Event Dyn S 2013; 23: 3–26.

48.

Zhao

Uzam

Hou

YF.

Near-optimal supervisory control of flexible manufacturing systems using divide-and-conquer iterative method. Adv Mech Eng 2016; 8: 1–17.

49.

Hou

Zhao

. Extended elementary siphon-based deadlock prevention policy for a class of generalized Petri nets. Int J Comp Integ M 2014; 27: 85–102.

An integrated control method for designing non-blocking supervisors using Petri nets

Abstract

Keywords

Introduction

LICs extraction method for G-systems

Definition 1

Definition 2

Example

Definition 3

Example

Definition 4

Example

Definition 5

Example

Definition 6

Example

Definition 7

Definition 8

Definition 9

Remark 1

Proposition 1

Proof

Remark 2

Example

Theorem 1

Proof

Deadlock control policy based on MIP method

Definition 10

Notation 1

Theorem 2

Proof

Theorem 3

Proof

Definition 11

Proposition 2

Proof

Definition 12

Corollary 1

Remark 3

Example

Proposition 3

Proof

Theorem 4

Proof

The application of the proposed policy

A G-system example

Comparison study

Discussion

Conclusion

Footnotes

Appendix 1

Appendix 2

Declaration of conflicting interests

Funding

References