Design of improved optimal and suboptimal deadlock prevention for flexible manufacturing systems based on place invariant and reachability graph analysis methods

Abstract

Flexible manufacturing systems exhibit a high degree of resource sharing. Since the parts advancing through the system compete for a finite number of resources, a deadlock may occur. Accordingly, many pioneers make efforts in the issue. However, how to obtain maximally permissive supervisors in deadlock flexible manufacturing system is an extremely difficult and time-consuming problem. In existing literature, place invariant) and graph analysis method are merged called maximal number of forbidding First Bad Marking (FBM) problem to obtained optimal controllers with a small number of control places. However, this prevention just can be used in some special nets. For general cases, deadlocks could still exist. Therefore, this paper tries to propose one improved iterative deadlock prevention policy to solve above disadvantage. Experimental results show that the proposed improved policy can be used in all kinds of nets. In other words, it does improve the drawback of conventional maximal number of forbidding First Bad Marking (FBM) problem technology.

Keywords

Manufacturing control systems flexible manufacturing Petri nets mixed integer linear programming deadlock prevention policy

Introduction

Flexible manufacturing systems (FMS) exhibit a high degree of resource sharing. Since the parts advancing through the system compete for a finite number of resources, a deadlock may occur. Solving deadlock prevention, therefore, seems a very important issue in essence for FMS.

Accordingly, many experts make their best efforts in the issue.^1–7,9–18 In the literature,^{7,10,13,19–22} the deadlock prevention problem is solved using the concept of siphons. In particular, Ezpeleta et al.⁷ first defined a subclass of the ordinary and conservative Petri nets called Systems of simple sequential processes with resources (S³PR) and proposed one novel deadlock prevention policy based on the concept of strict minimal siphon (SMS). However, every SMS is needed to prevent such that permissive states of a deadlock-prone system can be enforced. In short, they all cannot obtain optimal ones. On the other hand, reachability graph methods are proposed to obtain the optimal behavior in a deadlock-prone system.^4–6 However, these methods have the time-consuming problem since they need to generate the reachability graph. It is worth mentioning that Hu et al.,^23–25 for the first time, investigate the deadlock resolution in the paradigm of Petri nets allowing assembly operations, multiple-type and multiple-quantity resource acquisition, and production ratio among jobs. A mathematical programming-based method is developed to synthesize liveness-enforcing supervisors. Their approach outperforms many traditional methods in both generality and efficiency.

To circumvent the above disadvantage of the conventional siphon control, Piroddi et al.¹⁷ proposed a control policy which combined the concepts of siphon control and reachability graph for solving deadlock problems. Our experience shows that the above policy is the first deadlock prevention policy to achieve the goal which can obtain maximally permissive controllers for all S³PR models in existing literature. However, the problem is still NP hard—the same as other optimal policies due to the need to generate the reachability graph of a Petri net.

The maximal permissive (optimal) supervisors in deadlock FMS can usually be found but is an extremely difficult and time-consuming problem. Recently, Chen et al.¹ proposed one novel technology called maximal number of forbidding FBM problem (MFFP) to obtain optimal states with a small number of control places. Place invariant (PI) and reachability graph analysis method play very important keys in this novel deadlock prevention policy. It solves the time-consuming problem successfully. However, this policy merely can be used in some special nets (i.e. S³PR⁶). Furthermore, it could get no solution outside S³PR net. In other words, deadlocks still exist.

In this paper, the authors try to propose one improved iterative deadlock prevention policy which can suit for all kinds of FMS. The proposed policy not only can obtain maximally permissive controllers in S³PR net but all deadlock situations can be solved even outside S³PR net. Experimental results show that the proposed algorithm does improve the drawback of conventional MFFP.

The rest of this paper is organized as follows. The next section presents the basic definitions and properties of Petri nets theory and reachability graph analysis. “The improved control place computation” section describes our proposed deadlock prevention policy. Next, “Examples” section presents the experimental results. The final sections give the comparisons and conclusions.

Preliminaries

Petri Nets^7,8

A Petri net is a four-tuple $N = (P, T, F, W)$ where P and T are finite and nonempty sets. P is a set of places and T is a set of transitions with $P \cap T = Ø$ and $P \cup T \neq Ø$ . $F \subseteq (P \times T) \cup (T \times P)$ is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. $W : (P \times T) \cup (T \times P) \to ℕ$ is pointing that sets a weight to an arc from P to T or from T to P, where $ℕ$ = {0, 1, 2,…}. Let $(N, M_{0})$ be a net system with $N = (P, T, F, W)$ . A transition $t \in T$ is live at M₀ if $\forall M \in R (N, M_{0}), \exists M' \in R (N, M_{0}), M' [t 〉$ . $(N, M_{0})$ is live if $\forall t \in T$ , t is live at M₀. It is dead at $M_{0}$ if $/ t \in T, M_{0} [t 〉$ .

A P-vector is a column vector $I : P \to ℤ$ indexed by P. P-vector I is called a P-invariant (place invariant, PI for short) if $I \neq 0$ and $I^{T} [N] = 0^{T}$ . P-invariant I is said to be a P-semiflow if $I \geq 0$ . Let I be a PI of $(N, M_{0})$ and M be a reachable marking from M₀. Then, $I^{T} M = I^{T} M_{0}$ .

Reachability graphs and first bad markings^1,5

A reachability graph can be partitioned into a deadlock zone (DZ) and a live zone (LZ). DZ contains deadlocks and bad markings that inevitably lead to deadlocks. LZ contains all the legal markings. The set of legal markings $M_{L}$ is the maximal set of reachability markings, from which the initial marking M₀ is reachable without leaving $M_{L}$ . Generally, the set of legal markings of a net $(N, M_{0})$ can be defined as

M_{L} = {M | M \in R (N, M_{0})^M_{0} \in R (N, M)}

(1)

An FBM is a node within DZ, representing the very first entry from LZ to DZ. Mathematically

M_{FBM} = {M \in DZ | \exists M' \in LZ, t \in T, s . t . M' [tM}

(2)

In a reachability graph, a system cannot enter DZ if all FBMs are forbidden by control places. In this case, the controlled system keeps running in LZ, i.e. it is live.

PI

This section presents the control place synthesis based on PI,³ which we can use to forbid FBMs.

Generally, PI is concerned with a control place, its reachability graph, and related arcs. Let $[D_{P}]$ be the incidence matrix of a plant with n places and m transitions. The control places can be represented by a matrix $[D_{c}]$ that indicates the incidence relationship between the control places and transitions of the plant. The controlled net with incidence matrix $[D]$ consists of both original net and control places, i.e.

[D] = [D_{p} D_{c}]

Suppose that the control goal is to enforce the plant to satisfy the following constraint

\sum_{i = 1}^{n} l_{i} \cdot μ_{i} \leq β

(3)

where

μ_{i}

denotes the marking of place p_i, and l_i and β are nonnegative integers. By introducing a nonnegative slack variable

μ_{s}

, this inequality constraint can be transformed into an equality as follows

\sum_{i = 1}^{n} l_{i} \cdot μ_{i} + μ_{s} = β

(4)

where

μ_{s}

represents the marking of control place p_s, generally called a monitor. All constraints in the form of constraint (3) can be grouped into a matrix form and rewritten as below

[L] \cdot μ_{p} \leq [β]

(5)

where μ_p is the marking vector of the Petri net model,

[L]

is an

n_{c} \times n

matrix, b is an

n_{c} \times 1

vector, and n_c is the number of constraints.

Similarly, all PI equations of the type of (4) can be grouped into a matrix form as follows

[L] \cdot μ_{p} + μ_{c} = [β]

(6)

where

μ_{c}

is an

n_{c} \times 1

vector that represents the markings of the control places.

The PIs defined by equation (4) satisfy the PI equation $I^{T} [D] = 0^{T}$ . Given a Petri net incidence matrix $[D_{p}]$ and constraints $[L]$ and b, the supervisor $[D_{c}]$ can be computed by

I^{T} [N] = [L Ω] \cdot [D_{p} D_{c}] = 0^{T}; [D_{c}] = - [L] \cdot [D_{p}]

(7)

where

[Ω]

is an

n_{c} \times n_{c}

identity matrix since the all coefficients of the slack variables in the equations are equal to one.

Equation (6) must be true at the initial marking of a net. Thus, the initial marking $μ_{c 0}$ of the supervisor can be calculated as follows

μ_{c 0} = [β] - [L] \cdot μ_{p 0}

(8)

where

μ_{P 0}

is defined as the initial marking vector of the plant net.

The improved control place computation

Maximally permissive controller synthesis

One optimal controller synthesis method is obtaining maximally permissive controllers for a Petri net model of an FMS. Generally, all places in a Petri net can be defined as idle, activity, and resource places which are denoted as P⁰, P_A, and P_R, respectively.⁶ In designing of deadlock prevention policy, only activity places are considered.

Each FBM $M \in M_{FBM}$ can be forbidden by the following constraint

\sum_{i \in N_{A}} l_{i} \cdot μ_{i} \leq β

(9)

where

μ_{i}

denotes the number of tokens in places which belongs to activity places at a reachability marking μ, N_A is defined as

N_{A} = {i | p_{i} \in P_{A}}

, and β is defined as below

β = \sum_{i \in N_{A}} l_{i} \cdot M (p_{i}) - 1

(10)

Constraint (9) is called the forbidding condition. To ensure all marking $M' \in M_{L}$ is reachable, coefficient $l_{i} (i \in N_{A})$ in constraint (9) must satisfy

\sum_{i \in N_{A}} l_{i} \cdot M' (p_{i}) \leq \sum_{i \in N_{A}} l_{i} \cdot M (p_{i}) - 1

(11)

Constraint (11) is called the reachability conditions. For an FBM, by substituting equations (10) and (11), the reachability conditions of legal markings become

\sum_{i \in N_{A}} l_{i} \cdot (M' (p_{i}) - M (p_{i})) \leq - 1

(12)

Constraint (12) determine coefficients $l_{i} (i \in N_{A})$ . Thus, for an FBM, if its coefficients $l_{i} (i \in N_{A})$ of a PI satisfy constraint (12), then the PI designed by constraint (9) to forbid FBM, and there is no any legal marking forbidden.

Please note that we still find out suboptimal controllers once maximally permissive behavior does not exist in Petri net model of one FMS. In other words, the proposed improved deadlock prevention in this paper will identify one system’s optimal controllers if the maximal permissive behavior of one Petri net model does exist. Or, the proposed policy still finds out its suboptimal controllers so as to one Petri net model of an FMS is live.

New vector covering approach for PI¹

This section tries to improve the conventional vector covering approach which Chen et al.^1,2 developed to design an optimal PI, which can greatly reduce computation and the sets of FBMs and legal markings to be considered.

Definition 1

Let M and $M'$ be any two markings in $R (N, M_{0})$ . M A-covers $M'$ if $\forall p \in P_{A}, M (p) \geq M' (p)$ , which is denoted as $M \geq_{A} M'$ .

Similarly, if M A-covers M′, it can also be considered that M′ is A-covered by M, which is denoted as $M \leq_{A} M'$ . Assumed that M and M′ be two markings in $R (N, M_{0})$ with $M \geq_{A} M'$ . If $M'$ is forbidden by a PI, M is also forbidden; if is not forbidden by a PI, in other words, M′ is not forbidden.

Definition 2

Let $M_{FBM}^{⋆}$ be a subset of $M_{FBM}$ . $M_{FBM}^{⋆}$ is called the minimal covered set of FBMs if the following two conditions are satisfied:

$\forall M \in M_{FBM}, \exists M' \in M_{FBM}^{⋆}, s . t . M \geq_{A} M'$ ;

$/ t \in T, M_{0} [t 〉$ and $M \neq M ″$ .

In definition 2, if all markings in $M_{FBM}^{⋆}$ are forbidden by PI, all the FBMs are forbidden.

Definition 3

Let $M_{L}^{⋆}$ be a subset of $M_{L}$ . $M_{L}^{⋆}$ is called the minimal covering set of legal markings if the following two conditions are satisfied:

$\forall M \in M_{L}, \exists M' \in M_{L}^{⋆}, s . t . M' \geq_{A} M$ ;

$\forall M \in M_{L}^{⋆}, / M ″ \in M_{L}^{⋆}, s . t . M ″ \geq_{A} M$ and $M \neq M ″$ .

In definition 3, if no any markings in $M_{L}^{⋆}$ are forbidden by PI, all the FBMs are reachable.

Generally, $M_{FBM}^{⋆}$ and $M_{L}^{⋆}$ are smaller than $M_{FBM}$ and $M_{L}$ , which represent the set of all FBMs and legal markings, respectively. We can avoid considering all the legal markings and FBMs via formulating the minimal covering set of legal markings and the minimal covered set of FBMs, which is important particularly in high complexity FMS model.

Therefore, the vector covering approach can greatly reduce computation by reducing FBMs and legal markings which is needed to be considered.

Control place synthesis for forbidding FBMs

This section briefly reviews two techniques that Chen et al.¹ developed to design a maximally permissive PI, which can prevent system from FBMs as many as possible and no any legal marking. By using the proposed method in “New vector covering approach for PI¹” section, we can use the optimal PI to forbid FBMs. Let I be a PI for the constraint

I : \sum_{i \in N_{A}} l_{i} \cdot μ_{i} \leq β

(13)

where l_i’s are the coefficient of I, and β is a positive integer variable.

An FBM $M \in M_{FBM}^{⋆}$ is forbidden by I if

\sum_{i \in N_{A}} l_{i} \cdot M (p_{i}) \geq β + 1

(14)

A set of variable f_k’s $(k = 1, 2, \dots)$ is introduced to represent the relation between I and $M_{k} \in M_{FBM}^{⋆}$ . Therefore, constraint (15) is formulated as

\sum_{i \in N_{A}} l_{i} \cdot M (p_{i}) \geq β + 1 - Q \cdot (1 - f_{k})

(15)

where Q is a positive integer constant that must be big enough and

f_{k} \in {0, 1}

. In constraint (15),

f_{k} = 1

indicates that M_k is forbidden by I, and

f_{k} = 0

indicates that this constraint is redundant and M_k cannot be forbidden by I.

The coefficient of I and β should satisfy the reachability conditions. As a result, we have the following ILPP to design a PI, which is denoted as the MFFP as follows

MFFP : max f = \sum_{k \in N_{FBM}^{⋆}} f_{k}

Subject to

\sum_{i \in N_{A}} l_{i} \cdot M_{l} (p_{i}) \leq β, \forall M_{l} \in M_{L}^{⋆} \sum_{i \in N_{A}} l_{i} \cdot M_{k} (p_{i}) \geq β + 1 - Q \cdot (1 - f_{k}), \forall M_{k} \in M_{FBM}^{⋆} l_{i} \in {0, 1, 2, \dots}, \forall i \in N_{A} β \in {1, 2, \dots} f_{k} \in {0, 1}, \forall k \in N_{FBM}^{⋆}

The objective function f is used to maximize the number of FBMs that are forbidden by I. Please note that if $f = 0$ , there is no maximally permissive PI for any FBM in $M_{FBM}^{⋆}$ . Therefore, we need to seek general PI once no maximally permissive PI for all FBMs or deadlocks still exist while controllers are added in the net. And, the new added constraint should be

\sum_{i \in N_{A}} l_{i} \cdot μ_{i} \leq γ where μ \leq β; \in {1, 2, \dots}

(16)

The above improved maximal number of forbidding FBM problem is called IMFFP.

The improved deadlock prevention policy

Input: One Petri net model $(N, M_{0})$ of an deadlock FMS with $N = (P, T, F, W)$ .

Output: One optimal (maximally permissive)/suboptimal controlled Petri net system ( $N, M_{0}$ ).

The proposed deadlock prevention algorithm has the following steps given a deadlock PN model.

Generate R(N, M₀).

Identify all dead, illegal markings, and legal markings.

Identify all FBMs.

Identify the relative minimal covering sets of legal markings and covered set of FBMs.

List IMFFP equation.

Solve ILPPs.

All ILPPs are solved? /Yes go to Step 8. /No go to Step 9.

End and output the optimal controlled system.

Adding all obtained controllers into model and redo steps 4–6.

Solve suboptimal ILPPs.

End and output the suboptimal controlled system.

Theorem 1

The improved deadlock prevention policy is more efficient than the method in Chen et al.¹

Proof

(1) The S³PR net is included in all kinds of nets. (2) The conventional method MFFP is used merely in S³PR net. (3) The improved deadlock prevention policy in this paper can be used for all kinds of net. (4) Therefore, the improved deadlock prevention policy is more efficient than the method in Chen et al.¹

Examples

In this section, two examples are used to evaluate the proposed improved policy. The first one is a classical S³PR model. And, it is used to show our improved policy how to get the optimal controllers for a deadlock FMS when maximally permissive states exist. The second one is used to present how to obtain suboptimal controllers once maximally permissive states do not exist.

Example I

The Petri net model of FMS and its reachability graph are shown as Figures 1 and 2, respectively. There are 20 markings in total, five and 15 of which are FBMs and legal ones, respectively.

Figure 1.

A Petri net model of FMS. FMS: flexible manufacturing system.

Figure 2.

The reachability graph of Figure 1.

According to the proposed definition in “Control place synthesis for forbidding FBMs” section, the minimal covering set of legal markings and the minimal covered set of FBMs are $M_{FBM}^{⋆} = {M_{4}, M_{8}, M_{9}} = {{FBM}_{1}, {FBM}_{2}, {FBM}_{3}} = {p_{2} + p_{5}, p_{3} + p_{5}, p_{2} + p_{6}}$ and $M_{L}^{⋆} = {M_{18}, M_{19}} = {p_{2} + p_{3} + p_{4}, p_{5} + p_{6} + p_{7}}$ , respectively. Therefore, one can obtain an ILPP, all minimal covering set of legal markings, and the minimal covered set of FBMs shown as follows

IMFFP : max f = f_{1} + f_{2} + f_{3}; f_{k} \in {0, 1}, \forall k \in {1, 2, 3} . l_{2} + l_{3} + l_{4} \leq β l_{5} + l_{6} + l_{7} \leq β l_{2} + l_{5} \geq β + 1 - Q \cdot (1 - f_{1}) l_{3} + l_{5} \geq β + 1 - Q \cdot (1 - f_{2}) l_{2} + l_{6} \geq β + 1 - Q \cdot (1 - f_{3}) β \in {1, 2, \dots}

The above ILPP has an optimal solution with $l_{2} = 2$ , $l_{5} = 1$ , $l_{6} = 1$ , $β = 2$ , $f_{1} = 1$ , $f_{3} = 1$ , and the others are zero. According to the result, therefore, we can design the first set of PI as below

I_{1} : 2 μ_{2} + μ_{5} + μ_{6} + μ_{p_{c_{1}}} = 2

(17)

Accordingly, one control place calculated is that $M_{0} (p_{c_{1}}) = β = 2$ , $^{•} p_{c_{1}} = {2 t_{2}, t_{7}}$ , and $p_{c_{1}}^{•} = {2 t_{1}, t_{5}}$ .

After the first iteration, we can find that ${FBM}_{2}$ still cannot be forbidden. Therefore, the next iteration should be considered. Since ${FBM}_{1}$ and ${FBM}_{2}$ have been forbidden by the first iteration of ILPP, the minimal covered set of FBMs is only $M_{FBM}^{⋆} = {{FBM}_{2}} = {M_{4}}$ . According to the section iteration of $M_{FBM}^{⋆}$ , a new ILPP is shown as below

The second iteration of above ILPP has another optimal solution when $l_{3} = 1$ , $l_{5} = 1$ , $β = 2$ , $f_{2} = 1$ , and the others are zero. Similarly, we can also design second set of PI as below

I_{2} : μ_{3} + μ_{5} + μ_{p_{c_{2}}} = 1

(18)

Similarly, one control place calculated is that $M_{0} (p_{c_{2}}) = β = 1,^{•} p_{c_{2}} = {t_{3}, t_{6}}$ , and $p_{c_{2}}^{•} = {t_{2}, t_{5}}$ .

Adding these two control places to the original model shown in Figure 3, one new Petri net model is with 15 maximally permissive legal markings. Most important, it is deadlock free.

Example II

Another model shown in Figure 4 is used to demonstrate the proposed policy. In this model, there are 39 markings, nine and 23 of which are FBMs and legal ones, respectively (shown in Figure 5). According to vector covering approach, the set of minimal covered set of FBMs and legal markings can be defined as $M_{FBM}^{⋆} = {M_{6}, M_{12}, M_{14}} = {{FBM}_{1}, {FBM}_{2}, {FBM}_{3}} = {p_{2} + p_{5}, p_{3} + p_{5}, p_{2} + p_{6}}$ and $M_{L}^{⋆} = {M_{38}, M_{39}} = {2 p_{2} + p_{3} + p_{4}, 2 p_{5} + p_{6} + p_{7}}$ , respectively.

Figure 3.

The live system with optimal controllers.

Figure 4.

General Petri net model of an FMS. FMS: flexible manufacturing system.

Figure 5.

The reachability graph of Figure 4.

After determining the minimal covered set of FBMs and legal markings, we have an ILPP as below

IMFFP : f_{k} \in {0, 1}, \forall k \in {1, 2, 3} 2 l_{2} + l_{3} + l_{4} \leq β 2 l_{5} + l_{6} + l_{7} \leq β l_{2} + l_{5} \geq β + 1 - Q \cdot (1 - f_{1}) l_{3} + l_{5} \geq β + 1 - Q \cdot (1 - f_{2}) l_{2} + l_{6} \geq β + 1 - Q \cdot (1 - f_{3}) β \in {1, 2, \dots}

The ILPP above has an optimal solution with, $l_{3} = 2$ , $l_{5} = 1$ , $β = 2$ , $f_{2} = 1$ , and the others are zero. In this iteration, only ${FBM}_{2}$ is forbidden. The second iteration is considered for forbidding other FBMs. Thus, we have new ILPP

max f = f_{1} + f_{3}; f_{k} \in {0, 1}, \forall k \in {1, 3} 2 l_{2} + l_{3} + l_{4} \leq β 2 l_{5} + l_{6} + l_{7} \leq β l_{2} + l_{5} \geq β + 1 - Q \cdot (1 - f_{1}) l_{2} + l_{6} \geq β + 1 - Q \cdot (1 - f_{3}) β \in {1, 2, \dots}

The ILPP above has an optimal solution with $l_{1} = 1$ , $l_{6} = 2$ , $β = 2$ , $f_{3} = 1$ , and the others are zero. After two iterations, only ${FBM}_{1}$ is not forbidden. Thus, we continue using the third set of ILPP as the third iteration

MFFP : max f = f_{1}; f_{k} \in {0, 1}, k \in {1} 2 l_{2} + l_{3} + l_{4} \leq β 2 l_{5} + l_{6} + l_{7} \leq β l_{2} + l_{5} \geq β + 1 - Q \cdot (1 - f_{1}) β \in {1, 2, \dots}

However, there is no solution in the above ILPP. In other words, there are no optimal controllers in this example. It means that conventional MFFP method fails to solve the deadlock problem of this model. No doubt, after adding above two controllers into original model shown in Figure 6, its new reachability graph is present in Figure 7.

Figure 6.

The Petri net model with two controllers.

Figure 7.

The reachability graph of the uncontrolled model of Figure 6.

In our proposed policy, deadlock free controllers still can be obtained even when optimal controllers does not exist. Therefore, we redefine $M_{FBM}^{⋆}$ as $M_{FBM}^{⋆} = {{FBM}_{1}, {FBM}_{2}, {FBM}_{3}} = {M_{6}, M_{10}, M_{13}}$ since there are still four FBMs M₆, $M_{10}$ , $M_{13}$ , and $M_{20}$ cannot be forbidden. To design optimal PIs, by computation of new ILPP, we obtain the new three PIs as below

I_{3} : 2 μ_{3} + μ_{5} \leq 2 I_{4} : μ_{2} + 2 μ_{6} \leq 2 I_{5} : μ_{2} + μ_{5} \leq 1

(19)

Accordingly, we pick I₅ as the third set of PI since I₅ is the simplest one among all PIs. Finally, the third controller is then calculated. It is M₀( $p_{c_{3}}$ ) = 1, $^{•} p_{c_{3}} = {t_{6}, t_{2}}$ , and $p_{c_{3}}^{•} = {t_{1}, t_{5}}$ . The system is deadlock free when the third controller is added into the model of Figure 6. The controlled system and its reachability graph are shown in Figures 8 and 9, respectively.

Figure 8.

All controllers are added into example II.

Figure 9.

The reachability graph of the controlled model by IMFFP. IMFFP: improved maximal number of forbidding FBM problem.

Comparison with previous methods

This section compares this work with the past deadlock prevention policies^{1,4,14–17,19,21,26} based on the two examples of this paper. Please note that all prevention policies mentioned and shown in Table 1 are optimal control. In other words, these past policies can keep the controlled system (i.e. example I) maximally permissive. However, they just can be applied in some special S³PR nets. Nevertheless, it is still obvious that based on Table 1 the policy¹ and this work seems the best if we just focus on the number of control places and their relative arcs of the controlled example I since both of them are two control places and two arcs.

Table 1.

Comparison of the controlled example I.

Policy	Optimal?	Method	Number of control places?	Number of arcs?
Uzam⁴	Optimal	Theory of regions and MTSI	3	6
Huang et al.¹⁶	Optimal	Theory of regions and CMTSI	3	6
Pan et al.¹⁵	Optimal	Theory of regions and CMTSI with improved linear programming problems	3	6
Pan et al.¹⁴	Optimal	Theory of regions and CMTSI and selective siphon	3	6
Huang et al.¹⁹	Optimal	Minimal siphon	3	6
Li and Zhou²¹	Optimal	Elementary siphon	3	6
Piroddi et al.¹⁷	Optimal	Selective siphon	3	6
Pan et al.²⁶	Optimal	Improved selective siphon	3	6
Chen et al.¹	Optimal	MFFP	2	4
This work	Optimal	Improved MFFP	2	4

CMTSI: crucial set of marking transition separation instances; MFFP: maximal number of forbidding FBM problem; MTSI: the set of marking transition separation instances.

From Table 2, however, it is obvious that the policy¹ cannot be used in example II. It means that for general cases, the policy¹ cannot solve the deadlock problems. Based on above reason, this paper tries to propose one improved iterative deadlock prevention policy to solve above disadvantage. Therefore, from experimental results shown in Table 2, the proposed improved policy does improve the drawback of conventional MFFP technology.

Table 2.

Comparison in example II.

Policy	Controlled?	Method	Number of control places?	Number of arcs?
Chen et al.¹	Fail	MFFP
This work	Yes	Improved MFFP	3	12

MFFP: maximal number of forbidding FBM problem.

Conclusions

Solving deadlock problems of FMSs is a topic of intense research nowadays due to the damaging consequences to the entire factory if it was not controlled. Therefore, so many experts try to propose all kinds of technology. However, how to keep the liveness of one controlled system is very difficult. Nowadays, therefore, all proposed deadlock prevention methods devote to identifying maximally permissive and least number of controllers. In existing literature, all kinds of methods are tried to develop for this goal. In our study, the deadlock prevention policy developed by Chen et al.¹ seems the best one since it can obtain maximally permissive controllers and least number of control places. However, it just can be applied in some special S³PR nets.

Based on above reasons, this paper tries to propose one iterative deadlock prevention policy to circumvent the disadvantage. Although the final result is still suboptimal, it does control the deadlock system. In fact, this paper is the first one proposed to improve the MFFP technology. Experimental results also show that the proposed improved policy can be used in all kinds of nets. Therefore, we believe that this paper contains several new and significant concepts and ideas as well as enough materials since it does improve the drawback of conventional MFFP technology. In the future, we will try to enhance further the computational efficiency of MPPF technology and lower the computer time in solving the process of systems’ deadlock problem. Besides, how to use the concept of “Inhibitor Arcs”²⁷ solving deadlock problems is also our future goal since it can deal with the considered problem proposed in this paper.

Footnotes

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) received no financial support for the research, authorship, and/or publication of this article.

References

Chen

Zhou

. Behaviorally optimal and structurally simple liveness – enforcing supervisors of flexible manufacturing systems. IEEE Trans Syst Man Cybern A Syst Humans 2012; 42: 615–629.

Chen

Khalgui

et al.

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

Yamalidou

Moody

Lemmon

et al.

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

Uzam

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

Uzam

Zhou

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

Ghaffari

Rezg

Xie

. Feedback control logic for forbidden-state problems of marked graphs: application to a real manufacturing system. IEEE Trans Robot Automat 2003; 48: 18–29.

Ezpeleta

Colom

Martinez

. A Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE Trans Robot Automat 1995; 11: 173–184.

Murata

. Petri nets: properties, analysis and application. Proc IEEE 1989; 77: 541–580.

Kumaran

Chang

Cho

et al.

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

10.

Barkaoui

Abdallah

. Deadlock avoidance in FMS based on structural theory of Petri nets. Proc IEEE Symp Emerg Technol Fact Automat 1995; 2: 499–510.

11.

Xing

Zhou

Liu

et al.

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

12.

Xiong

Fan

Zhou

. A Petri net approach to analysis and composition of web services. IEEE Trans Syst Man Cybern A Syst Humans 2010; 40: 376–387.

13.

Huang

Jeng

Xie

et al.

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

14.

Pan

Huang

Jeng

et al.

Enhancement of an efficient control policy for FMSs using the theory of regions and selective siphons method. Int J Adv Manuf Technol 2013; 66: 1805–1815.

15.

Pan

Huang

Weng

et al.

Computationally improved optimal control methodology for linear programming problems of flexible manufacturing systems. J Appl Math 2013; 2013: 1–11.

16.

Huang

Pan

Zhou

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

17.

Piroddi

Cordone

Fumagalli

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

18.

Piroddi

Cordone

Fumagalli

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

19.

Huang

Jeng

Xie

et al.

Siphon-baseddeadlockpreventionpolicy for flexible manufacturing systems. IEEE Trans Syst Man Cybern A Syst Humans 2006; 36: 2152–2160.

20.

Huang

. Design of deadlock prevention supervisors for FMS using Petri nets. Int J Adv Manuf Technol 2007; 35: 349–362.

21.

Zhou

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

22.

Zhou

. On siphon computation for deadlock control in a class of Petri nets. IEEE Trans Syst Man Cybern A Syst Humans 2008; 38: 667–679.

23.

Zhou

. Supervisor design to enforce production ratio and absence of deadlock in automated manufacturing systems. IEEE Trans Syst Man Cybernet Part A 2011; 41: 201–212.

24.

Zhou

. Liveness and ratio-enforcing supervision of automated manufacturing systems using Petri nets. IEEE Trans Syst Man Cybernet Part A 2012; 42: 392–403.

25.

Zhou

. Supervisor optimization for deadlock resolution in automated manufacturing systems with Petri nets. IEEE Trans Automat Sci Eng 2011; 8: 794–804.

26.

Pan

Yang

Jeng

. Enhancement of selective siphon control method for deadlock prevention in FMSs. Math Probl Eng 2015; 2015: Article ID 196514, 1–6. http://dx.doi.org/10.1155/2015/196514.

27.

Chen

Barkaoui

et al.

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

Design of improved optimal and suboptimal deadlock prevention for flexible manufacturing systems based on place invariant and reachability graph analysis methods

Abstract

Keywords

Introduction

Preliminaries

Petri Nets7,8

Reachability graphs and first bad markings1,5

PI

The improved control place computation

Maximally permissive controller synthesis

New vector covering approach for PI 1

Definition 1

Definition 2

Definition 3

Control place synthesis for forbidding FBMs

The improved deadlock prevention policy

Theorem 1

Proof

Examples

Example I

Example II

Comparison with previous methods

Conclusions

Footnotes

Declaration of conflicting interests

Funding

References

Petri Nets^7,8

Reachability graphs and first bad markings^1,5

New vector covering approach for PI¹