Robust deadlock control for automated manufacturing systems with a single type of unreliable resources

Abstract

In automated manufacturing systems, resource failures are often inevitable. They reduce the number of available resources and may cause some processing routes of parts to halt and sometimes the whole system to shutdown. This article focuses on the robust deadlock control problem in automated manufacturing systems with multiple resource failures. To obtain such a robust controller, we first put forward a new concept of blocked states of automated manufacturing systems. From such a state, the production of some part types through one of their routes is blocked as caused by resource failures, and only after some failed resources are repaired, these parts can resume their normal processing. Then, these blocked states are characterized in terms of emptied siphons caused by resource failures. In order to prevent the system from deadlocks and blocked states, a robust controller is proposed by the following two steps. First, for siphons without unreliable resources, optimal deadlock control places are added. Then for siphons which contain unreliable resources, new control places are devised to ensure that they could be marked even when resource failures happen. It is proved that the proposed controller can guarantee that all types of parts can be processed repeatedly as long as one unit of unreliable resources can still work. This means that the proposed controller is of greatest robustness, that is, it can tolerate a maximum number of resource failures. Some examples are provided to illustrate the proposed method and show the advantage over the previous ones.

Keywords

Automated manufacturing system Petri net unreliable resource robust control deadlock

Introduction

Automated manufacturing systems (AMS) are modern production facilities which are highly adaptable to variable production plans and goals. Due to the competition of shared resources in AMS, deadlocks may occur, leading to unnecessary cost or even catastrophic results. Besides, AMSs have many types of components such as a sensor, an actuator, a tool, and so on which can fail unexpectedly, and any of the failure can cause an unexpected and unpredictable disruption. Therefore, it is highly important to develop an efficient controller to avoid these deadlock situations and guarantee the normal production of the system while resource failures happen.

It is well known that Petri nets (PNs) represent an important and popular mathematical model for modeling and analyzing discrete event systems, particularly AMS. Thus, many researchers adopt PN as a formalism to describe AMS and develop appropriate deadlock control methods and scheduling algorithm,^1–6 resulting in a wide variety of approaches.

Majority of deadlock control methods can be classified into two categories, namely, deadlock prevention^7–11,27 and deadlock avoidance.^12–14,28 However, in these deadlock control methods mentioned above, all the resources are assumed to be reliable, while real-world AMS may contain unreliable resources. When an AMS suffers resource failures, some or all of its processes might be blocked until these failed resources are repaired. Since resources repair may take a long time, these blocked states (BSs) reduce the efficiency of production. Consequently, it is necessary to develop an effective supervisory controller for AMS with unreliable resources, called as robust deadlock controller, to guarantee that all part types can be processed repetitively through any one of their process routes even when resource failures happen.

Some researchers have studied on the robust deadlock control of AMS with unreliable resources.^15–23 Generally speaking, according to the ways to model resource types, they can be divided into two categories. In Lawley and Sulistyono,¹⁸ resource types are modeled as workstations, one workstation is composed of one machine and multiple buffer spaces, and resource failure implies the failure of the workstation’s machine, not its buffer spaces. For this kind of AMS, Lawley and Sulistyono proposed a robust supervisory control policy. Neighborhood constraints and Banker’s Algorithm are used to guarantee that when the unreliable resource fails, the system can continue to produce all part types not requiring it. Many other researchers have also studied this kind of system and have achieved some results.^{15,20,22–24} While for another kind of AMS,^16,17,19,21 resource types are modeled as machines, one resource type may contain multiple machines. For this kind of AMS, Hsieh¹⁷ analyzed the fault-tolerant property of controlled assembly PNs and proposed an algorithm to handle unavailability of resources. Liu et al.¹⁹ used recovery subnets to describe the resource failure and recovery in system of simple sequential processes with resources (S³PR) with unreliable resources. Based on the concept of transition cover,² Feng et al.¹⁶ obtained a 1-robust PN controller for S³PR with a single unreliable resource, and it can ensure that the system can process all types of parts infinitely even if one of unreliable resources fails. Wu et al.²¹ reports a novel approach to obtain a 1-robust controller such that the controlled system can still work normally even if one resource failure happens.

The controller in Wu et al.²¹ suffers from the following two shortcomings: First, it overly restricts the permissive behavior of a PN because the output arcs of a controller are all led to the source transitions of the net, which limits the number of workpieces to be released into and processed by the system at a time. A source transition is the output of an idle place, which models the entry of raw parts into the system. Second, its robustness is too limited and not practical, since it only consider the case of at most one unit of resource failure, while real AMS may suffer from multiple resource failures. In order to handle the considered two shortcomings and to achieve a widely industrial applicability, this article proposes a multiple robust controller with more permissive behavior.

This article focuses on the robust deadlock control problem in AMS with a single type of unreliable resource. We consider only the case that an unreliable resource (machine or robot) can fail, but its buffer can still be assigned workpieces, and then resource failures in operation places are analyzed. The concept of a k-robust controller is defined. It guarantees repeated processing of all part types when most k units of the unreliable resource fail to work. After any number of failed resource units are repaired, they can be returned to the system to continue working. For an AMS with single type of unreliable resource r_u, this article presents how to design a robust controller, which can make sure that the whole system can produce products as long as one unit of unreliable resource can work.

This work makes two improvements over the approach in Wu et al.:²¹ First, the robust controller in this work is more permissive than controllers in Ezpeleta et al.,⁷ Liu et al.,¹⁰ and Wu et al.²¹ Note that the controllers in Ezpeleta et al.⁷ and Liu et al.¹⁰ are proposed for AMSs with reliable resources, and hence, no robustness, while the controller proposed in this article is robust for unreliable systems. Experimental study indicates that even for reliable AMS, the proposed controller in this article is more permissive than those non-robust controller. Second, this article improves the robustness level (RL) of the controller, from 1 in Wu et al.²¹ to Ψ(r_u) −1, where Ψ(r_u) is the capacity of unreliable resource r_u. The proposed robust controller can ensure continuous processing of all types of parts as long as one unit of unreliable resources can work. To the best of our knowledge, it is the first one with greatest robustness, that is, it can tolerate a maximum number of resource failures.

There are two major differences between this work and those in Wang et al.,²⁰ Yue and Xing,²² and Yue et al.:²³ First, the classes of AMSs considered are different. In Wang et al.,²⁰ Yue and Xing,²² and Yue et al.,²³ a resource type is one machine with buffer spaces and resource failure means the machine failure, not any of its buffer space. When the resource fails, it cannot process any parts, but its buffer space can still be used, while in this work, unreliable resources are only machines and robots without buffer spaces. Second, since the considered systems are different, the control objectives are completely different. In Wang et al.,²⁰ Yue and Xing,²² and Yue et al.,²³ the objective is to develop a control policy that allocates resources so that the failure of any given resource does not propagate through blocking to effectively stall other portions of the system. In other words, when a resource fails, they want the system to automatically continue producing all part types that do not require the failed resource. While in this article, we must ensure that the system can produce all types of parts even if Ψ(r_u) − 1 unreliable resources are failed.

The class of AMSs considered in this article is the same as Feng et al.¹⁶ and Wu et al.,²¹ but the performance of the proposed controller is better than that of controllers in Feng et al.¹⁶ and Wu et al.²¹ The controller proposed in this article permits more reachable markings than controllers in Feng et al.¹⁶ and Wu et al.²¹ Meanwhile, the proposed controller has a higher RL, up to Ψ(r_u)−1, while controllers in Feng et al.¹⁶ and Wu et al.²¹ have only 1, that is, they only considered the case where one unit of unreliable resources may fail.

The rest of this article is organized as follows. Some basic PN definitions are recalled in the next section. Then, we analyzed the BSs in S³PR with single type of unreliable resources and proposed a novel robust controller. Two examples are given and the results and principal outcomes of this article are discussed. The last section concludes this article.

Basic definitions of PNs

This section recalls some basic definitions and properties of PNs, S³PRs, and resource-transition circuits (RTCs). The reader is referred to Ezpeleta et al.,⁷ Han et al.,⁸ Xing et al.,¹⁴ and Zhou and Venkatesh²⁵ for more details.

PNs

A PN is a four-tuple N = (P, T, F, W), where P and T are finite sets of places and transitions, respectively. F⊆ (P×T) ∪ (T×P) is the set of directed arcs. W: F→Z ⁺ is an arc weighted function, where Z⁺ denotes the set of positive integers. N is pure or self-loop free if (x, y) ∈F implies (y, x) ∉F; N = (P, T, F, W) is ordinary if ∀f∈F, W(f) = 1, and in this case, W can be omitted. In this article, all the studied PNs are pure and ordinary. A pure net structure can be described by its incidence matrix [N], and it is a [P] × [T] integer matrix with [N](p, t) = W(t, p) − W(p, t).

Given a node x∈P∪T, the preset of x is defined as ^•x = {y∈P∪T | (y, x) ∈F}, and the postset of x is defined as x^• = {y∈P∪T | (x, y) ∈F}. These notations can be extended to a set, for example, if X⊆P×T, then ^•X = ∪_x∈_X^•x and X^• = ∪_x∈_Xx^•. A state machine is a PN in which each transition has exactly one input and one output place.

Let S be a nonempty subset of places and S is a siphon (trap) if ^•S⊆S^• (S^•⊆^•S). A siphon is said to be minimal if it contains no other siphons as its proper subset. A minimal siphon is said to be strict if it does not contain a trap. A strict minimal siphon is denoted as SMS for short.

Let Z = {0, 1, 2, …}, and Z_k = {1, 2, …, k} for a given positive integer k. A path x₁, …, x_n is a string where x_i_+ 1∈x_i^•, i∈ Z_n–1. A simple path is a path whose nodes are all different (except x₁ and x_n). A path x₁, …x_n is called a circuit if it is a simple path and x₁ = x_n.

A marking or state of N is a mapping M: P→ Z. A PN N with an initial marking M₀ is called a marked PN, denoted as (N, M₀). Given a place p∈P and a marking M, M(p) denotes the number of tokens in p at M. For B⊆P, let M(B) = Σ_p∈_BM(p).

Given a marking M, a transition t is enabled at M if ∀p∈^•t, M(p)≥W(p, t), and this fact can be denoted by M[t>. An enabled transition t at M can fire, resulting in a new marking M′, which is denoted by M[t>M′. A marking M is said reachable from M₀ if there exists a sequence of transitions σ such that M₀[σ>M holds. Let R(N, M₀) be the set of markings reachable from M₀ in N. A transition t is live if ∀M ∈ R(N, M₀) and ∃M′ ∈ R(N, M) so that M′[t>. A transition t is dead at M ∈ R(N, M₀) if ∀M′ ∈ R(N, M), M′[t>does not hold. (N, M₀) is said to be live if every transition of it is live.

A P vector is a column vector I: P → Z indexed by P, where Z is the set of integers. P vector I is called a P-invariant if I ≠ 0 and I^T[N] = 0^T. A P-semiflow I is a P-invariant satisfying that every element of I is non-negative.||I|| = {p ∈ P | I(p) ≠ 0} is called the support of I.

The composition of two PNs, N_i = (P_i, T_i, F_i), i∈{1, 2}, via the same elements, denoted as N₁⊗ N₂, is a PN N₁ ⊗ N₂ = (P, T, F), where P = P₁∪ P₂, T = T₁∪ T₂, and F = F₁∪ F₂. Two marked PNs, (N_i, M_i₀) = (P_i, T_i, F_i, M_i₀), i ∈ {1, 2}, are compatible if ∀p ∈ P₁ ∩ P₂, M₁₀(p) = M₂₀(p). The composition of two compatible PNs (N₁, M₁₀) and (N₂, M₂₀) is a marked PN (N₁, M₁₀) ⊗ (N₂, M₂₀) = (N₁ ⊗ N₂, M₀), where M₀(p) = M₁₀(p), ∀p ∈ P₁ and M₀(p) = M₂₀(p), ∀p ∈ P₂.

S³PR class

Definition 1

An S³PR is an ordinary PN (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) defined as follows:

P ∪ P₀ ∪ P_R is a partition such that (1.1) $P = ⋃_{i = 1}^{m} P_{i}$ is the set of operation places, where P_i ∩ P_j = ∅ for all i ≠ j; (1.2) $P_{0} = ⋃_{i = 1}^{m} P_{i 0}$ is the set of process idle places; and (1.3) P_R = {r₁, r₂, …, rn_n} is the set of resource places.

$T = ⋃_{i = 1}^{m} T_{i}$ is the set of transitions, where T_i ∩ T_j = ∅ for all i ≠ j.

∀i ∈ Z_m, the subset N_i generated by P_i ∪ {p_i₀}and T_i is a strong connected state machine, and every circuit of N_i contains p_i₀.

∀p ∈ P, ∀t₁ ∈ ^•p, ∀t₂ ∈ p^•, ^•t₁ ∩ P_R = t₂^• ∩ P_R ={r}, we say that p requires r, denoted as R(p) = r.

∀r ∈ P_R, ^•^•r ∩ P = r^•^• ∩ P ≠ ∅, ^•r ∩ r ^•= ∅, and ^•^•(P₀) ∩ P_R = (P₀) ∩ P_R^•^• = ∅.

The initial marking M₀ satisfies that (6.1) ∀p ∈ P₀, M₀(p) > 0; (6.2) ∀r ∈ P_R, M₀(r) = Ψ(r), let Ψ(r) be the capacity of resource r; and (6.3) ∀p ∈ P, M₀(p) = 0.

For a resource r ∈ P_R, let H(r) denote the set of all operation places that require resource r, that is, H(r) = {p ∈ P | R(p) = r}. This notation can be extended to sets, for example, if R′ is a set of resources, H(R′) = ∪_r∈R′H(r). Let ^(p)t = ^•t∩P, ^(r)^•t = t ∩ P_R, and M ∈ R(N, M₀). t is said to be process-enabled (resource-enabled) at M if M(^(p)t) > 0 (M(^(r)t) > 0). Let Ξ(N) be the set of all SMSs in (N, M₀). For S ∈ Ξ(N), the complementary set of S is denoted as [S] = H(S_R)\S, where S_R = S∩P_R, S_P = S∩P.

An operation path in N is a path containing only operation places and transitions. Let x, y ∈ P ∪ T. x is previous to y if there exists an operation path from x to y, denoted as x ≤_Ny; in this case, we have x ≤_Nx. Let A ⊆ P ∪ T, we say that x ≤_NA if there exists a node y ∈ A such that x ≤_Ny, and A ≤_Nx if there exists a node y ∈ A such that y ≤_Nx.

Deadlock controller for S³PR

Let θ be a circuit in an S³PR (N, M₀) and M ∈ R(N, M₀). θ is called a RTC if it contains only resource places and transitions. Let ℑ[θ] and ℜ[θ] denote the set of all transitions and resource places in θ, respectively.

An RTC θ is a perfect RTC (PRTC) if it satisfies (^(p)ℑ[θ]) ^•= ℑ[θ]. Let ϑ(R₁) denote the set of all PRTC with resource set R₁. If θ₁, θ₂ ∈ R₁, then the union of θ₁ and θ₂ is a PRTC with resource set R₁, that is, θ₁ ∪ θ₂ ∈ ϑ(R₁). Therefore, ϑ(R₁) contains a unique maximal PRTC (MPC). Let ϑ(N) denote the set of all MPCs in N.

An MPC θ is said to be saturated at marking M if M(^(p)ℑ[θ]) = Ψ(ℜ[θ]). Let θ∈ϑ(N) and t ∈ T, t is called an input of θ if its firing increases the number of tokens in ^(p)ℑ[θ] and an output one if its firing decreases the number of tokens in ^(p)ℑ[θ]. Let I(θ) and O(θ) denote the sets of input and output transitions of θ, respectively.

It has been proved in Xing et al.²⁶ that there exists a one-to-one corresponding between Ξ(N) and ϑ(N). For θ ∈ ϑ(N), let g(θ) be the SMS corresponding to θ, then we have g(θ) = ℜ[θ] ∪ (H(ℜ[θ])\^•ℑ[θ]), and [g(θ)] = ^(p)ℑ[θ]; similarly, let h(S) be the MPC corresponding to S, then we have h(S) = N[S_R ∪ {^•S_R\S_P^•}], and N[S_R ∪ T(S)] be a subset of N generated by S_R ∪ {^•S_R\S_P^•}. Let I([S]) = I(θ) and O([S]) = O(θ) denote the sets of input and output transitions of [S], respectively.

Let (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) be an S³PR, and M ∈ R(N, M₀). M is safe if M₀ ∈ R(N, M). A transition t ∈ T at a safe marking M is safe if M[t > M′ and M′ is safe.

Definition 2

Let (N, M₀) be an S³PR, r ∈ P_R is a κ-resource if M₀(r) = 1 and there exists a sequence of MPCs θ_i (i∈ Z_k, k≥ 2) in ϑ(N) satisfying

{r} = ∩_{i∈Z_k}ℜ[θ_i];

T_i = {t | t∈ℑ[θ_i] ∩I(θ_i₊₁), ^(r)t = r} ≠∅, i∈Z_k and subscripts are mod k;

$T'_{i} = (ℑ [θ_{i}] \cap r) \ T_{i} = \emptyset$ or $\forall t \in T'$ , $(H (t^{(r)}) \cap^{(p)} ℑ [θ_{i}]) \^{(p)} T'_{i} = \emptyset$ , i∈Z_k, and subscripts are mod k.

A κ-resource is a one-unit resource shared by two or more MPCs in a special way. The following lemma states that if an S³PR contains no κ-resources, then every unsafe state in it is a deadlock.

Lemma 1

An S³PR (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) without κ-resources contains only two kinds of reachable markings: safe ones and deadlocks.⁸

From Lemma 1 we know that in order to avoid deadlocks in an S³PR without κ-resources, the controller only needs to forbid transitions firing that lead the system from safe markings to deadlocks. Such a controller can be designed as follows.

Definition 3

Let (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) be an S³PR without κ-resources.

1. Define a PN controller for S ∈ Ξ(N)

(C [S], {M_{S}}_{0}) = ({c_{S}}, T_{S}, F_{S}, {M_{S}}_{0})

where c_S is a control place corresponding to S, its initial marking is M_S₀(c_S) = Ψ(S_R) – 1, T_S = I([S]) ∪O([S]), and F_S = {(c_S, t) | t ∈ I([S])}∪{(t, c_S) | t∈O([S])}.

2. Define a PN controller for (N, M₀)

(C, {M_{C}}_{0}) = \otimes_{S} \in_{Ξ (N)} (C [S], {M_{S}}_{0})

Let (CN, M_CN₀) = (N, M₀) ⊗ (C, M_C₀) be the controlled PN, and M ∈ R(CN, M_CN₀), for S ∈ Ξ(N), {c_S} ∪ [S] is a support of p-invariant in (CN, M_CN₀), and for any M∈R(CN, M_CN₀), M(c_S) + M([S]) =M_C₀(c_S) = Ψ(S_R) – 1.

Lemma 2

Let (N, M₀) be an S³PR without κ-resources.⁸ Then, the controller (C, M_C₀) for it in Definition 3 is the optimal deadlock controller for (N, M₀).

Example 1

An AMS cell shown in Figure 1(a) can process two types of parts Δ₁ and Δ₂, each processing line consists of three machines r₁, r₂, and r₃ with capacities 1,2, and 3, respectively. Each machine can process one part at a time. Parts enter the cell through uploading buffer I and leave the cell through downloading buffer O. The processing routes for types Δ₁ and Δ₂ are r₁r₂r₃ and r₃r₂r₁, respectively. The cell can be modeled with PNs as Figure 1(b) shows, and the corresponding operation path in PN model are t₁p₂t₂p₃t₃p₄t₄ and t₅p₆t₆p₇t₇p₈t₈.

Figure 1.

(a) An AMS cell, (b) an S³PR, and (c) the controller.

The net shown in Figure 1(b) is an S³PR without κ-resources. It has three SMSs: S₁ = p₃p₈r₁r₂, S₂ =p₄p₇r₂r₃, and S₃ = p₄p₈r₁r₂r₃. This PN has 166 reachable markings with 154 safe markings in it. For siphon S₁, we have [S₁] = {p₂, p₇}, I([S₁]) = {t₁, t₆}, and O([S₁]) = {t₂, t₇}. For M ∈ R(CN, M_CN₀), M_C₀(c_S₁) +M_C₀([S₁]) is a p-invariant; hence, F_S₁ = {(c_S₁, t₁), (c_S₁, t₆), (t₂, c_S₁), (t₇, c_S₁)}.

Similarly, we can get I([S₂]) = {t₂, t₅}, O([S₂]) = {t₃, t₆}, I([S₃]) = {t₁, t₅}, and O([S₃]) = {t₃, t₇}. The optimal PN deadlock controller (C, M_C₀) in Definition 3 is shown in Figure 1(c). All 154 safe markings are reachable under the control of (C, M_C₀).

For S³PR with κ-resources, a κ-resources elimination method is proposed in Han et al.⁸ and Xing et al.¹⁴ for reducing κ-resources so that the reduced PN does not contain κ-resources but still falls into the class of S³PRs. This method is shown as follows.

Definition 4

Let (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) be an S³PR and r be a κ-resource. The reduced net of (N, M₀) on r is a PN (N_A, M_A₀) = (P_A ∪ P₀ ∪ P_AR, T_A, F_A, M_A₀) which can be obtained by the following steps.

Delete r and its related arcs from N, and let P_AR = P_R\{r}.

For each transition t ∈ P_AR^•∩^•r, for example, r₁ ∈ P_AR such that (r₁, t) ∈F and (t, r) ∈F, delete (r₁, t) from S³PR. Let p_f = ^(p)t. If |p_f^•| = 1, then ∀t_f ∈ p_f^•, add (r₁, t_f) if (t_f, r₁) ∉F or delete (t_f, r₁) if (t_f, r₁) ∈F, rename r₁ to mr₁ (mean as modified resource place), and let R(κ) be the set of all modified resources. If |p_f^•| = k > 1, let p_f^• = {t₁, t₂, …, t_k} and ^(r)t_i = r_i, i∈Z_k, and then, replace p_f with k operation places, ∀t_f ∈ p_f, delete p_f^• and its related arcs and add k operation places, denoted as p_f₁, p_f₂, …, p_fk. Let p_f₀ = ^(p)t_f, R(p_f₀) = r_f. Delete t_f and its related arcs, add k transitions, denoted as t_f₁, t_f₂, …, t_fk (in this case, we will say that t_f is separable and is separated into t_f₁, t_f₂, …, t_fk), and add arcs (p_f₀, t_fi), (t_fi, p_fi), (p_fi, t_i), (r_i, t_fi), and (t_fi, r_f), i∈Z_k. Let T_f⊆T denote the set of all separable transitions in N. If for a resource place r′ and a transition place t′ such that (r′, t′) and (t′, r′) exist at the same time, then delete (r′, t′) and (t′, r′).

After steps 1 and 2, the sets of all the existing operation places, transitions, and arcs are denoted as P_A, T_A, and F_A, respectively. M_A₀ is the initial marking of N_A, under which only places in P₀∪P_AR are marked as in (N, M₀).

Then, a deadlock supervisory policy for S³PR with κ-resources can be defined as follows.

Definition 5

Let (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) be an S³PR and r be a κ-resource. (N_A, M_A₀) be the reduced PN without κ-resource, (Cr, M_Cr₀) be the optimal deadlock prevention controller of (N_A, M_A₀), and let (CN_A, M_CA₀) = (N_A, M_A₀) ⊗ (Cr, M_Cr₀). Define a supervisory policyζ as follows.

∀t∈T\T_f, ζ permits firing of t in (N, M₀) ⇔t can be fired in (CN_A, M_CA₀). t fires in (N, M₀) and (CN_A, M_CA₀) at the same time.

∀t_f∈T_f, ζ permits firing of t_f in (N, M₀) ⇔ one of t_f₁–t_fk can be fired in (CN_A, M_CA₀), where t_f is separated into k transitions t_f₁–t_fk, t_f fires a time ⇔ one of t_f₁–t_fk fires once in (CN_A, M_CA₀).

Let ζ||(N, M₀) denote (N, M₀) supervised under ζ. Then, ζ is the liveness supervisor for (N, M₀).

PN-based deadlock analysis for AMS with single type of unreliable resources

In this section, we first develop a PN model of the considered AMS with single type of unreliable resources and then analyze its liveness.

Let A(r_u) denote the considered AMS with single type of unreliable resources r_u. Note that in the absence of resource failures, A(r_u) can be modeled by an S³PR, while the resource failure and recovery activities can be modeled by the so-called failure and recovery net (FRN) defined as follows.

Definition 6

Let (N, M₀) = (P ∪ P₀ ∪ P_R, T, F, M₀) be the S³PR modeling A(r_u) in the absence of resource failures. The FRN of r_u is defined as (N_u, M_u₀) = (H(r_u) ∪ Q, T_P ∪ T_Q, F_u, M_u₀), where Q = {q_i | q_i is a resource recovery place corresponding to p_i∈H(r_u)}, T_P = {t_pi | t_pi is a transition corresponding to the resource failure in p_i∈H(r_u)}, and T_Q = {t_qi | t_qi is a transition corresponding to the resource recovery in q_i}. F_u = {(p_i, t_pi), (t_pi, q_i), (q_i, t_qi), (t_qi, p_i) | p_i∈H(r_u)} and M_u₀(q_i) = M_u₀(p_i) = 0, where p_i∈H(r_u).

Then, all activities in AMS can be modeled by (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀), called as the unreliable S³PR model of A(r_u) or US³PR for short.

Let M∈R(N_U, M_U₀) be a reachable marking of US³PR (N_U, M_U₀), in this article, we define M_N be the marking of (N, M₀) at M, and M_U be the marking of (N_u, M_u₀) at M, and then, M can be rewritten as M = (M_N, M_U).

Let us reconsider S³PR shown in Figure 1(b). Assume that r₃ is unreliable since H(r₃) = {p₄, p₆}, we know that Q = {q₄, q₆}, T_P = {t_p₄, t_p₆}, and T_Q = {t_q₄, t_q₆}. For S₁ = {p₃, p₈, r₁, r₂}, Q_S₁ = Q_[S1] = ∅; similarly, for S₂ = {p₄, p₇, r₂, r₃}, Q_S₂ = {q₄} and Q_[S2] = {q₆}; and for S₃ = {p₄, p₈, r₁, r₂, r₃}, Q_S₃ = {q₄} and Q_[S3] = {q₆}. The US³PR is shown in Figure 2.

Figure 2.

A US³PR.

In the remaining discussion, for an US³PR (N_U, M_U₀), Ξ(N) only denotes those SMSs in (N, M₀). For S ∈ Ξ(N), let Q_S = {q∈Q | ^•q∩S^•≠∅} and Q_[S] = {q∈Q |^•q∈ [S]^•}. Then, if r_u∉S, Q_S = Q_[S] = ∅; else, if r_u ∈ S, Q_[S] ∪ Q_S = Q.∀M ∈ R(N_U, M_U₀), M_U₀(S) = M(S) + M([S]) + M(Q_[S]) + M(Q_S).

In this work, our AMS control objective is to ensure that any kind of parts can be processed continuously through any one of their process routes even if some unreliable resource units fail. To this end, a kind of so-called robust controller is developed, and the concept of its RL is introduced. The RL of such a controller represents the number of how many units of failed resources can be tolerated by the controlled system, and it can be formally defined as follows.

Definition 7

Let (N_U, M_U₀) be the US³PR model of A(r_u), Λ be a controller for (N_U, M_U₀) and Λ||(N_U, M_U₀) be the controlled system. Then, for a integer k, Λ is called as a deadlock controller with robust level k or a k-robust controller for short, and if in the controlled system Λ||(N_U, M_U₀), the following occurs:

Any kind of parts can be processed continuously through any one of their process routes when at most k units of r_u fail;

When failed resources are repaired, they can be returned to the system, and their return would not affect the continuous processing of any kind of parts.

Note that if all units of r_u fail, it is impossible to achieve the control objective. So, we assume that at any reachable markings of the unreliable system, at least one unit of r_u can work normally. From Definition 7, we know that a deadlock controller for (N, M₀) is a 0-robust controller for (N_U, M_U₀). For example, the controller (C, M_C₀) in Definition 3 is a 0-robust controller for (N_U, M_U₀).

A (k + 1)-robust controller is also k-robust, and all k-robust controllers are 0-robust. But the converse is not true. This can be shown in the following example.

Example 2

Consider (N_U, M_U₀) = (N, M₀)⊗(N_u, M_u₀) shown in Figure 2, where r_u = r₃. The optimal deadlock controller for (N, M₀) is (C, M_C₀) as shown in Figure 1(c). It can be checked that (C, M_C₀) is 0-robust, but not 1-robust for (N_U, M_U₀), since (N_CU, M_CU₀) = (N_U, M_U₀)⊗(C, M_C₀) can reach marking M₁ as shown in Figure 3. At M₁, one unit of r₃ fails, M₁(q₄) = 1, and tokens in both process routes cannot move forward until the failed resource is repaired. Such a blockage is related to resource failures and the applied controller.

Figure 3.

A reachable marking in the controlled net.

In this article, for the US³PR controlled by a 0-robust controller, reachable markings like M₁ in Example 2 are called as BSs, formally defined as follows.

Definition 8

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be the US³PR model of A(r_u), (C, M_C₀) be a 0-robust controller for (N_U, M_U₀), (N_CU, M_CU₀) = (N_U, M_U₀) ⊗ (C, M_C₀) and M∈R(N_CU, M_CU₀), and M = (M_N, M_U, M_C), where M_N, M_U, and M_C are markings of N, N_u, and C, respectively. Then, M is called a BS if (1) 0 < M(Q) < Ψ(r_u) and (2) M_N is a deadlock marking of (N, M_N).

For (N_U, M_U₀) and M∈R(N_U, M_U₀), let R_TP(N_U, M) = {M′ | ∃α∈ (T∪T_P)* such that M [α > M′}. That is, R_TP(N_U, M) is the set of reachable markings from M under the condition that no resource recovery happens. Then according to Definition 8, we can infer that for M ∈ R(N_U, M_U₀), if there are no dead transitions at any marking of R_TP(N_U, M), then M is not a BS.

In Definition 8, condition (1) indicates that at any BS, at least one unit of unreliable resources has failed and condition (2) shows that the S³PR part of the US³PR has trapped into deadlock states because of resource failures, that is, unless at least one failed resources is repaired, the production on some processing route pauses. Take state M₁ in Figure 3 as an example, we can see that M₁(Q) = 1 > 0, and SMS S₁ is empty at M_1N, that is, M_1N(S₁) = 0, and all transitions in T are not enabled at any marking in R(N, M_N).

There are mainly two differences between BSs and deadlocks. (1) BSs only occur when some units of unreliable resource are failed, while deadlocks may occur no matter whether resource failure happen or not. (2) BSs would not cause permanent blockage of the system, when the failure units are repaired and return to the system, those blocked process routes can be resumed, while deadlocks cause permanent blockage of the entire system.

For the US³PR controlled by a 0-robust controller, though all the deadlocks in (N, M₀) are forbidden, the existence of BSs pauses some processing routes, and hence, such a controller cannot achieve the proposed control objective. Therefore, both BSs and deadlocks should be forbidden by ideal robust controllers.

Now, let us characterize BSs in the controlled US³PR with the controller proposed in Definition 3. For (N_CU, M_CU₀) = (N_U, M_U₀) ⊗ (C, M_C₀), where (C, M_C₀) is the optimal controller for (N, M₀) in Definition 3. If M∈R(N_CU, M_CU₀) is a BS, according to Definition 8, M_N is a deadlock marking of N. Since a marked S³PR is live if and only if all siphons in it are not empty at any reachable markings, we have the following lemma.

Lemma 3

Let (N_CU, M_CU₀) = (N_U, M_U₀)⊗(C, M_C₀), where (N_U, M_U₀) is an US³PR and (C, M_C₀) is its optimal 0-robust controller for (N, M₀), M∈R(N_CU, M_CU₀) and M is a BS. Then, there exists an SMS S∈Ξ(N) such that M_N(S) = 0.

Proof

Since M is a BS, according to Definition 8, M_N is a deadlock marking of (N, M_N). Notice that a marked S³PR is live if and only if all siphons in it are not empty at any reachable markings. Then, there must exist an empty SMS at M_N. Therefore, there exists an SMS S∈Ξ(N) such that M_N(S) = 0.♣

According to Lemma 3, if all SMSs in (N_CU, M_CU₀) are controlled to be not empty even if resource failures happen, all BSs can be forbidden.

According to whether SMSs contain places in H(r_u), Ξ(N) can be divided into two disjoint subsets Ξ₁ and Ξ₂, where Ξ₁ = {S | S∈Ξ(N), r_u∈S, H(r_u) ∩S≠∅}, and Ξ₂ = Ξ(N)\Ξ₁. Then φ[S] = [S] ∪H(r_u) if S∈Ξ₁; φ[S] = [S] if S∈Ξ₂.

Take US³PR in Figure 2 as an example. There are three SMSs in (N, M₀): S₁ = {p₃, p₈, r₁, r₂}, S₂ = {p₄, p₇, r₂, r₃}, and S₃ = {p₄, p₈, r₁, r₂, r₃}. r₃ is unreliable, and H(r₃) = {p₄, p₆}. Then, Ξ₁ = {S₂, S₃} and Ξ₂ = {S₁}, φ[S₁] = [S₁] = {p₂, p₇}, φ[S₂] = [S₂] ∪H(r₃) = {p₃, p₄, p₆}, and φ[S₃] = [S₃] ∪H(r₃) = {p₂, p₃, p₄, p₆, p₇}.

From Definition 3, we can know that {c_S∪ [S] ∪Q_[S]} is the support of p-invariant in the controlled PN (N_CU, M_CU₀), and hence, for M∈R(N_CU, M_CU₀), M(c_S) + M([S]) + M_U(Q_[S]) = M_CU₀(c_S) = Ψ(S_R) − 1. If M is a BS, according to Lemma 3, there exists an S ∈ Ξ(N) such that M_N(S) = 0. Then, M_U(Q_S) = M_CU₀(S) − (M([S]) + M_U(Q_[S])) = M(c_S) + 1 > 0. That is, for (N_CU, M_CU₀) and S ∈ Ξ(N), due to the fact that operation places in H(r_u) ∩ S are not restricted, S may still be empty even if the number of tokens in [S] is no more than Ψ(S_R) − 1.

Based on the discussions above, in order to forbid BSs and deadlocks, a robust controller should ensure that S\(H(r_u) ∩ S) would not be empty, that is, the number of tokens in φ[S] should be limited.

Robust controllers design

Let (N_U, M_U₀) = (N, M₀)⊗(N_u, M_u₀) be an US³PR. If (N, M₀) does not contain κ-resources, for convenience, we also say that (N_U, M_U₀) has no κ-resources.

In the following, we first develop robust controllers for an US³PRs without κ-resources and then for general US³PRs.

Robust controller for US³PR without κ-resources

For φ[S] = [S] ∪ (H(r_u) ∩S), let ω(S) = {p | p∈P, p≤_Nφ[S]} be the set of operation places which are previous to φ[S], and then, t is called an input of ω(S) if its firing increases the number of tokens in ω(S) and an output one if its firing decreases the number of tokens in ω(S). Let I(ω(S)) and O(ω(S)) denote the sets of input and output transitions of ω(S), respectively.

For an US³PR without κ-resources, its PN controller is defined as follows.

Definition 9

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be an US³PR without κ-resources.

1. Define a PN controller for S∈Ξ₁

(K [S], {M_{K}}_{0}) = ({p_{S}}, T_{S}, F_{S}, {M_{K}}_{0})

where p_S is a control place corresponding to S, its initial marking is M_K₀(p_S) = Ψ(S) − 1, and T_S = I(ω(S)) ∪O(ω(S)) and F_S = {(p_S, t) | t∈I(ω(S))} ∪ {(t, p_S) | t∈O(ω(S))}.

2. Define a PN controller for S∈Ξ₂

(K [S], {M_{K}}_{0}) = (C [S], {M_{S}}_{0})

where (C[S], M_S₀) is the controller in Definition 3.

3. Define a PN controller for (N_U, M_U₀)

(K, M_{K 0}) = \otimes_{S} \in_{Ξ (N)} (K [S], M_{K 0}) = (P_{K}, T_{K}, F_{K}, M_{K 0})

Then, the controlled PN is (N_C, M_C₀) = (K, M_K₀) ⊗ (N_U, M_U₀).

Example 3

Consider US³PR (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) shown in Figure 2, and r_u = r₃. Note that (N, M₀) contains no κ-resource and has three SMSs: S₁ = {p₃, p₈, r₁, r₂}, S₂ = {p₄, p₇, r₂, r₃}, and S₃ = {p₄, p₈, r₁, r₂, r₃}. Then, Ξ₁ = {S₂, S₃}, and Ξ₂ = {S₁}; ϕ[S₁] = {p₂, p₇}, φ[S₂] = {p₃, p₄, p₆}, and φ[S₃] = {p₂, p₃, p₄, p₆, p₇}. Its controller in Definition 9 is designed as follows. Let p_S₂ and p_S₃ be their control places for S₂ and S₃, we have ω(S₂) = {p₂, p₃, p₄, p₆}, ω(S₃) = {p₂, p₃, p₄, p₆, p₇}, I(ω(S₂)) = {t₁, t₅}, O(ω(S₂)) = {t₄, t₆}, I(ω(S₃)) = {t₁, t₅}, and O(ω(S₃)) = {t₄, t₇}. F_S₂ = {(p_S₂, t₁), (p_S₂, t₅), (t₆, p_S₂), (t₄, p_S₂)} and F_S₃ = {(p_S₃, t₁), (p_S₃, t₅), (t₄, p_S₃), (t₇, p_S₃)}. The controller for S₁ is the same as defined in Definition 3. Then, the controlled PN is shown in Figure 4.

Figure 4.

The controlled system with our robust controllers.

Let H(p_S) = {p∈P | (p_S^•≤_N p) ∧ (p≤_N^•p_S)}, then according to the definition of controller, if S contains no operation places of H(r_u), H(p_S) = ω(S). In (N_C, M_C₀), the number of tokens in H(p_S) ∪Q∪ {p_S} is a constant, that is, for M∈R(N_C, M_C₀) and S∈Ξ(N), we have M(p_S) +M(H(p_S)) + M(Q_[S]) + M(Q_S) = M_C₀(p_S).

Let (C, M_C₀) = ⊗_S∈Ξ(N)(C[S], M_S₀) be the controller in Definition 3 and (K, M_K₀) be the controller in Definition 9. According to Definition 9, ⊗_S∈Ξ2(K(S), M_K₀) = ⊗_S∈Ξ2(C(S), M_S₀). Besides, note that ∀S∈Ξ₁, M_K₀(p_S) = M_S₀(c_S), and H(c_S) ⊆H(p_S), and then, we can know that for ⊗_S∈Ξ1{(C[S], M_S₀) ⊗ (K[S], M_K₀)}, controllers in ⊗_S∈Ξ1(C[S], M_S₀) are redundant and can be omitted. Hence, (C, M_C₀)⊗_S∈Ξ1(K[S], M_K₀) = ⊗_S∈Ξ2(C[S], M_S₀) ⊗_S∈Ξ1(C[S], M_S₀) ⊗_S∈Ξ1(K[S], M_K₀) = ⊗_S∈Ξ2(K[S], M_K₀)⊗_S∈Ξ1(K[S], M_K₀) = (K, M_K₀).

The following lemma states that all SMSs in Ξ(N) cannot be emptied in the controlled PN.

Lemma 4

For M∈R(N_C, M_C₀) and S∈Ξ(N), we have M(S) > 0.

Proof

Let M_A∈R(N_C, M_C₀), then M_C₀(S) =M_A(S) + M_A([S]) + M_A(Q_[S]) + M_A(Q_S). Note that [S] ⊆H(p_s), we can get M_A([S]) ≤M_A(H(p_s)), and hence, M_C₀(S) ≤M_A(S) + M_A(H(p_s)) + M_A(Q_[S]) +M_A(Q_S). Meanwhile, we know that M_A(H(p_s))+M_A(Q_[S])+M_A(Q_S) = M_C₀(p_S) –M_A(p_S) = M_C₀(S) − 1 −M_A(p_S), then M_C₀(S) ≤M_A(S) + M_C₀(S) − 1 −M_A(p_S), simplify this inequality we can get M_A(S) ≥ 1 + M_A(p_S) > 0. Therefore, Lemma 4 is proved.♣

The next lemma shows that there are no BSs and deadlocks in (N_C, M_C₀).

Lemma 5

Let (K, M_K₀) be the controller proposed in Definition 9, and (N_C, M_C₀) = (K, M_K₀)⊗(N_U, M_U₀), and then, there are no BSs and deadlocks in (N_C, M_C₀).

Proof

Since (K, M_K₀) = (C, M_C₀) ⊗_S∈Ξ1(K[S], M_K₀), we have (N_C, M_C₀) = (N_U, M_U₀) ⊗ (C, M_C₀) ⊗_S∈Ξ1(K[S], M_K₀).

First, we prove that (N_C, M_C₀) has no deadlocks. Note that all output arcs of ⊗_S∈Ξ1(K[S], M_K₀) are point to P₀^•, and then, controllers in ⊗_S∈Ξ1(K[S], M_K₀) would not generate new emptied SMSs, thus controllers in ⊗_S∈Ξ1(K[S], M_K₀) would not generate any BSs or deadlocks. Due to the fact that (N_U, M_U₀) ⊗ (C, M_C₀) has no deadlocks, and controllers in ⊗_S∈Ξ1(K[S], M_K₀) would not generate any new deadlocks, we can conclude that (N_C, M_C₀) has no deadlocks.

Second, we prove that (N_C, M_C₀) has no BSs. According to Definition 8, we can know that each BSs corresponds to an empty SMS, note that controllers in ⊗_S∈Ξ1(K[S], M_K₀) would not generate any new SMSs, so controllers in ⊗_S∈Ξ1(K[S], M_K₀) generate no new BSs. Then, Lemma 3 and Lemma 4 shows that all BSs in (N_U, M_U₀)⊗(C, M_C₀) are forbidden in (N_C, M_C₀). As a result, (N_C, M_C₀) has no BSs.♣

Now, we can prove our main result: the controller proposed in Definition 9 is (Ψ(r_u) − 1)-robust.

Theorem 1

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be an US³PR without κ-resources. Then, the controller (K, M_K₀) for (N_U, M_U₀) designed in Definition 9 is (Ψ(r_u) − 1)-robust.

Proof

Let (N_C, M_C₀) = (K, M_K₀) ⊗ (N_U, M_U₀), since in this article, at most Ψ(r_u) − 1 units of unreliable resource r_u can fail at a marking, the controller is at most (Ψ(r_u) − 1)-robust. According to Definition 9, we can know that when those failed resources are repaired and return to the system, the number of tokens in the related SMS has increased, and in this case, their return would not affect the continuous processing of any kind of parts. Then, based on Definition 7, in order to prove that (K, M_K₀) is (Ψ(r_u) − 1)-robust, we only need to prove that for M∈R(N_C, M_K₀), there are no dead transitions at any marking of R_TP(N_C, M).

Let M_τ∈R_TP(N_C, M). If M_τ(P) = 0, it is easy to know that there are no dead transitions at M_τ. Otherwise, if M_τ(P) > 0, according to the fact that all BSs and deadlocks in (N_C, M_C₀) are forbidden, we can know that there are no deadlocks in N at marking M_τ. Thus, there exists a transition t₁ ∈ T\P₀ that can be fired. Let M_τ[t₁ > M_υ, iterating this reasoning, there must exist a sequence η₁ such that M_τ[η₁ > M_B with M_B(P) = M_τ(P) − 1. By mathematical induction for the number of tokens in P, we can conclude that there exists a sequence η₂ such that M_τ[η₂ > M_C with M_C(P) = 0. In other words, there are no dead transitions at any markings of R_TP(N_C, M). Hence, according to Definition 7, we can conclude that (K, M_K₀) is (Ψ(r_u) − 1)-robust.♣

Robust supervisor for US³PR withκ-resources

If (N_U, M_U₀) has κ-resources, the robust controller in Definition 9 cannot be directly used. In this situation, the κ-resource elimination method proposed in Definition 4 is used to obtain a reduced S³PR (N_A, M_A₀). Since the capacity of the unreliable resource is larger than one, no unreliable resources are κ-resources, and this means that the FRN of r_u, (N_u, M_u₀), is also suitable for (N_A, M_A₀). In view of the fact that (N_A, M_A₀) ⊗ (N_u, M_u₀) has no κ-resources, the proposed robust controller in Definition 9 can be used to the reduced PN. For (N_A, M_A₀) ⊗ (N_u, M_u₀), let (K_A, M_AK₀) be the robust controller designed by Definition 9, and then, similar to Definition 5, a robust supervisory policy can be defined as follows.

Definition 10

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be an US³PR with κ-resources. (N_A, M_A₀) be the reduced PN of (N, M₀) without κ-resources, T_f be the set of separable transitions, (K_A, M_AK₀) be the designed (Ψ(r_u) − 1)-robust controller for (N_A, M_A₀) ⊗ (N_u, M_u₀), and let (N_AC, M_AC₀) = (N_A, M_A₀) ⊗ (N_u, M_u₀) ⊗ (K_A, M_AK₀). Define a supervisory policy χ as follows.

∀t∈T\T_f, χ permits firing of t in (N_U, M_U₀)⇔t can be fired in (N_AC, M_AC₀); t fires in (N_U, M_U₀) and (N_AC, M_AC₀) at the same time.

∀t_f∈T_f, χ permits firing of t_f in (N_U, M_U₀) ⇔ one of t_f_{1 −}t_fk can be fired in (N_AC, M_AC₀), where t_f is separated into k transitions t_f_{1 −}t_fk; t_f fires a time in (N_U, M_U₀) ⇔ one of t_f_{1 −} t_fk fires once in (N_AC, M_AC₀).

Moreover, if there exist no separable transitions in (N_A, M_A₀), that is, T_f = ∅, then according to Definition 10, a transition t can be fired under χ if and only if it can be fired in (N_U, M_U₀) ⊗ (N_AC, M_AC₀). In this case, the supervisory policy χ in Definition 10 can be considered as a controller as follows.

Definition 11

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be an US³PR with κ-resources. (N_A, M_A₀) be the reduced model of (N, M₀), T_f = ∅, and R(κ) be the set of modified resources. Then, the subset of modified resources, (N_κ, M_κ0) = N[R(κ), R(κ)^•∪^•R(κ)], is a subset generated by places in R(κ), transitions in R(κ)^•∪^•R(κ) and related arcs.

Definition 12

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be an US³PR with κ-resources. (N_A, M_A₀) be the reduced model of (N, M₀) and (N_A, M_A₀) contains no κ-resources, T_f = ∅, and (K_A, M_AK₀) be the (Ψ(r_u) − 1)-robust controller designed by Definition 9. Then, (K_A, M_AK₀) ⊗ (N_X(κ), M_X₀) is a robust controller for (N_U, M_U₀).

Definitions 11 and 12 show that for (N_U, M_U₀) with κ-resources, if there exists no separable transitions in its reduced S³PR (N_A, M_A₀), all the modified resources in (N_A, M_A₀) can be considered as control places of (N_U, M_U₀), so the robust controller for (N_U, M_U₀) is (K_A, M_AK₀) ⊗ (N_κ, M_κ₀), where (K_A, M_AK₀) is the (Ψ(r_u) − 1)-robust controller for (N_A, M_A₀) ⊗ (N_u, M_u₀). An example (Example 5) is given to illustrate this situation.

In the following, we will prove that for US³PR with κ-resources, χ is a (Ψ(r_u) − 1)-robust supervisory policy.

Theorem 2

Let (N_U, M_U₀) = (N, M₀) ⊗ (N_u, M_u₀) be an US³PR with κ-resources, (N_A, M_A₀) be the reduced model without κ-resources, (K_A, M_AK₀) be the robust controller for (N_A, M_A₀) ⊗ (N_u, M_u₀), and χ be the supervisory policy in Definition 10. Then, χ is a (Ψ(r_u) − 1)-robust supervisory policy.

Proof

Assume, on the contrary, that ζ′ is not a (Ψ(r_u) − 1)-robust supervisory policy. In this case, ∃M′∈R(χ||(N_U, M_U₀)) and a transition t′∈T, such that t′ is not enabled at any marking of R_TP(χ||(N_U, M_U₀), M′).

Let (N_AC, M_AC₀) = (N_A, M_A₀) ⊗ (N_u, M_u₀) ⊗ (K_A, M_AK₀) be the reduced controlled PN. Note that (K_A, M_AK₀) is (Ψ(r_u) − 1)-robust for (N_A, M_A₀) ⊗ (N_u, M_u₀); according to Definition 7, we can know that there are no dead transitions in R_TP(N_AC, M′). Considering that a transition can be fired under χ if and only if it can be fired in both (N_AC, M_AC₀) and (N_U, M_U₀), then at M′, transition t′ is enabled in (N_AC, M_AC₀) but disabled in (N_U, M_U₀). Then, according to Definitions 4 and 10, there must exist a κ-resource r′ ∈ ^•t′ such that ∀M∈R_TP(ζ′||(N_U, M_U₀), M′), M(r′) = 0. This means that if the κ-resource r′ is occupied, (N_AC, M_AC₀) cannot make sure that r′ can be released, that is, (N_AC, M_AC₀) is not (Ψ(r_u) − 1)-robust. However, based on Theorem 1, this is impossible. Hence, χ is a (Ψ(r_u) −1)-robust supervisory policy.♣

Examples and discussion

Example 4

Consider the US³PR with unreliable resource r₄ shown in Figure 5. Ξ(N) = {S₁, S₂, …, S₇}, where S₁ = {p₃, p₅, p₁₀, p₁₂, r₂, r₃, r₄}, S₂ = {p₃, p₅, p₉, p₁₃, r₃, r₄, r₅}, S₃ = {p₅, p₈, r₁, r₃}, S₄ = {p₃, p₅, p₁₀, p₁₃, r₂, r₃, r₄, r₅}, S₅ = {p₅, p₉, p₁₃, r₁, r₃, r₄, r₅}, S₆ = {p₅, p₁₀, p₁₂, r₁, r₂, r₃, r₄}, and S₇ = {p₅, p₁₀, p₁₃, r₁, r₂, r₃, r₄, r₅}. It can be checked that this net has no κ-resources.

Figure 5.

US³PR of Example 4.

Note that H(r₄) = {p₉, p₁₂}, we have Ξ₁ = {S₁, S₂, S₅, S₆} and Ξ₂ = {S₃, S₄, S₇}. According to Definition 9, the robust controller is shown as follows:

p_S ₁: ^•p_S₁ = {t₂, t₉, t₁₂}, p_S₁^• = {t₁, t₆, t₁₁}, M_C₀(p_S₁) = 5;

p_S ₂: ^•p_S₂ = {t₉, t₁₂}, p_S₂^• = {t₆, t₁₁}, M_C₀(p_S₂) = 5;

p_S ₃: ^•p_S₃ = {t₄}, p_S₃ ^•= {t₂}, M_C₀(p_S₃) = 2;

p_S ₄: ^•p_S₄ = {t₂, t₉, t₁₂}, p_S₄^• = {t₁, t₆, t₁₁}, M_C₀(p_S₄) = 7;

p_S ₅: ^•p_S₅ = {t₄, t₉, t₁₂}, p_S₅^• = {t₁, t₆, t₁₁}, M_C₀(p_S₅) = 7;

p_S ₆: ^•p_S₆ = {t₄, t₉, t₁₂}, p_S₆ ^•= {t₁, t₆, t₁₁}, M_C₀(p_S₆) = 7;

p_S ₇: ^•p_S₇ = {t₄, t₉, t₁₂}, p_S₇^• = {t₁, t₆, t₁₁}, M_C₀(p_S₇) = 9;

Since ^•p_S₁ =^• p_S₄, p_S₁^• = p_S₄^•, M_C₀(p_S₁) < M_C₀(p_S4), compared with p_S₁, the control place p_S₄ is redundant and can be omitted. Similarly, compared with p_S₅, p_S₆ and p_S₇ are also redundant and can be omitted. In this case, the robust controller proposed in this article has only four control places: {p_S₁, p_S₂, p_S₃, p_S₅}. In this example, Ψ(r₄) = 3, so the proposed controller is 2-robust. The controlled PN is shown in Figure 6.

Figure 6.

The controlled PN.

Example 4 discussion

In this example, the US³PR in Figure 5 has 12168 reachable markings, including 1317 BSs and deadlock states.

Table 1 shows a performance comparison between the controller proposed in this article with some controllers in the literature for this example.

Table 1.

Performance comparison of some controllers.

Controllers	Δ_R	Δ_B	Δ_C	RL
Ezpeleta et al.⁷	8413	46	7	0
Liu et al.¹⁰	8123	20	3	0
Han et al.⁸	10,941	90	4	0
Feng et al.¹⁶	8152	47	3	1
Wu et al.²¹	7885	0	4	1
Proposed controller	9567	0	4	2

Δ_R: no. of reachable markings in controlled system; Δ_B: no. of BSs in controlled system; Δ_C: no. of control places.

From Table 1, we can see that the controlled PNs with controllers in Ezpeleta et al.,⁷ Han et al.,⁸ and Liu et al.¹⁰ have 46, 90, and 20 BSs, respectively. Thus, controllers in Ezpeleta et al.,⁷ Han et al.,⁸ and Liu et al.¹⁰ are not robust. Although they can prevent all deadlocks, since any of the BSs can cause an unexpected and unpredictable disruption, these controllers are not suitable for real systems with unreliable resources.

Among the three robust controller in Feng et al.,¹⁶ Wu et al.,²¹ and this work, Feng et al.¹⁶ is only suitable for one unit failure case, when multiple resources are failed, such as in this example, the controller in Feng et al. could not prevent all BSs, which causes a lot of restrictions on the application of the controller. Wu et al.²¹ can only achieve 7885 reachable markings, and owing to the fact that all of the output arcs of its control places are pointed to the source transitions, the restrictions of the controller are too strict, and many safe states are prohibited, in this case its control performance is not very good. While the controller in this work leads to 9567 reachable markings with only four control places, it has the best permissive behavior in these robust controllers; moreover, among those controllers in Table 1, only the controller in this work can achieve 2-robust.

We can see that the proposed controller in this work has two major advantages:

The proposed controller permits more reachable markings than controllers in Feng et al.¹⁶ and Wu et al.²¹

The proposed controller has the highest RL, while other controllers are not suitable for multi-resource failure cases. Besides, if the capacity of unreliable resource increases, the proposed controller can still be applied to the changed PN by increasing the capacity of related control places.

In conclusion, the proposed controller in this work is a highly permissive robust controller with high degree of robustness.

Example 5

In order to show the application of the proposed method for US³PR with κ-resources, we consider an example shown in Figure 7(a). In Figure 7(a), the unreliable Petri net (N_U, M_U₀) = (N, M₀)⊗(N_u, M_u₀), where r₂ is a κ-resource and r₁ is unreliable, H(r₁) = {p₂, p₉, p₁₁}.

Figure 7.

(a) An US³PR example. (b) The reduced PN. (c) The controlled reduced PN with robust controller. (d) The robust controller for the US³PR.

Since r₂ is a κ-resource, the κ-resource elimination method in Definition 4 is used to get a reduced PN, that is, (1) delete r₂ and its related arcs from N; (2) note that in ∈r₂∩r₃, then delete (r₃, t₃) and add (r₃, t₂) from N; similarly, delete (r₁, t₇) and add (r₁, r₆) from the S³PR. Meanwhile, r₁ and r₃ are replaced to mr₁ and mr₃ to show that their arcs have been modified. The final reduced PN is shown in Figure 7(b).

For the reduced PN shown in Figure 7(b), since p₃ and p₄ require the same modified resource mr₂, they can be considered as one operation place, and {p₈, p₉} can also be considered as one place. Thus the reduced PN can be considered as an S³PR.

In the reduced S³PR, there is only one SMS: S = {p₃, p₄, p₈, p₉, mr₁, mr₃}. Since r₁ is unreliable and H(r₁) = H(r₁) = {p₂, p₉, p₁₁}, we can know that Ξ₁ = {S} and Ξ₂ = ∅, and then, ϕ[S] = [S] ∪H(r₁) = {p₂, p₇, p₉, p₁₁}. According to Definition 9, control place, p_S, is added, M_C₀(p_S) = 4 and F_K = {(p_S, t₁), (p_S, t₅), (p_S, t₉), (t₂, p_S), (t₈, p_S), (t₁₀, p_S)}. The controlled PN for the reduced S³PR is shown in Figure 7(c). Notice that there is no separable transitions in the reduced S³PR, and then, according to Definitions 11 and 12, the modified resources {mr₁, mr₃} and their related arcs can be considered as control places for the S³PR in Figure 7(a). The final controlled PN, with three control places {mr₁, mr₃, p_S}, is shown in Figure 7(d).

Example 5 discussion

This US³PR has 3341 reachable markings, including 357 BSs and deadlock states, thus only 2984 reachable markings are acceptable.

By Example 4, we can know that controllers in Ezpeleta et al.,⁷ Han et al.,⁸ and Liu et al.¹⁰ are not robust controller; hence, in this example, they are no longer included in the comparative scope. Table 2 gives the performance comparison of prior-mentioned three robust controllers.

Table 2.

Performance comparison of some robust controllers.

Controllers	Δ_R	Δ_B	Δ_C	RL
Feng et al.¹⁶	2347	36	3	1
Wu et al.²¹	1586	0	5	1
Proposed controller	2232	0	3	2

Δ_R: no. of reachable markings in controlled system; Δ_B: no. of BSs in controlled system; Δ_C: no. of control places.

Compared with Wu et al.,²¹ the proposed controller can achieve more acceptable markings (2232 in this work vs 1586 in Wu et al.²¹) while using significantly less control places (3 in this work vs 5 in Wu et al.²¹). This means that even for systems with κ-resources, the proposed controller in this article is still more permissive than Wu et al.²¹ Besides, in terms of robust level, the controller in Wu et al.²¹ is only 1-robust, while the proposed controller is Ψ(r_u) −1-robust, considering the fact that at most Ψ(r_u) − 1 units of resources are failed at one time, the proposed controller has the highest RL.

Compared with Feng et al.,¹⁶ it seems that in this example, the proposed controller in this work permits no more reachable markings than the one in Feng et al.,¹⁶ and this is due to the fact that the US³PR contains κ-resources, so the κ-resource elimination method is used, which prohibit some safe markings. Still, from Table 2, we can see that the proposed controller can forbid all BSs, while the approach in Feng et al.¹⁶ is only suitable for one resource failure case. For a robust controller, its most important evaluation indicator is whether it can prohibit all BSs and deadlocks. For this reason, we consider that the proposed controller is a more permissive and effective robust controller than the one in Feng et al.¹⁶

We can see that the proposed controller in this work has the most important advantages: it has the highest RL. Among these three robust controllers, only the proposed controller is suitable for multiple resource failure cases. Considering the fact that multiple resource failures may occur in real AMS, we can conclude that the proposed controller is a permissive and effective robust controller for AMS with a widely industrial applicability, and it represents the most desired one so far to our best knowledge.

Conclusion

This article has focused on the robust deadlock prevention problems in AMS with single type of unreliable resources. For AMS that can be modeled by S³PR with a single type of unreliable resources, the conception of BS is presented. In order to forbid BSs and deadlocks, for US³PR without κ-resources, a robust controller is proposed to make sure that all the SMSs cannot be empty even if resource failures happen. For US³PR with κ-resources, a robust supervisory policy based on κ-resource elimination method is given. In this case, a (Ψ(r_u) − 1)-robust deadlock control controller is proposed for all kinds of US³PR, it can ensure that all process routes can work normally when most Ψ(r_u) − 1 units of unreliable resources fail. The controller proposed in this article has two major outcomes: first, it has a better permissive behavior than most of the existing ones; second, it has the highest robust control level, which can be viewed as its most important advantage, that is to say, the proposed controller can ensure the normal operation of the system as long as one unit of unreliable resource can be used.

Robust control for AMS with multiple types of unreliable resources is still an open problem. The proposed robust controller can restrict some safe states. In this case, it should be an explicit guideline on designing a more permissive robust controller with few constraints. Another future research is to design a robust controller for AMS with multiple unreliable resources.

Footnotes

Handling Editor: Yangmin Li

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 in part by the National Natural Science Foundation of China under Grants 61304052 and 61573278.

ORCID iD

Yunchao Wu

References

Xing

et al . Total energy consumption optimization via genetic algorithm in flexible manufacturing systems. Comput Ind Eng 2017; 104: 188–200.

Wang

Xing

et al . An estimation of distribution algorithm for scheduling problem of flexible manufacturing systems using Petri nets. Appl Math Model 2016; 55: 776–788.

Zhou

. Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation. IEEE T Autom Sci Eng 2012; 9: 203–209.

Chu

et al . Petri net modeling and cycle-time analysis of dual-arm cluster tools with wafer revisiting. IEEE T Syst Man Cy A 2013; 43: 196–207.

Zhou

Bai

et al . Short-term scheduling of crude oil operations in refinery with high-fusion-point oil and two transportation pipelines. Enterp Inf Syst 2016; 10: 581–610.

Zhang

et al . Petri net-based approach to short-term scheduling of crude oil operations with less tank requirement. Inf Sci 2017; 417: 247–261.

Ezpeleta

Colom

Martinez

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

Han

Xing

Zhou

et al . Efficient optimal deadlock control of flexible manufacturing systems. IET Control Theory A 2016; 10: 1181–1186.

Liu

et al . Design of optimal Petri-net controllers for a class of flexible manufacturing systems with key resources. Inf Sci 2016; 363: 221–234.

10.

Liu

Xing

Zhou

et al . Transition cover-based design of Petri net controllers for automated manufacturing systems. IEEE T Syst Man Cy A 2014; 44: 196–208.

11.

Liu

Xing

et al . Deadlock prevention for flexible manufacturing systems via controllable siphon basis of Petri nets. IEEE T Syst Man Cy A 2015; 45: 519–529.

12.

Xing

Han

Zhou

et al . Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy. IEEE T Syst Man Cy A 2012; 42: 603–615.

13.

Xing

Chen

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

14.

Xing

Zhou

Liu

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

15.

Chew

Lawley

. Robust supervisory control for production systems with multiple resource failures. IEEE T Autom Sci Eng 2006; 3: 309–323.

16.

Feng

Xing

Gao

et al . Transition cover-based robust Petri net controllers for automated manufacturing systems with a type of unreliable resources. IEEE T Syst Man Cy A 2016; 47: 3019–3029.

17.

Hsieh

. Fault-tolerant deadlock avoidance algorithm for assembly processes. IEEE T Syst Man Cy A 2004; 34: 65–79.

18.

Lawley

Sulistyono

. Robust supervisory control policies for manufacturing systems with unreliable resources. IEEE T Robotic Autom 2002; 18: 346–359.

19.

Liu

Barkaoui

et al . Robustness of deadlock control for a class of Petri nets with unreliable resources. Inf Sci 2013; 235: 259–279.

20.

Wang

Xing

Zhou

et al . A robust deadlock prevention control for automated manufacturing systems with unreliable resources. Inf Sci345: 243–256.

21.

Xing

Luo

et al . Robust deadlock control for automated manufacturing systems with an unreliable resource. Inf. Sci 2016; 346–347: 17–28.

22.

Yue

Xing

. Robust supervisory control for avoiding deadlocks in automated manufacturing systems with one specified unreliable resource. T I Meas Control 2014; 36: 435–444.

23.

Yue

Xing

. Robust supervisory control policy for avoiding deadlock in automated manufacturing systems with unreliable resources. Int J Prod Res 20146; 52: 1573–1591.

24.

Wang

Chew

Lawley

. Using shared-resource capacity for robust control of failure-prone manufacturing systems. IEEE T Syst Man Cy A 2008; 38: 605–627.

25.

Zhou

Venkatesh

. Modeling, simulation, and control of flexible manufacturing systems: a Petri net approach. Singapore: World Scientific, 1999.

26.

Xing

Zhou

Wang

et al . Resource-transition circuits and siphons for deadlock control of automated manufacturing systems. IEEE T Syst Man Cy A 2011; 41: 74–84.

27.

Chu

Xie

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

28.

Fanti

Zhou

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

Robust deadlock control for automated manufacturing systems with a single type of unreliable resources

Abstract

Keywords

Introduction

Basic definitions of PNs

PNs

S3PR class

Definition 1

Deadlock controller for S3PR

Definition 2

Lemma 1

Definition 3

Lemma 2

Example 1

Definition 4

Definition 5

PN-based deadlock analysis for AMS with single type of unreliable resources

Definition 6

Definition 7

Example 2

Definition 8

Lemma 3

Proof

Robust controllers design

Robust controller for US3PR without κ-resources

Definition 9

Example 3

Lemma 4

Proof

Lemma 5

Proof

Theorem 1

Proof

Robust supervisor for US3PR withκ-resources

Definition 10

Definition 11

Definition 12

Theorem 2

Proof

Examples and discussion

Example 4

Example 4 discussion

Example 5

Example 5 discussion

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References

S³PR class

Deadlock controller for S³PR

Robust controller for US³PR without κ-resources

Robust supervisor for US³PR withκ-resources