Robust supervisory control for avoiding deadlocks in automated manufacturing systems with one specified unreliable resource

Abstract

The design of supervisory controllers to resolve any deadlock issue in automated manufacturing systems (AMSs) has attracted the efforts of many researchers. A great deal of work, which assumes that allocated resources do not fail, has been done, while only a few works pay attention to the existence of unreliable resources in AMSs. In this paper, we focus on the robust supervisory control for avoiding deadlocks in AMSs, each of which has one specified unreliable resource. We develop a robust supervisory control policy under which the system can continue producing without manual intervention in the face of the unreliable resource’s failure and recovery. Our policy consists of a modified Banker’s Algorithm and the available resource constraints. After proving the correctness of our policy, we show that there are more reachable states under our policy than the existing one. Therefore, our policy imposes less restrictive constraints on the system and is more permissive than the original one. Finally, an example is provided to illustrate our control policy’s advantage in permissiveness.

Keywords

Automated manufacturing systems (AMSs)control policy deadlock avoidance robust control

Introduction

Over the past two decades or so, practitioners and researchers from the manufacturing field recognized the need to develop supervisory control policies for automated manufacturing systems (AMSs). An AMS is usually a computer-integrated manufacturing system, i.e. a conglomeration of computer numerically controlled system. Supervisory control policies can be embedded in the software controller and implemented on the supervisory computers in the control hierarchy. An active area of supervisory control research has been the development of deadlock solution methods (Fanti and Zhou, 2004). There are a large number of research achievements for deadlock control problems (Chao et al., 2012; Chen et al., 2012; Hu et al., 2012; Huang et al., 2012; Jeng et al., 2002; Li et al., 2012; Liu et al., 2010; Nazeem and Reveliotis, 2012; Piroddi et al., 2008; Uzam, 2002; Wang et al., 2012; Wu and Zhou, 2001; Wu et al., 2008; Xing et al., 2011, 2012; Yue, 2011).

In most of the work, all the allocated resources are assumed to be reliable. However, inevitably, there are uncertainty factors such as an unreliable resource, which is prone to failure in an actual system. The common failures that may happen in AMSs include tool breakages, hydraulic failures, electrical failures, sensor failures, pneumatic failures, spindle failures and failures caused by parts going out of specification. When an AMS suffers a failure, none of the part instances, which are in processing on, or require in the future the failed resource, can be completed until the resource’s recovery. That is, some of the parts might be stalled. Much worse problems may arise, such as the stalled parts can block the production of other part types that do not need the failed resource. Compared with the scheduling problems, the deadlock and blocking problems in uncertain AMSs are not often focused (Chew et al., 2011; Hsieh, 2011). Consequently, it is a challenging area of research to consider robust supervisory deadlock control for AMSs with unreliable resources.

Wu and Zhou (2011) pioneer the concept of an ‘intelligent token Petri net’. They use this concept to model and control the reconfigurable AMSs with dynamic changes, and develop a supervisor for these systems to guarantee deadlock-free operations.

For an uncertain and non-deterministic discrete event system, Park (2012) presents necessary and sufficient conditions for the existence of a special robust and non-blocking supervisor.

Lawley et al. (Chew and Lawley, 2006; Chew et al., 2009, 2011; Lawley and Sulistyono, 2002; Wang et al., 2008, 2009) consider the robust supervisory control for a class of AMSs with unreliable resources. Each resource being discussed, which is actually a resource type, is a workstation. Specifically, a resource workstation contains a server or processor for processing parts and a couple of units of buffer space for storing parts. For a given resource, the number of its buffer space units is referred to its capacity. Resource ‘failure’ implies the failure of the server. When a resource fails, none of the waiting parts on the resource for processing can be processed and, thus, cannot proceed along their respective route until the resource is restored. Therefore, the failure of a resource may cause the buffer space to capacitate and propagate through blocking to stall other portions of the system. The supervisors proposed by Lawley et al. guarantee that, at all times, the system continues to produce part types that do not require failed resources.

For the same class of AMSs as researched by Lawley and Sulistyono (2002), this paper presents a robust supervisory control policy for deadlock avoidance. Our policy consists of an improved version of the Banker’s Algorithm and the available resource constraints. The policy is proved to be correct using the formal languages and automata theory.

The work in this paper is different from that of Wang et al. (2008); those researchers tried to improve the behavioural permissiveness of the supervisory controller by using the shared resources. Their policy is of the so-called ‘distributing’ type (Wang et al., 2009), while our policy belongs to the ‘absorbing’-type controllers. In fact, our policy is able to move all parts requiring the failed resource into the associated failure-dependent resources’ buffer spaces. Thus, the production of all the part types that do not require the failed resource is not affected at all.

Our work differs from the work of Hsieh (2007, 2011), which concentrated on the robustness analysis for flexible manufacturing systems, while our objective is to control the system so that the system can continue to produce part types not requiring the failed resource in the face of the unreliable resource’s failure and the failure recovery.

Unlike the mostly researched AMSs (Hsieh, 2011; Liu et al., 2010; Uzam, 2002; Wu and Zhou, 2011; Xing et al., 2009), in which each unit of each type of resource is able to process or store one part, every resource in our system is actually a resource type and consists of a server and several units of buffer space.

Moreover, our work differs from the work of Reveliotis (1999) and Chew et al. (2009) because we use no additional and external central buffers for temporarily storing parts, while central buffers are indispensable in their policies.

The main contribution of our work is as follows. In the modified Banker’s Algorithm of our policy, we carefully deal with the parts that have finished their current operation on the specified unreliable resource r_u and do not need r_u anymore. Therefore, our policy turns out to be more permissive than the existing one (Lawley and Sulistyono, 2002). Furthermore, we replace the original neighbourhood constraints by the available resource constraints. So our policy takes a more concise form.

The rest of this paper is organized as follows. Next we formally and precisely define the class of AMSs considered. Then, we propose the robust control policy to avoid deadlocks. We provide a performance comparison between our policy and the existing one, followed by the discussion. Finally, we conclude the paper.

Discrete event dynamic system model

This section is a brief presentation of some definitions and notations of the AMSs and their discrete event dynamic system models. For more details, please refer to Lawley and Sulistyono (2002).

The discrete event dynamic system model for this class of systems can be described as S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ}, where

R is the set of resources in the system with r_u being the sole unreliable resource. We assume that r_u is subject to failure and other resources are not subject to failure. For r∈R, C(r)≥1 is the capacity of r.

P is the set of part types produced by the system with each part type P_j∈P represented as an ordered product route P_j = <P_j₁, P_j₂, …, P_j, _{|P_j|}>, where P_jk is the kth part type stage of P_j, k = 1, 2, …, |P_j|. Let p_jk represent an actual instance of P_jk. Each p_jk occupies one unit of buffer space of the resource ρ(P_jk), where ρ(P_jk) is the resource required by P_jk. For r∈R, let Ω(r) = {P_jk: ρ(P_jk) = r}, and this notation can be extended to a set, i.e. if R₁⊆R, then Ω(R₁)=∪_r∈R₁Ω(r).

Q is the set of system states, and Q ∍ q = (sv_u, y_jk, x_jk, j = 1, 2, …, |P|, k = 1, 2, …, |P_j|) is a state, where sv_u shows the status of the unreliable resource r_u (0 if failed, 1 otherwise), x_jk (y_jk) is the number of the parts that are on the resource ρ(P_jk) and have (have not) finished their current operation P_jk. q₀ is the initial state in which no resource is allocated and r_u is operational.

Σ=Σ_c∪Σ_u is the set of all events. Σ_c = {α_jk: j = 1, 2, …, |P|, k = 1, 2, …, (|P_j|+1)} is the set of controllable events with α_jk (k ≤ |P_j|) representing allocating a unit of buffer space at resource ρ(P_jk) to a p_jk, and α_j, _{(|P_j|+1)} representing that a finished part of type P_j leaves the system. Σ_u = Σ_u1∪Σ_u2 is the set of uncontrollable events with Σ_u1 = {β_jk: j = 1, 2, …, |P|, k = 1, 2, …, |P_j|} where β_jk represents the completion of service for part type stage P_jk, and Σ_u2 = {κ_u, η_u} where κ_u and η_u represents the failure and the recovery of r_u, respectively.

ξ: Q → 2^Σ is the event enabling function. For q∈Q, ξ(q) is the set of enabled events under q, as defined as follows. a) ∀r∈R, ∀P_j₁∈Ω(r), if C(r)−∑_{P_jk∈Ω(r)} (y_jk+x_jk)>0, then α_j₁∈ξ(q); b) ∀r_i∈R (if i = u, then sv_u = 1 is additionally needed), ∀P_jk∈Ω(r_i), if y_jk>0, then β_jk∈ξ(q); c) if sv_u = 1 and ∃P_jk∈Ω(r_u) such that y_jk>0, then κ_u∈ξ(q); d) if sv_u = 0, then η_u∈ξ(q), and for ∀P_jk∈Ω(r_u), β_jk∉ξ(q); e) ∀r∈R, ∀P_jk∈Ω(r) with 1 < k≤ |P_j|, if x_j, _k-1>0, and C(r)−∑_{P_jk∈Ω(r)} (y_jk+x_jk)>0, then α_jk∈ξ(q); f) if $x_{j, | P_{j} |}$ >1, then $a_{j, (| P_{j} | + 1)}$ ∈ξ(q).

δ : Q×Σ→Q is the state transition function. δ(q, π) is defined only for π∈ξ(q). Let $e_{y_{jk}}$ , $e_{x_{jk}}$ and $e_{s v_{u}}$ be the standard unit vectors with the components y_jk, x_jk and sv_u being 1, respectively. Then, for α_jk, β_jk, κ_u, η_u∈ξ(q), there are δ(q, α_jk) = q+ $e_{y_{jk}}$ − $e_{x_{j, (k - 1)}}$ , δ(q, β_jk) = q− $e_{y_{jk}}$ + $e_{x_{jk}}$ , δ(q, κ_u) = q− $e_{s v_{u}}$ and δ(q, η_u) = q+ $e_{s v_{u}}$ , respectively. In addition, note that $e_{y_{j, (| P_{j} | + 1)}}$ = $e_{x_{j 0}}$ = 0, the null vector. Let Σ^* denote the set of all finite strings of elements of Σ. For σ∈Σ^*, π∈Σ, let π_σ be the number of occurrences of π in σ. We can easily extend δ to σ∈Σ^* recursively.

Let L(S) = {σ : σ∈Σ^* and δ(q₀, σ) is defined} be the language generated by S, and let Q_r(q₀) = {q : σ∈L(S), q = δ(q₀, σ)} denote the set of states reachable from the initial state q₀.

Example 1. Consider the AMS shown in Figure 1, which is first considered in Lawley and Sulistyono (2002). The resource set is R = {r₁, r₂, r₃, r₄, r₅, r₆, r₇}, where each resource’s capacity is two and the unreliable resource is r₂. The AMS can process three types of parts P = {P₁, P₂, P₃} with P₁ : <r₁, r₂, r₃, r₄>, P₂ : <r₆, r₃, r₂, r₁, r₃, r₂> and P₃ : <r₇, r₅, r₄, r₃>. So we have that Ω(r₁) = {P₁₁, P₂₄}, Ω(r₂) = {P₁₂, P₂₃, P₂₆}, Ω(r₃) = {P₁₃, P₂₂, P₂₅, P₃₄} and so on.

Figure 1.

A state of an automated manufacturing system.

Consider the system state shown in Figure 1. There are part instances such as double p₁₁ on the resource r₁ with x₁₁+y₁₁ = 2, and a single p₂₆ with x₂₆+y₂₆ = 1. Note that the information about the exact number of y_jk or x_jk, and the status of the unreliable resource is not presented in Figure 1. However, for the state as shown in Figure 1, we designate that all the parts have finished their current operations, that is, y_jk = 0, j = 1, 2, 3, k = 1, 2, …, |P_j|.

Definition 1. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS.

A supervisory control policy△ for S is a function △:Q→ 2^Σ, with △(q) = {π∈Σ : π is permitted to occur by the policy △ at the state q}. A policy △ cannot prohibit the uncontrollable events, i.e. Σ_u∩ξ(q)⊆△(q).

The state transition function under the control of a policy △ is δ_△ :Q×Σ→Q, where for q∈Q and π∈Σ, if δ(q, π) is defined and π∈△(q), then δ_△(q, π) = δ(q, π); otherwise δ_△(q, π) is not defined. Similarly, δ_△ can be extended to Q×Σ^* in the usual way.

The language generated by S under △ is L(△/S) = {σ∈Σ^* : δ_△(q₀, σ) is defined}. Let Q_r(△, q₀) = {q∈Q: q = δ_△(q₀, σ), and σ∈L(△/S)} denote the set of all states reachable from q₀ under △.

Robust supervisory control

Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS. We want to design a robust supervisory control policy for S. To make it easy to understand our policy, we first depict a fairly simple AMS with one of its block states.

The AMS shown in Figure 2 has resources r₁, r₂ and r₃, each having a single unit of buffer space, and r₂ is unreliable. One circle stands for one buffer space unit and the spanners for the servers, one resource with one server. Three types of parts have to be processed with processing routes <r₁, r₂>, <r₂, r₁> and <r₃, r₁, r₃>. In the state as shown in Figure 2, a part p₁₁ and a part p₁₂ are in process on the servers of r₁ and r₂, respectively. Then the sate is a ‘bad’ one because, if r₂ fails at this time, not only the parts p₁₁ and p₁₂ are stalled, but also the production of parts of type <r₃, r₁, r₃>, which does not need the failed resource, is blocked. Therefore, our policy must discard such ‘bad’ states like the one shown in Figure 2.

Figure 2.

Another automated manufacturing system with a ‘bad’ state.

Formal definition of robust supervisory control policy

The following definition of a robust supervisory control policy △ is essentially the same to that in Lawley and Sulistyono (2002).

Definition 2. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS with one specified unreliable resource r_u. Let ψ = {α_jk : ∃P_jm∈Ω(r_u), k = 1, …, |P_j|+1}∪{β_jk : ∃P_jm∈Ω(r_u), k = 1, …, |P_j|}. A supervisory control policy △ of S is robust to the failure of r_u if △ satisfies the following four properties.

For q∈Q_r(△, q₀) such that sv_u = 1, then ∀π∈Σ\Σ_u2, ∀n∈N={0, 1, 2, …}, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△(q, σ) is defined and π_σ>n.

For q∈Q_r(△, q₀) such that sv_u = 1, if κ_u∈ξ(q), let δ_△(q, κ_u) = q_g, then ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△(q_g, σ) is defined and π_σ>n.

For q∈Q_r(△, q₀) such that sv_u = 0, then ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△(q, σ) is defined and π_σ>n.

For q∈Q_r(△, q₀) such that sv_u = 0, let δ_△(q, η_u) = q_h, then ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△(q_h, σ) is defined and π_σ>n.

Obviously, Q_r(△, q₀)⊆Q_r(q₀). Generally, we hope that the limitation of △ to the system would be as small as possible. That is, |Q_r(△, q₀)|, the cardinality of the set Q_r(△, q₀), should be as large as possible.

Furthermore, let us give some remarks on the term ‘robust’ in Definition 2. It is accepted that the unreliable resource’s failure can disable the production of some part types. However, a ‘robust’ supervisory control policy can prevent the failure from propagating to stall other part types whose production does not need the failed resource. That is, under the control of a ‘robust’ supervisory control policy, and with the unreliable resource alternating between failed and operational, the system can continue producing any part type that does not require the currently failed resource without any manual intervention.

Partitioning the set of part type stages

First of all, we classify the resources of an AMS as Lawley and Sulistyono (2002) did.

Definition 3. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS with one specified unreliable resource r_u. A resource r∈R is said to be failure dependent on r_u if every part that enters the buffer space of r requires future processing on r_u. Let FD = {r∈R : ∀P_jk∈Ω(r), ∃P_j, _k+c∈Ω(r_u) with c∈N}. We call ND = R\FD the set of non-failure-dependent resources in S.

For the AMS shown in Figure 1, we have that r_u = r₂, FD = {r₁, r₂, r₆} and ND = {r₃, r₄, r₅, r₇}.

Let ℙ denote the set of all part type stages in the system. For P_jk∈ℙ, j = 1, 2, …, |P|, k = 1, 2, …, |P_j|, let RT_jk = {ρ(P_jl) : l = k, k+1, …, |P_j|}, and let P^FD = {P_jk : r_u∈RT_jk}. As a consequence, there is a partition of ℙ

ℙ = P^{FD} \cup P^{ND}

(1)

And

P^{ND} = ℙ \ P^{FD} .

For the system as shown in Figure 1, P^FD = {P₁₁, P₁₂, P₂₁, P₂₂, P₂₃, P₂₄, P₂₅, P₂₆}, P^ND = {P₁₃, P₁₄, P₃₁, P₃₂, P₃₃, P₃₄}.

Going a step further, there is a partition for P^FD

P^{FD} = (P^{FD} \ Ω (F D)) \cup Ω (F D)

(2)

since ∀r∈FD, Ω(r)⊆P^FD.

In order to go one more step further in partition the set of part type stages, we need the following definition.

Definition 4. Let Θ = {P_jk: (ρ(P_jk) = r_u) ∧ (r_u∉RT_j, _(k+1))} denote the set of final unreliable resource dependent part type stages.

For example, recall that the sole unreliable resource is r₂ in the AMS shown in Figure 1, so we have that Θ = {P₁₂, P₂₆}. Evidently, Θ⊆Ω(r_u), and hence,

Ω (FD) = (Ω (FD) \ Θ) \cup Θ

(3)

From (1), (2) and (3), we have

ℙ = ℙ_{1} \cup ℙ_{2} \cup ℙ_{3} \cup ℙ_{4}

(4)

where ℙ₁ = P^ND, ℙ₂ = (P^FD\Ω(FD)), ℙ₃ = (Ω(FD)\Θ) and ℙ₄ = Θ. It is trivial that ℙ_m∩ℙ_n = ∅, m≠n.

For the AMS shown in Figure 1, we have ℙ₁ = {P₁₃, P₁₄, P₃₁}, ℙ₂ = {P₂₂, P₂₅}, ℙ₃ = {P₁₁, P₂₄, P₂₃, P₂₁} and ℙ₄ = {P₁₂, P₂₆}.

For q∈Q, let d(q) = {P_jk: x_jk+y_jk>0}. Namely, d(q) is the set of part type stages represented in q. In order to prepare for the modified Banker’s Algorithm (MBA) that will be presented in the next subsection, we partition the set d(q) as follows

d (q) = d_{1} (q) \cup d_{2} (q) \cup d_{3} (q) \cup d_{4} (q)

where d₁(q) = d(q) ∩ℙ₁, d₂(q) = d(q) ∩ℙ₂, d₃(q)=(ℙ₃∪ℙ₄)\d₄(q), d₄(q) = {P_jk: P_jk∈ℙ₄∧x_jk>0}. It is also trivial that d_m(q) ∩d_n(q)=∅, m≠n.

Clearly, even if r_u fails, it is still possible for the x_jk part instances of type P_jk∈d₄(q), which has completed their operation on r_u, to be finished and driven out of the system.

For example, for the system state shown in Figure 1, recall that x₂₆ = 1, then we have that d₁(q) = {P₁₃, P₃₃, P₃₂, P₃₁}, d₂(q) = {P₂₂}, d₃(q) = {P₁₁, P₂₁}, d₄(q) = {P₂₆}.

Modified Banker’s Algorithm

In order to increase the policy flexibility of the existing supervisory controller, we modify the Banker’s Algorithm (BA) in Lawley and Sulistyono (2002). Let us first briefly review BA. For a state q, BA tries to move all parts of all part type stages in Λ_LS(q) = d₁(q)∪d₂(q) so that the following two things finally hold: 1) all part instances of type P_jk∈d₁(q) can be driven out of the system; 2) every part instance of type P_jk∈d₂(q) can be advanced into the first-met failure-dependent resource in its remaining route.

Our MBA is then outlined. Taking a state q, MBA acts as follows. 1) Try to move all parts of type P_jk∈d₁(q) to completion; 2) try to advance every part of type P_jk∈d₂(q) into the first-met failure-dependent resource in its remaining route; 3) try to drive the parts of type P_jk∈d₄(q), which have finished their services on r_u and still remain at r_u, to completion; and 4) keep other parts where they currently are.

To summarize, for a state q, MBA tries to search for an ordering of all the part type stages in the set Λ₁(q) = d₁(q)∪d₂(q)∪d₄(q) such that all parts can be placed in proper locations by following this ordering. If this part type stage ordering is possible, MBA accepts q and returns (Accept, q_e), where q_e is the resulting state computed by MBA on q. Otherwise, MBA rejects q and returns (Reject, q_e).

Now, we want to explain and highlight the differences between BA and MBA. MBA pays more attention to the parts that have finished their current operation on the specified unreliable resource r_u and do not need r_u anymore. Unlike BA, which just keeps these parts on r_u, MBA tries to move these parts to completion and out of the system. Furthermore, after its execution on a state q, MBA outputs the resulting state q_e, which will be used later by the available resource constraints. However, BA does not output its resulting state since the resulting state is useless.

In the following description of Algorithm MBA, for r_i∈R, i = 1, 2, …, |R|, AVAILABLE[i] records the number of available buffer space units of the resource r_i. For r_i∈R and a part type stage P_jk, NEED[ j][k][i]=1 (or 0) records that a part p_jk does (does not) require the resource r_i in order that p_jk can reach the proper location.

Algorithm MBA

INPUT: An AMS S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} and a state q.

OUTPUT: MBA(q)∈{Accept, Reject} ×Q.

Step 1: Initialization

Г=d₁(q) ∪d₂(q) ∪d₄(q) ;

q_e = q;

For (P_jk∈Г) ∧ (r_i∈R)

NEED[ j][k][i]=0;

For (P_jk∈d₁(q)) ∧ (r_i∈RT_j, _k+1) ∧ (ρ(P_jk) ≠r_i)

NEED[ j][k][i]=1;

For (P_jk∈d₄(q)) ∧ (r_i∈RT_j, _k+1)

NEED[ j][k][i]=1;

For (P_jk∈d₂(q)) ∧ (r_i∈{ρ(P_j, _k+l) : l = 1, 2, …, c}, where c is the minimal value such that ρ(P_j, _k+c)∈FD) ∧ (ρ(P_jk) ≠r_i)

NEED[ j][k][i]=1;

For all r_i∈R

AVAILABLE[i]=rc(q, r_i); /*rc(q, r_i) is the number of remaining buffer space units at r_i in q. */

Step 2: Main body

Begin

While (Г≠∅)

Find P_jk∈Г such that NEED[j][k][] <=AVAILABLE[]

If (no such P_jk) exits, return (Reject, q_e);

Else

If (P_jk∈d₁(q)){

Advance all parts of type P_jk to completion, and reach a new state q_n ;

AVAILABLE[i]=AVAILABLE[i]+x_jk+y_jk, where ρ(P_jk)==r_i;

}End If

If (P_jk∈d₂(q)){

Advance all parts of type P_jk to the first-met failure-dependent resource r_w in their remaining route, and reach a new state q_n ;

AVAILABLE[i]=AVAILABLE[i]+x_jk+y_jk, where ρ(P_jk)==r_i;

AVAILABLE[w]=AVAILABLE[w]−x_jk−y_jk ;

If (AVAILABLE[w] < 0) exits, return (Reject, q_e);

}End If

If (P_jk∈d₄(q)){

Advance the parts which have finished their current operations and of type P_jk to completion, and reach a new state q_n ;

AVAILABLE[i]=AVAILABLE[i]+x_jk, where ρ(P_jk)==r_i;

}End If

q_e = q_n;

Г=Г\{P_jk} ;

End Else

End While

If (Г==∅), exits, return (Accept, q_e);

End

In the rest of the paper, we will also use q_e = MBA(q) if only the relation between the output and input states is considered.

Definition 5. A state q is acceptable by MBA if MBA(q)=(Accept, q_e). Let Q_T = {q : q∈Q_r(q₀) ∧d₁(q)=∅∧d₂(q)=∅∧d₄(q)=∅}.

Lemma 1. Let S = {R, C, P,ρ, Q, q₀, Σ, ξ, δ} be an AMS, q∈Q_r(q₀) and q_e = MBA(q). Then, q is acceptable by MBA if and only if q_e∈Q_T.

Lemma 1 is trivial and its proof is omitted.

For example, let us consider that MBA takes the state q shown in Figure 1 as input. Then, MBA acts as follows. 1) Move the p₂₂ from r₃ to r₂; 2) unload the finished unit p₂₆ from the system; 3) advance the double p₃₃, double p₃₂ and double p₃₁ to completion and unload them; 4) advance the p₁₃ to completion and unload it. Therefore, the ordering of all stages in the set Λ₁(q), which is computed by MBA, is <P₂₂, P₂₆, P₃₃, P₃₂, P₃₁, P₁₃>. So we have MBA(q)=(Accept, q_e) and q_e∈Q_T, where q_e is the state with a single p₂₃, double p₁₁ and double p₂₁ located in the buffer space of r₂, r₁ and r₆, respectively.

Robust supervisory control policy

We first propose the available resource constraints (ARC). ARC requires that for q∈Q_r(q₀), there are at least (|FD|−1) resources of FD such that any of them has at least one available buffer space unit. That is, any two resources in FD totally have at least one remaining buffer space unit in q. Formally, ARC consists of the following (|FD|×(|FD|−1))/2 inequalities.

ARC : rc (q, r_{g}) + rc (q, r_{h}) \geq 1, \forall r_{g}, r_{h} \in FD

For example, please reconsider the state q shown in Figure 1. It is easy to check to know that q fails to satisfy ARC since rc(q, r₁)+rc(q, r₆)=0.

Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS. Our robust supervisory control policy for S is a function △₁ : Q→ 2^Σ such that for a state q∈Q and an event π∈Σ, it follows that: 1) if π∈Σ_u, then π∈△₁(q); and 2) otherwise(π∈Σ_c), π∈△₁(q) if and only if q₁ = δ(q, π) is defined, MBA(q₁)=(Accept, q_e), and q_e satisfies ARC.

In order to prove the correctness of △₁, we first need the following lemma.

Lemma 2. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS, q∈Q_r(△₁, q₀), and q_e = MBA(q). Then, MBA accepts q and q_e satisfies ARC.

Proof: Since q∈Q_r(△₁, q₀), we have that ∃σ∈Σ^* such that q = δ_△₁(q₀, σ) according to the definition of Q_r(△₁, q₀). We prove that MBA accepts q and q_e satisfies ARC by mathematical induction on the length of the event string |σ| as follows.

If σ = ε (empty string), then q = q₀ and MBA(q) = q₀. It is clear that q₀∈Q_T, so MBA accepts q according to the sufficient condition in Lemma 1. Additionally, we have that q₀ satisfies ARC. Thus, the conclusion follows when |σ|=0.

Suppose that the conclusion follows when |σ|=n≥0. If |σ|=n+1, let σ = σ₁π, π∈Σ. Since q = δ_△₁(q₀, σ) = δ_△₁(q₀, σ₁π) is defined, we get that q′∈Q_r(△₁, q₀) and q = δ_△₁(q′, π) is defined, where q′=δ_△₁(q₀, σ₁). From inductive hypothesis, we have MBA(q′)=(Accept, q′_e) and q′_e satisfies ARC since |σ₁|=n. We get that π∈△₁(q′) since δ_△₁(q′, π) is defined. Now, we consider three cases of π∈Σ=Σ_c∪Σ_u1∪Σ_u2.

Case 1: π∈Σ_c. According to the depiction of △₁, we have MBA(q)=(Accept, q_e) and q_e satisfies ARC since π∈△₁(q′) and π∈Σ_c.

Case 2: π∈Σ_u1. It is evident that MBA(q)=(Accept, q_e) and q_e satisfies ARC since MBA(q′)=(Accept, q′_e) and q′_e satisfies ARC. To see this, we have that ∀r∈R, rc(q_e, r)≥rc(q′_e, r).

Case 3: π∈Σ_u2. It is also clear that MBA(q)=(Accept, q_e) and q_e satisfies ARC since MBA(q′)=(Accept, q′_e) and q′_e satisfies ARC. To see this, we have that ∀r∈R, rc(q_e, r) = rc(q′_e, r).

In summary, when |σ|=n+1, we have MBA(q)=(Accept, q_e) and q_e satisfies ARC, where q∈Q_r(△₁, q₀) and q = δ_△₁(q₀, σ).

Therefore, through mathematical induction, we have that, if a state q∈Q_r(△₁, q₀), then MBA(q)=(Accept, q_e) and q_e satisfies ARC. ▪

Lemma 3. Given an AMS S = {R, C, P,ρ, Q, q₀, Σ, ξ, δ}, MBA(q)=(Accept, q₁), q₁ satisfies ARC, and σ∈(Σ_c∪Σ_u1)^* is computed by MBA at q such that q₁ = δ(q, σ). Then, q₁ = δ_△₁(q, σ).

Proof: Let σ = π₁π₂…π_t∈(Σ_c∪Σ_u1)^*, q₀′=q, q_i′=δ(q, π₁π₂…π_i), i = 1, 2, …, t−1, q_t′=δ(q, π₁π₂…π_t) = δ(q, σ) = q₁. Since MBA(q)=(Accept, q₁), we have that MBA(q_i′)=(Accept, q₁). Combining it with the fact that q₁ satisfies ARC, we have that π_i∈△₁(q′_i−1), i = 1, 2, …, t. It then follows that q₁ = δ_△₁(q, σ). ▪

Lemma 4. Given an AMS S = {R, C, P,ρ, Q, q₀, Σ, ξ, δ}, q∈Q_T, sv_u = 1 and q satisfies ARC. Then ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) = q₁∈Q_T and for ∀r∈R, rc(q₁, r)≥1.

Proof: Since q∈Q_T, we have that all parts represented in q are located in the buffer space of failure-dependent resources. Therefore, all the non-failure-dependent resources are free of parts. Thus, we have

\forall r \in ND, rc (q, r) = C (r) \geq 1

(5)

If ∀r∈R\ND = FD, rc(q, r)≥1, then let σ = ε, and q₁ = δ_△₁(q, σ) = δ_△₁(q, ε) = q. Otherwise, consider the set of resources {r : r∈FD and rc(q, r)=0}. Since q satisfies ARC, the set FD contains at most one resource that does not have any remaining buffer space unit in q. Thus, let s₁ be the only failure-dependent resource that has no free buffer space unit in q, and we have

\forall r \in F D, if r \neq s_{1}, then r c (q, r) \geq 1

(6)

Take at random a part p_jk represented in q at s₁. From (5) and (6), we have that p_jk can be allocated enough resources to be driven from the system, making s₁ get one empty buffer space unit. Let the corresponding event sequence of the above procedure be σ₁, then σ₁∈(Σ_c∪Σ_u1)^*. Furthermore, it is evident that the execution of σ₁ never requires a violation of △₁. Thus, δ_△₁(q, σ₁) is defined. Let δ_△₁(q, σ₁) = q₁. We then have ∀r∈R, rc(q₁, r)≥1. ▪

Lemma 5. Let S = {R, C, P,ρ, Q, q₀, Σ, ξ, δ} be an AMS, q∈Q_T and sv_u = 1, if ∀r∈R, rc(q, r)≥1, then, ∀π∈Σ\Σ_u2, ∀n∈ N , ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ>n.

Proof: For ∀π∈Σ\Σ_u2, ∃P_j∈P such that π is an event in the production route of P_j, i.e. π∈{α_jk : k = 1, 2,…, (|P_j|+1)}∪{β_jk: k = 1, 2,…, |P_j|}. Let σ_j = π₁π₂…π_t = α_j₁β_j₁α_j₂β_j₂… ${α_{j,}}_{| P_{j} |}$ ${β_{j,}}_{| P_{j} |}$ ${α_{j,}}_{(| P_{j} | + 1)}$ be the complete sequence of all the events corresponding to the production route of P_j. Then we have δ(q, σ_j) = q from the fact that ∀r∈R, rc(q, r)≥1. Furthermore, let q₀′=q, q_i′=δ(q, π₁π₂…π_i), i = 1, 2, …, t, and we have q_t′=q₀′=q. Let q_i′′=MBA(q_i′), i = 1, 2, …, t. Since q∈Q_T, q_i′′∈Q_T. Since ∀r∈R, rc(q, r)≥1, we have that q_i′′ satisfies ARC. From the description of the policy △₁, we get that π_i∈△₁(q′_i−1), i = 1, 2, …, t. So we have δ_△₁(q, σ_j) = q_t′=q. For ∀n∈N, let σ = (σ_j)⁽ⁿ⁺¹⁾. It follows that δ_△₁ (q, σ) = q and π_σ = n+1>n. To summarize, for ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ = (σ_j)ⁿ⁺¹∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) = q and π_σ = n+1>n. ▪

Lemma 6. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS, q∈Q_T, sv_u = 0, and q satisfies ARC, if ∀r∈ND, rc(q, r) = C(r), then, ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ>n.

Proof: For ∀π∈Σ\(ψ∪Σ_u2), ∃P_j∈P such that π is an event in the production route of P_j, i.e. π∈{α_jk : k = 1, 2, …, (|P_j|+1)}∪{β_jk: k = 1, 2, …, |P_j|}. Let σ_j = π₁π₂…π_t = α_j₁β_j₁α_j₂β_j₂… ${α_{j,}}_{| P_{j} |}$ ${β_{j,}}_{| P_{j} |}$ ${α_{j,}}_{(| P_{j} | + 1)}$ be the complete sequence of all the events corresponding to the production route of P_j. Since π∉ψ, the occurrence of the event sequence σ_j requires none of the resource in FD. Then, we have δ(q, σ_j) = q from the fact that ∀r∈ND, rc(q, r) = C(r). Furthermore, let q₀′=q, q_i′=δ(q, π₁π₂…π_i), i = 1, 2, …, t, and we have q_t′=q₀′=q. Since q∈Q_T and q satisfies ARC, it follows that q_i′′∈Q_T, and q_i′′ satisfies ARC, where q_i′′=MBA(q_i′),i = 1, 2, …, t. Thus, we get that π_i∈△₁(q′_i−1), i = 1, 2, …, t. So we have δ_△₁(q, σ_j) = q_t′=q. Then, for ∀n∈N, let σ = (σ_j)⁽ⁿ⁺¹⁾, it follows that δ_△₁ (q, σ) = q and π_σ = n+1>n. In summary, for ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ = (σ_j)ⁿ⁺¹∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) = q and π_σ = n+1>n. ▪

Lemma 7. In an AMS S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ}, if q∈Q_r(△₁, q₀) and sv_u = 1, then ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ>n.

Proof: We carry out MBA on q. Let q₁ = MBA(q), and σ₁∈(Σ_c∪Σ_u1)^* is computed by MBA at q with q₁ = δ(q, σ₁). Since q∈Q_r(△₁, q₀), we have that MBA(q)=(Accept, q₁) and q₁ satisfies ARC from Lemma 2. Then we have q₁ = δ_△₁(q, σ₁) from Lemma 3. Furthermore, we have that q₁∈Q_T and q₁ satisfies ARC. Thus, according to Lemma 4, we obtain that ∃σ₂∈(Σ_c∪Σ_u1)^* such that δ_△₁(q₁, σ₂) = q₂∈Q_T and for ∀r∈R, rc(q₂, r)≥1. From Lemma 5, ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ₃∈(Σ_c∪Σ_u1)^* such that δ_△₁(q₂, σ₃) is defined and π_{$σ_{3}$}>n. In summary, ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ = σ₁σ₂σ₃∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ≥π_{$σ_{3}$}>n. ▪

Lemma 8. In an AMS S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ}, if q∈Q_r(△₁, q₀) and sv_u = 0, then ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ>n.

Proof: Since q∈Q_r(△₁, q₀), we have that MBA(q)=(Accept, q₁) and q₁ satisfies ARC from Lemma 2. Let σ₁∈(Σ_c∪Σ_u1)^* be a event sequence computed by MBA at q with q₁ = δ(q, σ₁). Then we have q₁ = δ_△₁(q, σ₁) from Lemma 3. Moreover, we have that q₁∈Q_T and q₁ satisfies ARC. By q₁∈Q_T, it follows that ∀r∈ND, rc(q₁, r) = C(r). From Lemma 6, ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ₂∈(Σ_c∪Σ_u1)^* such that δ_△₁(q₁, σ₂) is defined and π_{$σ_{2}$}>n. To summarize, ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ = σ₁σ₂∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ≥π_{$σ_{2}$}>n. ▪

Theorem 1. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS with one specified unreliable resource r_u. Then △₁ is a roust deadlock avoidance supervisory control policy for S.

Proof:

∀q∈Q_r(△₁, q₀) such that sv_u = 1, from Lemma 7, we get that ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ>n.

∀q∈Q_r(△₁, q₀) such that sv_u = 1, if κ_u∈ξ(q), then κ_u∈△₁(q). Let δ_△₁(q, κ_u) = q_g, then q_g∈Q_r(△₁, q₀) and sv_u = 0. From Lemma 8, we have that ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q_g, σ) is defined and π_σ>n.

∀q∈Q_r(△₁, q₀) such that sv_u = 0, from Lemma 8, we get that ∀π∈Σ\(ψ∪Σ_u2), ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q, σ) is defined and π_σ>n.

∀q∈Q_r(△₁, q₀) such that sv_u = 0, let δ_△₁(q, η_u) = q_h. Then q_h∈Q_r(△₁, q₀) and sv_u = 1. From Lemma 7, we have that ∀π∈Σ\Σ_u2, ∀n∈N, ∃σ∈(Σ_c∪Σ_u1)^* such that δ_△₁(q_h, σ) is defined and π_σ>n.

By Definition 2, the above 1)–4) imply that △₁ is a robust supervisory control policy to avoid deadlocks. ▪

Policy performance comparison

In this section, we compare the performance of our policy △₁ with that of the policy △_LS (Lawley and Sulistyono, 2002).

The control policy △_LS is made up of BA and the neighbourhood constraints (NHC). That is, for π∈Σ_c, π∈△_LS(q) if and only if q₁ = δ(q, π) is defined, BA accepts q₁ and q₁ satisfies NHC. Here, we need briefly to review NHC.

For r∈FD, let NH(r)=Ω(r)∪{P_jk : ∃c>0 such that P_j, _k+c∈Ω(r), and ∀d∈[0, c), ρ(P_j, _k+d) ∉FD}. For r∈FD and NH(r), let Z(r)=∑_{P_jk∈NH(r)} (x_jk+y_jk). Let NHC₁ = {Z(r) ≤C(r): r∈FD }, NHC₂ = {Z(r_g)+Z(r_h) < C(r_g)+C(r_h) : r_g, r_h∈FD }, and NHC=NHC₁∪NHC₂. A state q is said to satisfy NHC if and only if q satisfies every inequality in the set NHC.

In the following, we first prove Q_r(△_LS, q₀) ⊆Q_r(△₁, q₀). Then, we propose an algorithm based on the breadth-first research to generate the reachable state space for a control policy. Finally, we illustrate that △₁ is more permissive than △_LS.

Lemma 9. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS and q∈Q. Then, q is acceptable by MBA if q is acceptable by BA.

Proof: For a state q, the sets of part type stages Λ_LS = d₁(q)∪d₂(q) and Λ₁ = Λ_LS∪d₄(q) are checked by BA and MBA, respectively. Let q₁ be the resulting state computed by BA on q. Since BA accepts q, all parts represented in q₁ are located at failure-dependent resources. Therefore, all non-failure-dependent resources are empty, that is

\forall r \in ND, rc (q_{1}, r) = C (r)

(7)

Taking the state q as input, MBA acts the following two steps.

Step 1: MBA executes the same as BA does. The state q₁ is reached again. Moreover, the remaining part type stages in Λ₁ constitute d₄(q). We have

For each P_{jk} \in d_{4} (q), R T_{j, (k + 1)} \subseteq ND

(8)

Step 2: MBA continues from q₁. Because of (7) and (8), all parts of all types P_jk∈d₄(q) that have finished their current operations are driven out of the system. Let q₂ be the resulting state, and it is clear that q₂∈Q_T. Thus, MBA accepts q by the sufficient condition in Lemma 1. ▪

Lemma 10. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS, q∈Q, q satisfies NHC₂, and MBA(q) = (Accept, q_e). Then q_e satisfies ARC.

Proof: The state q satisfies the constraints NHC₂. Therefore, ∀r_g, r_h∈FD, we have

Z (r_{g}, q) + Z (r_{h}, q) < C (r_{g}) + C (r_{h})

(9)

where Z(r_g, q)=∑_{P_jk∈_NH(rg)} (x_jk+y_jk) and Z(r_h, q)=∑_{P_jk∈_{NH(r_h)}} (x_jk+y_jk). Since q_e = MBA(q), according to the execution of MBA, it follows that, for ∀r∈FD

Σ_{P_{j k} \in Ω (r)} (x_{j k} + y_{j k}) \leq Z (r, q)

(10)

where ∑_{P_jk∈_Ω(r)} (x_jk+y_jk) corresponds to q_e. Moreover, at the state q_e, for ∀r∈FD,

rc (q_{e}, r) = C (r) - Σ_{P_{jk} \in Ω (r)} (x_{jk} + y_{jk}) .

Then

\begin{matrix} rc (q_{e}, r_{g}) & + rc (q_{e}, r_{h}) = (C (r_{g}) - Σ_{P_{jk} \in Ω (r_{g})} (x_{jk} + y_{jk})) \\ + (C (r_{h}) - Σ_{P_{jk} \in Ω (r_{g})} (x_{jk} + y_{jk})) . \end{matrix}

From (10), we have

\begin{array}{l} (C (r_{g}) - Σ_{P_{j k} \in Ω (r_{g})} (x_{j k} + y_{j k})) \\ + (C (r_{h}) - Σ_{P_{j k} \in Ω (r_{h})} (x_{j k} + y_{j k})) \geq (C (r_{g}) - Z (r_{g}, q)) \\ + (C (r_{h}) - Z (r_{h}, q)) = (C (r_{g}) + C (r_{h})) - (Z (r_{g}, q) + Z (r_{h}, q)) . \end{array}

Furthermore, from (9),

(C (r_{g}) + C (r_{h})) - (Z (r_{g}, q) + Z (r_{h}, q)) \geq 1 .

To summarize, we have that,

for \forall r_{g}, r_{h} \in FD, rc (q_{e}, r_{g}) + rc (q_{e}, r_{h}) \geq 1 .

Hence, q_e satisfies ARC. ▪

Theorem 2. Let S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ} be an AMS. Then

Q_{r} (Δ_{LS}, q_{0}) \subseteq Q_{r} (Δ_{1}, q_{0}) .

Proof: Let q∈Q_r(△_LS, q₀). From the definition of Q_r(△_LS, q₀), ∃σ∈L(△_LS /S) such that δ_{△_LS}(q₀, σ) = q. By mathematical induction on the length of the event string |σ|, we prove in the following that σ∈L(△₁/S), so δ_△₁(q₀, σ) = q, q∈Q_r(△₁, q₀). 1) If |σ|=0, σ = ε, then q = q₀, the conclusion follows. 2) Suppose that the conclusion holds when |σ|=l≥0. If |σ|=l+1, let σ = σ₁π, |σ₁|=l. Then, σ∈L(△_LS /S) and δ_{△_LS}(q₀, σ) = q imply δ_{△_LS}(q₀, σ) = δ_{△_LS}(δ_{△_LS}(q₀, σ₁), π) = q. Therefore, both δ_{△_LS}(q₀, σ₁) = q₁ and δ_{△_LS}(q₁, π) = q are defined. δ_{△_LS}(q₀, σ₁) is defined implies σ₁∈L(△_LS /S) from the definition of L(△_LS /S). Additionally, by the inductive hypothesis, σ₁∈L(△_LS /S) and |σ₁|=l imply

σ_{1} \in L (Δ_{1} / S) and δ_{Δ_{1}} (q_{0}, σ_{1}) = q_{1}

(11)

Since δ_{△_LS}(q₁, π) = q is defined, π∈△_LS(q₁). So it follows that BA accepts q and q satisfies NHC. By Lemma 9, BA accepts q implies that MBA accepts q. Let MBA(q)=(Accept, q₂). By Lemma 10, q satisfies NHC₂ and MBA(q)=(Accept, q₂) imply that q₂ satisfies ARC. Thus, we have that π∈△₁(q₁) and δ_△₁(q₁, π) = q. Combining δ_△₁(q₁, π) = q with (11), we get δ_△₁(q₀, σ₁π) = δ_△₁(q₀, σ) = q, σ∈L(△₁ /S). Hence, it follows by induction that q∈Q_r(△₁, q₀) and Q_r(△_LS, q₀) ⊆Q_r(△₁, q₀). ▪

We design the following algorithm, Algorithm ES, which is based on the breadth-first search, to get all reachable states from the initial state under a policy.

Algorithm ES

INPUT: An AMS S = {R, C, P, ρ, Q, q₀, Σ, ξ, δ}, and a supervisory control policy △.

OUTPUT: Q_r(△, q₀).

Step 1: Initialization

Q_r(△, q₀)=∅;

QUEUE=NULL (empty queue);

enqueue(QUEUE, q₀);

Q_r(△, q₀) = {q₀} ∪Q_r(△, q₀);

Step 2: Main body

Begin

While (QUEUE !=NULL)

q = dequeue(QUEUE); /* Return the element at the front of the queue and remove it from the queue. */

For (each event π∈△(q) ∩ξ(q))

q₁ = δ(q, π)

If (q₁∉Q_r(△, q₀))

Q_r(△, q₀) = {q₁} ∪Q_r(△, q₀);

enqueue(QUEUE, q₁);

End If

End For

End While

End

Example 2. Reconsider the system S in Example 1. By using Algorithm ES, we have that |Q_r(△_LS, q₀)| and |Q_r(△₁, q₀)| are 3,978,720 and 6,101,859, respectively.

Furthermore, we have tried over 100 system instances. We have found that our policy △₁ achieves about 40% improvement in the number of the reachable states over △_LS on average.

From Theorem 2. we know that Q_r(△_LS, q₀) is a subset of Q_r(△₁, q₀). Now we use an example to show that Q_r(△_LS, q₀) is a proper subset of Q_r(△₁, q₀), that is, there are states which are in Q_r(△₁, q₀), but not in Q_r(△_LS, q₀).

Consider two more states named q′ and q″, which are described as follows. In comparison with the state q that is shown in Figure 1, q′ has only one p₂₁ in r₆ and has an additional completed part instance p₁₂ staying in r₂. The difference between q′ and q″ is that q″ has no part instance p₂₆ staying in r₂. We have that q′∉Q_r(△_LS, q₀) and q″∉Q_r(△_LS, q₀). To see this, we note that q′ is rejected by BA, NHC₁ and NHC₂, and q″ is accepted by BA, but is rejected by NHC₂. Nevertheless, both q′ and q″ are accepted by MBA, and both of the states MBA(q′) and MBA(q″) satisfy ARC. Moreover, it is easy to verify that both q′ and q″ are in Q_r(△₁, q₀).

Discussion

We address how to improve the policy flexibility for the robust supervisor in AMSs each with a specified unreliable resource. Our policy has advantages over the original one in permissiveness. However, both our policy and the original one have the following two limitations. First, it can only handle the systems each with a single unreliable resource; however, a real system might have more than one unreliable resource. Second, the inherent drawback of all the Banker’s Algorithms makes it impossible to get a general optimal control policy.

The aforementioned limitations may lead to some open issues. Using the underlying idea in this paper and the associated existing policies in literature, it is possible to extend the policy proposed here to obtain robust supervisory controllers with more permissiveness for AMSs with multiple unreliable resources. However, it seems to be rather difficult for the policy’s extension to the systems where each part type may require multiple unreliable resources due to the combinatory nature of such systems. As far as the control optimality is concerned, there is a lack of generally accepted robust supervisory control policies with optimal deadlock avoidance even for a simple class of AMSs. Another open issue is as follows. Though our policy can guarantee the robust deadlock-free operation of the AMSs, the performance measures or indexes such as the maximal production level or the minimal makespan cannot be guaranteed until a suitable scheduling algorithm is proposed.

Conclusion

In this paper, we proposed a robust supervisory control policy for deadlock avoidance in a class of AMSs each with one specified unreliable resource. Specifically, our policy consists of a modified version of the well-known Banker’s Algorithm, and the available resource constraints. In comparison with the original one, our policy imposes less restrictive constraint on the system and is more concise. Moreover, it is the most important that evidence shows that our policy achieves a great improvement in the permissiveness of the policy.

Footnotes

Acknowledgements

The authors would like to thank the editor and all anonymous reviewers for their thoughtful comments and suggestions that greatly helped in improving the presentation and technical quality of this paper.

Funding

This work is supported by the National Natural Science Foundation of China under grants 50975224 and 60774083, China Postdoctoral Science Foundation funded project under grant 2013M532064 and the Natural Science Foundation of Fujian Province of China under grants 2013J05105 and 2010J01354.

References

Chao

Chen

. (2012) A best deadlock control for S³PMR to reach all states. Asian Journal of Control 14: 278–283.

Chen

Zhou

(2012) Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans 42: 615–629.

Chew

Lawley

(2006) Robust supervisory control for production systems with multiple resource failures. IEEE Transactions on Automation Science and Engineering 3: 309–323.

Chew

Wang

Lawley

(2009) Robust supervisory control for product routings with multiple unreliable resources. IEEE Transactions on Automation Science and Engineering 6: 195–200.

Chew

Wang

Lawley

(2011) Resource failure and blockage control for production systems. International Journal of Computer Integrated Manufacturing 24: 229–241.

Fanti

Zhou

(2004) Deadlock control methods in automated manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans 34: 5–22.

Hsieh

(2007) Analysis of flexible assembly processes based on structural decomposition of Petri nets. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans 37: 792–803.

Hsieh

(2011) Robustness analysis of non-ordinary Petri nets for flexible assembly/disassembly processes based on structural decomposition. International Journal of Control 84: 496–510.

Zhou

(2012) Liveness and ratio-enforcing supervision of automated manufacturing systems using Petri nets. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans 42: 392–403.

10.

Huang

Pan

Zhou

(2012) Computationally improved optimal deadlock control policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans 42: 404–415.

11.

Jeng

Xie

Peng

(2002) Process nets with resources for manufacturing modeling and their analysis. IEEE Transactions on Robotics and Automation 18: 875–889.

12.

Lawley

Sulistyono

(2002) Robust supervisory control policies for manufacturing systems with unreliable resources. IEEE Transactions on Robotics and Automation 18: 346–359.

13.

Liu

Hanisch

. (2012) Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans 42: 178–191.

14.

Liu

Jiang

Zhou

(2010) Two simple deadlock prevention policies for S³PR based on key- resource/operation-place pairs. IEEE Transactions on Automation Science and Engineering 7: 945–957.

15.

Nazeem

Reveliotis

(2012) Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the nonlinear case. IEEE Transactions on Automatic Control 57: 1670–1684.

16.

Park

(2012) Robust and nonblocking supervisory control of nondeterministic discrete event systems with communication delay and partial observation. International Journal of Control 85: 58–68.

17.

Piroddi

Cordone

Fumagalli

(2008) Selective siphon control for deadlock prevention in Petri nets. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans 38: 1337–1348.

18.

Reveliotis

(1999) Accommodating FMS operational contingencies through routing flexibility. IEEE Transactions on Robotics and Automation 15: 3–19.

19.

Uzam

(2002) An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. International Journal of Advanced Manufacturing Technology 19: 192–208.

20.

Wang

Zhou

(2012) Controllability conditions of resultant siphons in a class of Petri nets. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans 42: 1206–1215.

21.

Wang

Chew

Lawley

(2008) Using shared-resource capacity for robust control of failure-prone manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans 38: 605–627.

22.

Wang

Chew

Lawley

(2009) Guidelines for implementing robust supervisors in flexible manufacturing systems. International Journal of Production Research 47: 6499–6524.

23.

Zhou

(2001) Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems. IEEE Transactions on Robotics and Automation 17: 658–669.

24.

Zhou

(2011) Intelligent token Petri nets for modelling and control of reconfigurable automated manufacturing systems with dynamical changes. Transactions of the Institute of Measurement and Control 33: 9–29.

25.

Zhou

(2008) Resource-oriented Petri net for deadlock avoidance in flexible assembly systems. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans 38: 56–69.

26.

Xing

Zhou

Liu

. (2009) Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans 39: 188–199.

27.

Xing

Zhou

Wang

. (2011) Resource-transition circuits and siphons for deadlock control of automated manufacturing systems. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans 41: 74–84.

28.

Xing

Han

Zhou

. (2012) Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy. IEEE Transactions on Systems Man and Cybernetics Part B: Cybernetics 42: 603–615.

29.

Yue

(2011) Property of liveness in sequential resource allocation systems based on Petri net. Chinese Journal of Computer Science 38: 267–271.