Robust Deadlock Avoidance Policy for Automated Manufacturing System With Multiple Unreliable Resources

Jianchao Luo, Zhiqiang Liu, Shuogang Wang, and Keyi Xing

Abstract—This work studies the robust deadlock control of automated manufacturing systems with multiple unreliable resources. Our goal is to ensure the continuous production of the jobs that only require reliable resources. To reach this goal, we propose a new modified Banker’s algorithm (MBA) to ensure that all resources required by these jobs can be freed. Moreover,a Petri net based deadlock avoidance policy (DAP) is introduced to ensure that all jobs remaining in the system after executing the new MBA can complete their processing smoothly when their required unreliable resources are operational. The new MBA together with the DAP forms a new DAP that is robust to the failures of unreliable resources. Owing to the high permissiveness of the new MBA and the optimality of the DAP, it is tested to be more permissive than state-of-the-art control policies.

Nomenclature

I. Introduction

WITH the rapid development of information technology, a growing number of traditional manufacturing systems are reformed into automated manufacturing systems (AMSs)to improve the economy profit and enhance the competitiveness. As a consequence, the degree of resource sharing in AMSs becomes increasingly high. The shared resources together with the interacting parts may cause deadlocks under which the whole system or a part of it stalls indefinitely.Therefore, many researchers focus on solving such deadlocks,and propose different kinds of control policies [1]–[17]. Most of them are only applicable for AMSs without unreliable resources.

Although a great deal of techniques have been applied to extend the useful life of resources in AMSs, unreliable resources are still inevitable. The failures of unreliable resources will block the production of the jobs that require them. Since the resources occupied by the blocked jobs are required by other jobs, such an occupation may cause the whole AMS stalled. Thus, developing efficient control policies to deal with such blockages in AMSs is necessary.

More and more researchers realize the importance and propose different kinds of robust control policies [18]–[36].Liuet al. [27] concentrate on the robust control of AMS with unreliable resources. They model the system by the Petri net(PN) and develop a PN-based controller to ensure its liveness.Wuet al. [33] investigate the system studied in [27]. They construct a constraint set for each minimal siphon and add a controller to restrict its activities. Differing from the controller in [27], their controller can ensure the continuous production of all jobs even if some unreliable resource breaks down.

All resources in the AMSs in [21], [22], [25]–[27], [33] are machines or robots, whereas those in [18]–[20], [23], [24],[28]–[32], [34]–[36] are workstations with a machine for processing jobs and a buffer space for storing jobs. Lawley[23] pioneers the study on the control of such AMS with an unreliable resource. By combining a set of resource order constraints with a set of neighborhood constraints, he proposes a robust control policy. In order to make a controlled AMS more permissive, five different methods have been proposed in [24], [28], [29], [32], and [36], respectively.Chewet al. [18] pioneer the study on the control of AMS with multiple unreliable resources. They develop a robust DAP that is made up of an MBA and several neighborhood constraints.Yueet al. [34] improve the permissiveness of the MBA in[18] by moving the jobs that finish their operations on unreliable resources out of the system to release buffers. Chewet al. [19] and Yueet al. [35] present two solutions to relax the restriction on AMSs in [18] that a job requires no more than one unreliable resource.

An unreliable resource may fail when it is working(processing jobs) because its bearing may be worn out. Also,it may fail when it is idle (not processing jobs) because its electronic components may be affected with damp. We study the robust control problem of AMSs with multiple unreliable resources that may fail when they are working or idle. The studied AMSs are different with those in [18], [19], [30], [34],[35], where unreliable resources can fail only when they are working. The studied AMSs are modeled by automata models and PN models. Based on the developed models, a new version of MBA is developed and the PN-based DAP in [16]is introduced. They together ensure that AMS can always produce those jobs that only require operational resources if no additional unreliable resources fail. Compared with the controllers in [18], [20], [23], [24], [27], [28], [31], [32],[34]–[36], ours owns higher permissiveness. Moreover, the system controlled under it is also robust to the failure of unreliable resources that may fail when they are idle.

Main contributions are summarized as below.

1) A new MBA is proposed, which is proved to be more permissive than the improved version in [34].

2) The new proposed MBA can be integrated with any DAP for system of simple sequential process with resources (S3PR[3]) in the same way as with the DAP in [16], which eventually leads to improved performance of our control policy if a better DAP for S3PR is proposed.

3) We study the robust deadlock control of AMSs where resources are workstations and unreliable resources may fail when they are working or idle for the first time.

4) The proposed robust DAP exhibits higher permissiveness than existing ones for systems with multiple unreliable resources or a single one.

The rest paper is organized as follows. Section II models the studied AMSs. A robust DAP is developed in Section III.Section IV illustrates its effectiveness. The whole work is concluded in Section V.

II. Modeling of AMSs

This section describes the considered AMSs. Thereafter, their automata and PN models are established. The following two reasons encourage us to develop both automata and PN models.Firstly, almost all existing control policies for the studied systems are established based on automata models. Theoretical comparison with existing policies is necessary to illustrate the effectiveness of our policy. Such a comparison can only be conducted under automata models. Secondly, we will introduce a PN-based optimal DAP that is proposed for AMSs without unreliable resources to the studied AMSs. The introduced policy is not understandable under the automata model.

A. Automata Model

A resource in the studied AMS has a machine and a buffer space, which are used to process and store jobs, respectively.A buffer space may contain several buffers. Each buffer can hold a job at a time. All buffer spaces are always reliable,while several machines are unreliable. A resource is unreliable if it contains an unreliable machine. Unreliable resources may fail when they are working or idle. Suppose that their failures never destroy the jobs being processed. Each job requires no more than one unreliable resource. Note that the studied AMSs are more general than those in [18] and [34], where unreliable resources can fail only when they are working.

The system is described as a six-tuple S = {R,J,Q,Σ,ξ,δ},whereR= {r1,r2, …,rm} =RU∪RRwithRU(RR) being the set of unreliable (reliable) resources,andRU∩RR= ?. LetC(r) denote the number of buffers of resourcer.

Jrepresents the set of job (or part) types.Ji= 〈Ji1,Ji2, …,Ji|Ji|〉 ∈Jis a sequence of operation stages withJikbeing itskth operation stage. Letρ(Jik) denote the resource required byJik. All job instances ofJikdwell in the buffers ofρ(Jik). Let Π(r) = {Jik:ρ(Jik) =r} denote the set of operation stages that require resourcer.

Qis the set of all system states.is a state withλi∈ {1, 0} being the status ofri∈RU(1 if operational, 0 if failed), andxjk(yjk) ∈Zbeing the number of finished (unfinished) job instances ofJjk.Specially,q0∈Qis the initial state withλi= 1 forand

Σ=Σc∪Σurepresents the set of all system events withΣc(Σu) being the set of controllable (uncontrollable) events.Σc=whererepresents the assignment ofρ(Jjk) to a job instance ofJjk, andrepresents the movement of a finished job ofJjout of S.Σu=wherewithβjkrepresenting the completion of service for a job instance ofJjkandwithκi(ηi) representing the failure(repair) ofri∈RU.

δ:is a mapping that associatesq∈Qand an eventπ∈ξ(q) to a new state, i.e.,δ(q,π), which is obtained after enablingπatq.

Note that the above automata model and that in [35] only differ in the condition for resource failures. In this work,ri∈RUmay fail ifλi= 1; while in [35],ri∈RUmay fail ifλi= 1 and

Letσ=π1π2···πkbe a string of events ofΣ.σis feasible fromq∈Qif ?i∈Zk, ?qi+1=δ(qi,πi) ∈Q, whereq1=q.Then,qi+1is called reachable fromq. LetQR(q) represent the set of states reachable fromq, andQR(q, Δ) represent the set of states reachable fromqunder control policy Δ.

B. PN Model

We omit the preliminaries of PN in our paper. They can be found in [37]–[49]. The PN model of a studied system is defined below.

Definition 1:A studied AMS is modeled by a PNN= (P∪PR,T,F) where

b)PR= {r1, …,rm}, whereri∈PRrepresents the buffer space of resourceri;

c)where? ?i,j∈Znand

d) ?i∈Zn,Pi∪Tigenerates a subnet that is a state machine;

e) ?i∈Zm, ?a minimalP-SemiflowYisuch thatand

f)

A bri ef description of above mentioned definitions is as following:

i) Definition 1-a) suggests thatpij∈Piis the operation place ofJij.

ii) Definition 1-c) suggests thattij∈Tiis a transition which is corresponded toαij. Operation placepijrequires a resourceρ(pij) =ρ(Jij). Thus, the PN model is corresponded to the automata model. As we stated earlier, the introduced PN-based DAP is proposed for AMSs without unreliable resources. It cannot handle uncontrollable events. Thus, only the controllable events are modeled in the PN model. For more details about the PN models of uncontrollable events, please refer to [35].

iii) Definition 1-e) restricts that all buffer spaces can never be created or destroyed and they must be used by some operations.denotes the set of operation places that useri.

The initial marking ofN, i.e.,M0, represents no job instance in the system. Thus, ?p∈P,M0(p) = 0, and ?ri∈PR,M0(ri)=C(ri). All markings ofNreachable fromM0is represented byR(N,M0).

Since the PN model is corresponded to the automata model,a state ofQR(q0) is corresponded to a marking of R(N,M0).Letis defined below.and ?ri∈PR,M(ri) =

There is a difference between the above PN model and that in [35], i.e., our PN models all controllable events while only a part of controllable events are modeled in the PN in [35].

Fig. 1. PN model of the system in Example 1.

Let(o)t(t(o)) represent the input (output) operation places oft∈T, and(r)t(t(r)) represent its input (output) resource places.t∈Tis enabled atM∈ R(N,M0) if (a)M((o)t) > 0 (tis processenabled) and (b)M((r)t) > 0 (tis resource-enabled). Only enabled transitions can fire.

III. Robust Deadlock Avoidance Policy

Initially, the properties that a robust control policy for AMSs with multiple unreliable resources should satisfy are reviewed. Later on, a DAP is proposed to satisfy them.

A. Properties for a Robust Control Policy

The properties that a robust control policy should have are firstly discussed in [18], where motivating examples for these properties can be found. For economy of space, we recall them briefly.

If all jobs not requiring failed resources are possible to be completed from a state, then the state is called as a feasible initial (FI) state. A robust control policy should guarantee that a state of a system can always be treated as an FI state.Formally, the properties presented in [18] are recalled as follows.

Definition 2 [18]:A control policy Δ is robust to the failures ofRUif a) it guarantees the continuous production of jobs not requiring failed resources if no additional failures or repairs occur; b) it only admits states that are FI if some additional failure occurs; and c) it only admits states that are FI if some additional repair occurs.

By Definition 2, we know that a robust control policy should guarantee that the system operates normally when no resource fails, which can be found in Definition 2-a). Also, it should guarantee that the system can normally process those jobs not requiring failed resources when a part of the unreliable resources fail, which can be found in Definition 2-b) and 2-c).

The aim of this work is to propose a robust DAP that satisfies properties in Definition 2. Note that such an aim is the same as that in [18] and [34]. Since the studied AMSs in this work are more general than those in [18] and [34], our work is more challenging than those in [18] and [34]. The proposed robust DAP contains two parts: a new MBA and a PN-based DAP, which are given as follows.

B. A New Modified Banker’s Algorithm

Before proposing the new MBA (MBAL), we review some definitions about the classification of resources and operation stages as follows.

By Definition 4, J1is the set of operation stages whose jobs do not require any FD resources in their remaining routes. J2is the set of operation stages whose jobs occupy unreliable resources but those jobs in their next stages do not require any FD resources in their remaining routes. J3is the set of operation stages whose jobs require FD resources in their remaining routes but do not occupy FD resources currently.

Givenq∈Q, MBALtries to move 1) all jobs at stageJij∈J1(q) out of S; 2) all jobs at stageJij∈ J2(q) that have finished their current operations onρ(Jij) out of S; and 3) all jobs at stageJij∈ J3(q) into the first-met FD resource inLet J(q) =represent the set of operation stages considered by MBALatq.

A different version of MBA that considers the same set of operation stages has been proposed in [34]. It is denoted as MBAY. Givenq∈Q, MBAYtries to find an ordering of J(q)such that the jobs at the according operation stages can be moved to proper positions sequentially. If such an ordering is not found, it rejectsq.

Note that even if such an ordering does not exist, there may still be a string of events by which all jobs can be moved to proper positions. To see this, let us reconsider Example 1.Consider a stateq= 1 + 1 +x11+x21∈Q. J(q) = {J11,J21},J1(q) = {J11}, and J3(q) = {J21}. The first-met FD resource in?21isr4. Thus, MBAYtries to move the job at stageJ11out of the system and that at stageJ21intor4. A job at stageJ11occupies the only one buffer ofr1and needs to be processed onr3, while a job at stageJ21occupies the only one buffer ofr3and needs to be processed onr1. None of them can be moved to their proper positions directly. Thus, the MBAYrejectsq. In fact, after moving the job at stageJ11tor2fromq,the system reachesq1= 1 + 1 +y12+x21. There is an ordering of J(q1), i.e.,J21J12such that all jobs can be moved to their proper positions sequentially. Motivated by such an example,we modify the MBAYfurther and propose a new version of MBA, i.e., MBAL. MBALcan admit more states than MBAYdoes, to be shown later.

Givenq∈Q, letbe an indexing function on J(q) withbeing theith operation stage of J(q). In MBAL,Λais an array withΛa[j] recording the number of idle buffers ofrj∈R.Λris a two-dimensional array withΛr[i][j] = 1 if a job atζ(i) requiresrj∈Rto be moved to its proper position, and otherwiseΛr[i][j] = 0.Λois another two-dimensional array withΛo[i][j] =xst+ystifζ(i) =Jstandρ(Jst) =rj, and otherwiseΛo[i][j] = 0.

MBALcontains two main parts: Initialization and MBA1.Initialization initializesΛa,Λr, andΛofor an input stateq.MBA1is equivalent to the main body of MBAY. Given a stateq, MBALinvokes Initialization to initializesΛa,Λr, andΛoforq. Then, MBALinvokes MBA1to judge ifqis admitted by MBA1. If it is admitted, MBALaccepts it too. Such a process corresponds to Lines 1?4 in MBAL. Otherwise, MBALtries to find a job remaining in the system that can be moved a step forward. If such a job is found, MBALinvokes MBA1to judge if the state obtained after moving such a job is admitted by MBA1. If it is admitted, MBALaccepts it too. Otherwise,MBALtries to move such a job two steps forward and invokes MBA1to judge the state obtained after such a movement. If it is admitted, MBALaccepts it too. This process repeats until MBALaccepts the resulting state or such a job cannot be moved forward more. Such a process corresponds to Lines 8?20 in MBAL. If such a job cannot be moved forward more,MBALtries to find another job remaining in the system that can be moved a step forward. Then, the process corresponding to Lines 8?20 repeats. Such a process repeats until all jobs remaining in the system have been tried. This process corresponds to the for-loop in Lines 6-21. Finally, MBALrejectsqif all jobs have been tried and no resulting state is accepted by MBA1. Formally, Algorithm I (MBA1),Algorithm II (Initialization), and Algorithm III (MBAL) are as follows.

Algorithm I. Modified Banker’s Algorithm MBA1

Lemma 1:Algorithm I is of polynomial complexity.

Proof:LetandThere are at mosts1elements inIand at mosts2jobs on unreliable resources, thus the while-loop in Algorithm I can be iterated at most (s1+s2) times. In the while-loop, all Lines except for Line 3 can be completed in a constant time. The complexity of Line 3 isO(s1×m). Thus the total complexity of Algorithm I isO((s1+s2) ×s1×m).

Algorithm II. Initialization

Algorithm III. MBAL

Lemma 2:Algorithm II is of polynomial complexity.

Proof:The complexities of the for-loops in Lines 2–4, Lines 5–7, Lines 8–10, and Lines 11–22 areO(s1×m),O(s1),O(s1×m), andO(s1×m), respectively, where. Thus the complexity of Algorithm II isO(s1×m).

Theorem 1:Algorithm III is of polynomial complexity.

Proof:The for-loop in Lines 6–21 can be iterated at mosttimes. The complexity of an iteration is dominated by the for-loop in Lines 13–20, which can be iterated at mosts3= max{|Ji|:i∈Zn} times. The complexity of an iteration in such a loop isO(Algorithm I) +O(Algorithm II) =O((s1+s2) ×s1×m). Thus the complexity of Algorithm III isO(s1×s3× (s1+s2) ×s1×m) =O(s12× (s1+s2) ×s3×m).

Theorem 2:QR(q0, MBAY) ?QR(q0, MBAL).

Proof:Givenq∈QR(q0, MBAY), let (Λa,Λr,Λo) =Algorithm II(q). Sinceq∈QR(q0, MBAY), MBA1(q,Λa,Λr,Λo) = (1,q1), whereq1∈Qis the output state. Since MBA1(q,Λa,Λr,Λo) = (1,q1),q∈QR(q0, MBAL).

Remark 1:By Theorem 2, all markings reachable under MBAYfromq0are reachable under MBALfromq0.

C. Failure Dependent Subnet and Its PN-based DAP

MBALcan ensure that all jobs in S can be moved out of S or into the first-met FD resources in their remaining routes.However, it cannot ensure that those jobs remaining in the system after such movements can be moved out of S. To see this, consider a state of the system in Fig. 1, i.e.,q= 1 + 1 +x31+x41. Obviously, MBAL(q) = (1,qe), whereqe= 1 + 1 +x32+x41. Atqe, a job is inr5and waiting for being produced byr6, while a job is inr6and waiting for being produced byr5. Thus, a deadlock occurs atqe. To avoid such deadlocks, a PN-based DAP is introduced.

Given a stateq∈QR(q0, MBAL), after executing MBALon it, all jobs remaining in the system are in the buffers of FD resources. To ensure the resulting state is deadlock-free, we only need to ensure the safety of a subsystem that consists of FD resources. Thus, we reduce the PN model of an AMS below.

1) Failure Dependent Subnet (FDS)

Let ΩF= {pij:ρ(pij) ∈RF} be the set of operation places where jobs occupy FD resources. Givenpij∈ ΩF, let Ω(pij) ={pij} ∪ {pic:c

Definition 5:The FDS ofN= (P∪PR,T,F) is a PNNf=(Pf∪RF,Tf,Ff), which is obtained by the following three steps:

1) Delete all resource places except for those inRFand those arcs connected to them fromN.

2) Delete all operation places except for those inPf, all arcs connected to these places, and all isolated transitions.

3) For eachpij∈ ΩFwith |Ω(pij)| > 1, delete (r,tij), wheretij=?pijandr=ρ(pij). Letpikbe the operation place in Ω(pij)with the smallest index andtik=?pik. If (tik,r) ?F, then add (r,tik); otherwise, delete (tik,r).

Theorem 3:ifthen ?r1∈{RU{r}},?kt∩RF(r1) = ?.

Proof:Suppose thatandρ(Jk(t+c)) ∈RF(r1), wherec∈Z+. Since∈Z?ρ(Jk(t+c+d)) =r1. Sinceρ(Jk(t+e)) =r≠r1. It is a contradiction to the hypothesis that a job requires no more than one unreliable resource.

Remark 2:By Theorem 3, if a job requires no more than one unreliable resource, then all sets of FD resources on unreliable resources are nonintersecting.

?ri∈RU, letNfi= (Pfi∪RF(ri),Tfi,Ffi) be the subnet corresponding tori, wherePfi= {Ω(pst):ρ(pst) ∈RF(ri)},Tfi={?pst,pst?:pst∈Pfi},Ffi= {(p,t), (t,p) ∈Ff:p∈Pfi∪RF(ri),t∈Tfi}.

Corollary 1:?ri,rj∈RU,Nfiis independent ofNfj.

Proof:By Theorem 3,RF(ri) ∩RF(rj) = ?. By the definition of Ω(p) forp∈ ΩF, ?p1,p2∈ ΩF, Ω(p1) ∩ Ω(p2) = ?. Thus,Pfi∩Pfj= ?,Tfi∩Tfj= ?, andFfi∩Ffj= ?.

Remark 3:By Corollary 1,Nfis the combination of allNfi,whereri∈RU.

Example 3:Consider the system in Example 1, ΩF= {p24,p32-p34,p41,p42,p44}, Ω(p24) = {p21–p24}, Ω(p32) = {p31,p32},Ω(p33) = {p33}, Ω(p34) = {p34}, Ω(p41) = {p41}, Ω(p42) = {p42},and Ω(p44) = {p43,p44}. To derive its FDS, we first delete resource placesr1,r2, andr3, and arcs related with them from Fig. 1. Then, we delete operation placesp11,p12, andp13, arcs related with them, and isolated transitionst11,t12,t13, andt14.Finally, delete arcs (r4,t24), (r5,t32), and (r7,t44), and add arcs(r4,t21), (r5,t31), and (r7,t43). The FDS of the system is exhibited in Fig. 2, which is the composition ofNf4andNf7.

Fig. 2. FDS of the AMS in Example 1.

GivenM∈ R(N,M0), letγ(M) =M1denote the marking ofNfcorresponded toM, which is defined below. ?p∈Pf,M1(p) =M(p), and ?r∈RF,M1(r) =C(r) ?M(Ω(r)).Specially, letMf0=γ(M0) denote the initial marking ofNf.

2)PN-based DAP for FDS

Letpij∈ ΩFbe an operation place inNfwith |Ω(pij)| > 1. InNf, all places in Ω(pij) useρ(pij). By treating them as one operation place, FDS belongs to the class of S3PR [3]. Thus,the DAP in [16] can be adopted to ensure FDS deadlock-free.

Xinget al. [16] characterize deadlocks in S3PR as saturated maximal prefect resource-transition circuits (MPRT-circuits).If a resourcerbelongs to two MPRT-circuits that do not include each other andC(r) = 1, thenris called as a center resource. For S3PR without center resources, Xinget al. [16]develop a one-step-look-ahead deadlock search (DS)algorithm, which is proved to be optimal andO(DS) =O(s4),whereFor S3PR with ξ-resources, Xinget al.[16] reduce them to obtain a reduced net without center resources. Then, by applying DS to the reduced net and using the controlled reduced net as a supervisor for the original net,a suboptimal polynomial controller for the original net is obtained. For simplicity, let DS be the DAP forNfwith or without center resources.

Remark 4:SinceNfis the composition of allNfi, whereri∈RU, DS can be treated as the composition of all DSi, where DSiis a DAP forNfi.

Givenq∈Q,qis admitted by DS ifγ(χ(q)) ∈ R(Nf,Mf0,DS), where R(Nf,Mf0, DS) is the set of all markings ofNfreachable fromMf0under DS.

Given a stateqthat is admitted by DS, letπ∈ξ(q) be an event enabled atq, andq1=δ(q,π). Now, we have the following three lemmas.

Lemma 3:Ifπ∈Σu,γ(χ(q1)) ∈ R(Nf,Mf0, DS).

Proof:By the definition ofχ, we know thatχ(q) =χ(q1) ifπ∈Σu1orΣu2. Since0, DS).

Remark 5:By Lemma 3, the occurrences of uncontrollable events are not prohibited by DS.

Lemma 4:Ifπ=αijis a controllable event, and the transition corresponding toαij, i.e.,tij?Tf,γ(χ(q1)) ∈ R(Nf,Mf0, DS).

Proof:Sincetij?Tf, the occurring ofαijdoes not changeM(p) ?p∈Pf, whereM=γ(χ(q)). By the definition ofγ, we know thatγ(χ(q)) =γ(χ(q1)). Sinceγ(χ(q)) ∈ R(Nf,Mf0, DS),γ(χ(q1)) ∈ R(Nf,Mf0, DS).R(Nf,Mf0, DS).

Lemma 5:Ifπ=αijis a controllable event, the transition corresponding toαij, i.e.,tij∈Tf, and(r)tij= ? inNf,γ(χ(q1)) ∈

Proof:Sincetij∈Tf, and(r)tij= ?, the occurring ofαijwhich is corresponded to the firing oftijdoes not increaseM(r), ?r∈RF, whereM=γ(χ(q)). Thus, ?r∈RF,M(r) ≥M1(r), whereM1=γ(χ(q1)). SinceM∈ R(Nf,Mf0, DS),M1∈ R(Nf,Mf0,DS).

Let Ξ1and Ξ2denote the set of all controllable events described in Lemmas 4 and 5, respectively, and Ξ3=Σc{Ξ1∪ Ξ2}.

D. Proposed Robust DAP

Our policy for S = {R,J,Q,Σ,ξ,δ} is a function ΔLLXW:Q×Σ→{0, 1} defined below. Letq∈QR(q0, ΔLLXW) be a state andπ∈ξ(q) be an enabled event to be judged, andq1=δ(q,π). Ifπ∈Σu, then ΔLLXW(q,π) = 1. Else ifπ∈ {Ξ1∪Ξ2} and MBAL(q1) = (1,qe), then ΔLLXW(q,π) = 1. Else, let MBAL(q) = (1,qe),M=γ(χ(qe)), andtbe the transition corresponded toπ. ΔLLXW(q,π) = 1 if DS(M,t) = permitted and MBAL(q1) = (1,qe1).

Next, we prove that ΔLLXWsatisfies the three properties in Definition 2.

Lemma 6:Givenq∈QR(q0, ΔLLXW), let MBAL(q) = (1,qe)andσbe a sequence of events such thatq=δ(q0,σ), thenM=γ(χ(qe)) ∈ R(Nf,Mf0, DS).

Proof:We proveM∈ R(Nf,Mf0, DS) by mathematical induction over |σ| as below.

If |σ| = 0, thenq=δ(q0,σ) =q0. Thus, MBAL(q) =MBAL(q0) = (1,q0), andM=γ(χ(q0)) =Mf0∈ R(Nf,Mf0, DS).

Suppose that |σ| =n> 0,M∈ R(Nf,Mf0, DS). Letπ∈ξ(q)be an event enabled atq, andq1=δ(q0,σπ). Suppose thatq1∈QR(q0, ΔLLXW). Let MBAL(q1) = (1,qe1) andM1=γ(χ(qe1)).Now, we proveM1∈ R(Nf,Mf0, DS).

Case 1:π=βst∈Σu1. IfJst∈ J1(q) ∪ J3(q) ∪ J4(q), by MBAL,qe=qe1, thusM1=M∈ R(Nf,Mf0, DS). IfJst∈ J2(q),the job corresponding toβstwill be moved out of S by MBALatq1. Since such a job does not complete its service onρ(Jst),it will not be moved by MBALatq. Thus, all elements inqe1are equal to those inqeexcept forqe1(yst) =qe(yst) ? 1. Thus,M1(p) =M(p), ?p∈ {Pf{pst}}, andM1(pst) =M(pst) ? 1,wherepstis the operation place corresponding toJst. SinceM∈ R(Nf,Mf0, DS),M1∈ R(Nf,Mf0, DS).Case 2:π∈Σu2. By MBAL,qe=qe1, thusM1=M∈ R(Nf,Mf0, DS).

Case 3:π=αik∈ Ξ1. Sinceαik∈ Ξ1,Ji(k–1)∈ J1(q). Ifk≤|Ji|,Jik∈ J1(q1) and {J1(q) ∪ {Jik}} = { J1(q1) ∪ {Ji(k–1)}},J2(q) = J2(q1), and J3(q) = J3(q1). Otherwise, J1(q) = {J1(q1) ∪{Ji(k–1)}}, J2(q) = J2(q1), and J3(q) = J3(q1). Since the jobs at stageJi(k–1)orJikwill be moved out of S by MBAL,qe=qe1andM1=M∈ R(Nf,Mf0, DS).

Case 4:π=αik∈ Ξ2. Sinceαik∈ Ξ2,Ji(k–1)∈ { J2(q) ∪J3(q)}. IfJi(k–1)∈ J2(q) andk≤ |Ji|,Jik∈ J1(q1) and J1(q1) =J1(q) ∪ {Jik}, J2(q1) ∪ {Ji(k–1)} = J2(q), and J3(q1) = J3(q). IfJi(k–1)∈ J2(q) andk> |Ji|, J1(q) = J1(q1), J2(q) = J2(q1) ∪

{Ji(k–1)}, and J3(q) = J3(q1). Since the job at stageJi(k–1)orJikwill be moved out of S by MBAL,qe=qe1, andM1=M∈R(Nf,Mf0, DS).

IfJi(k–1)∈ J3(q),Jik∈ J3(q1) and J1(q1) = J1(q), J2(q1) =

J2(q), and J3(q1) ∪ {Ji(k–1)} = J3(q) ∪ {Jik}. Sinceαik∈ Ξ2,the first-met FD resource in?i(k–1)is the same as that in?ik.Since the job at stageJi(k–1)orJikwill be moved into the same FD resource,qe=qe1, andM1=M∈ R(Nf,Mf0, DS).

Case 5:π=αik∈ Ξ3. Lettjk∈Tfbe the transition corresponding toαik. Sinceq1∈QR(q0, ΔLLXW), DS(M,tjk) =permitted. Thus,M[tjk> =M2∈ R(Nf,Mf0, DS). Sinceαik∈Ξ3, the occurrence ofαikstands for moving a raw job that requires FD resources into the system or moving a job out of an FD resource. MBALwill move such a job into the first-met FD resource in?ik. Letσ1=αi(k+1)αi(k+2)...αi(k+c)be the sequence of controllable events corresponding to such a movement andT1=ti(k+1)ti(k+2)...ti(k+c)be the sequence of transitions corresponding toσ1. Then,qe1=δ(qe,αikσ1) andM2[T1>M1=γ(χ(qe1)). By Lemma 5, the firings of transitions inT1fromM2are permitted by DS,M1∈ R(Nf,Mf0, DS).

Proof:Recall thatq∈QR(q0, MBAL) only if 1) all jobs at stageJij∈ J1(q) can be moved out of S; 2) all jobs at stageJij∈ J2(q) that have finished their current operations onρ(Jij) can be moved out of S; and 3) all jobs at stageJij∈ J3(q) can be moved into the first-met FD resource in?ij. IfJij∈ J1(q),every eventπcorresponding to the movement in 1) is in {Σu1∪ Ξ1}. IfJij∈ J2(q), every eventπcorresponding to the movement in 2) is in {Σu1∪ Ξ1∪ Ξ2}. IfJij∈ J3(q), every eventπcorresponding to the movement in 3) is in {Σu1∪Ξ2}. Since all these events do not contain the completion of service events on unreliable resources, they are executable no matter whether unreliable resources are operational or failed.By Lemmas 3–5, all these events are permitted by DS. Thus,q1∈QR(q0, ΔLLXW). Since J1(q1) = J2(q1) = J3(q1) = ?,MBAL(q1) = (1,q1). By Lemma 6,γ(χ(q1)) ∈ R(Nf,Mf0, DS).

Lemma 8:?q∈Q? J1(q) = J2(q) = J3(q) = ? andM=γ(χ(q)) ∈ R(Nf,Mf0, DS), if ?ri∈RU?svi= 1 andM(Pfi) > 0,then ?tjk∈Tfi? DS(M,tjk) = permitted andq1=δ(q,αjk) ∈QR(q0, MBAL).

Proof:By Remark 4, DS is the composition of all DSi, ?ri∈RU. Since DSiis a DAP forNfiandM(Pfi) > 0, at least one transitiontjk∈Tfiis enabled atM.

Since J1(q) = J2(q) = J3(q) = ?, all jobs are in FD resources and allRRFare idle atq. Now, we consider the following four cases.

Case 1:k≤ |Jj|,ρ(Jjk) ∈RRF, andtj(k+1)∈Tfi. Since allRRFare idle atq,αjk∈ξ(q). Sincetj(k+1)∈Tfi, the job moved by eventαjkwill be further moved to an FD resource by MBAL.All resources required by such a movement are inRRF. Since all required resources are idle,q1=δ(q,αjk) ∈QR(q0, MBAL).

Case 2:k≤ |Jj|,ρ(Jjk) ∈RRF, andtj(k+1)?Tfi. Since allRRFare idle atq,αjk∈ξ(q). Sincetj(k+1)?Tfi, the job moved by eventαjkwill be moved out of S by MBAL. All resources required by such a movement are inRRF. Since all required resources are idle,q1=δ(q,αjk) ∈QR(q0, MBAL).

Case 3:k≤ |Jj| andρ(Jjk) ∈RF. Letρ(Jjk) =(r)tjk. Since DS(M,tjk) = permitted,ρ(Jjk) has at least one idle buffer, and henceαjk∈ξ(q). Sinceρ(Jjk) ∈RF, J1(q1) = J2(q1) = J3(q1) =?, thusq1∈QR(q0, MBAL).

Case 4:k= |Jj| + 1. Since DS(M,tjk) = permitted, there are some finished parts atJj(k–1), and henceαjk∈ξ(q). Sincek=|Jj| + 1, J1(q1) = J2(q1) = J3(q1) = ?, thusq1∈QR(q0, MBAL).

Remark 6:By Lemma 7, ΔLLXWguarantees that all jobs can be moved either out of the system or to the first-met FD resources in their remaining routes. By Lemma 8, if those jobs in FD resources do not require failed resources, they can be moved out of the system under ΔLLXW.

Remark 7:By Theorem 4, ΔLLXWguarantees that all jobs not requiring failed resource can be completed.

Corollary 2:?q∈QR(q0, ΔLLXW), all jobs not requiring resources in R(q) can be processed continuously if no additional failures or repairs occur.

Proof:By Theorem 4, ?σ∈ {Σc∪Σu1}*?δ(q,σ) =q1?Atq1, all resources except for those in {RF(r):r∈ R(q)} are idle. Thus, moving a job that does not require those resources in {RF(r):r∈ R(q)} is permitted by MBALand DS. Letq2∈QR(q0, ΔLLXW) be the state obtained after executing such a movement fromq1. By Theorem 4, such a job can be completed and moved out of S. The aforementioned process can be repeated if no additional failures or repairs occur.

Theorem 5:?q∈QR(q0, ΔLLXW), ifκi∈ξ(q),δ(q,κi) =q1is an FI state.

Theorem 6:?q∈QR(q0, ΔLLXW), ifηi∈ξ(q),δ(q,ηi) =q1is an FI state.

Proof:Sinceηi∈Σu,q1∈QR(q0, ΔLLXW). By Theorem 4,?σ∈ {Σc∪Σu1}*?δ(q1,σ) =q2? ?Jjk? {Jst∈ J:ρ(Jst) ∈{RF(r):r∈ R(q1)}},q2(xjk) +q2(yjk) = 0. Thus,q1is an FI state.Theorem 7:ΔLLXWis a robust DAP.

Proof:Corollary 2 and Theorems 5 and 6 prove that ΔLLXWhas properties 1–3 in Definition 2, respectively.

Remark 8:In the aforementioned process of proof, DS is merely treated as a DAP. It means that if there is another DAP that is better than DS, then it can be integrated with MBALto make a new robust DAP for the studied systems.

IV. Comparison Studies

In this section, we compare ΔLLXWwith those controllers for AMSs with |RU| = 1 and those controllers for AMSs with |RU| >1, respectively. To be fair, |QR(q0, ΔLLXW)| are computed under the assumption that unreliable resources can only fail when they are working.

Consider an AMS withRR= {r1,r3,r4,r5,r6},RU= {r2},C(r6) = 2,C(r1) =C(r2) =C(r3) =C(r4) =C(r5) = 1, andJ={J1,J2,J3,J4}. |J1| = |J2| = |J3| = 3, |J4| = 4,ρ(J22) =ρ(J42) =r1,ρ(J23) =ρ(J44) =r2,ρ(J13) =ρ(J31) =r3,ρ(J21) =ρ(J43) =r4,ρ(J11) =ρ(J33) =ρ(J41) =r5, andρ(J12) =ρ(J32) =r6. Seven controllers proposed in [23] (ΔL1), [24] (ΔL2), [28] (ΔL3), [29](ΔL4), [31] (ΔW1), [32] (ΔW2), and [36] (ΔY1) can be used for it. In [28], we have proved that ΔL3is more permissive than ΔL2andΔY1. Besides, in [29], we have proved that ΔL4admits more states than ΔL1does. Therefore, we only need to compare ΔLLXWwith ΔL3, ΔL4, ΔW1, and ΔW2. |QR(q0, ΔLLXW)| =32 039, |QR(q0, ΔL3)| = 29 659, |QR(q0, ΔL4)| = 19 075, |QR(q0,ΔW1)| = 835, and |QR(q0, ΔW2)| = 32 039. Obviously, ΔLLXWadmits many more states than ΔL3, ΔL4, and ΔW1do. Although ΔLLXWand ΔW2admit the same number of states, ΔLLXWcan handle AMS with |RU| > 1.

The illustrative AMS with |RU| > 1 is shown in Example 1.Five controllers proposed in [18] (ΔC1), [20] (ΔC2), [31] (ΔW1),[34] (ΔY2), and [35] (ΔY3) can be used for it. Yueet al. [34]have proved that ΔY2admits more states than ΔC1does.Therefore, we only compare ΔLLXWwith ΔC2, ΔW1, ΔY2, and ΔY3. |QR(q0, ΔLLXW)| = 73 572, |QR(q0, ΔC2)| = 22 662, |QR(q0,ΔW1)| = 3085, |QR(q0, ΔY2)| = 35 628, |QR(q0, ΔY3)| = 5106.Obviously, ΔLLXWadmits many more states than ΔC2, ΔW1,ΔY2, and ΔY3do. Moreover, ΔLLXWcan ensure the robustness of the AMSs where unreliable resources can fail when they are idle.

There are three main reasons why ΔLLXWadmits more states than ΔL3, ΔL4, ΔW1, ΔC2, ΔY2and ΔY3. At first, DS is optimal forNfwithout ξ-resources, while the neighborhood constraints in ΔW1, ΔW2, ΔC2, ΔY2and ΔY3are suboptimal. Secondly,MBALadmits more states than the MBAYin ΔL4and ΔY2.Thirdly, MBALtries to move every job that has finished its operation on an unreliable resource out of S to release the occupied buffer, while these jobs are not moved by ΔL3, ΔW1,ΔW2, ΔC2and ΔY3. Since these policies are so different,comparing them theoretically is still an open work. Besides,ΔY3is also applicable for AMSs where a job can require multiple unreliable resources. Extending ΔLLXWfor this kind of systems is in our research agenda.

V. Conclusion

This paper proposes a polynomial robust DAP for AMSs with unreliable resources, which consists of MBALand a DAP for the FDS of the system. MBALcan ensure that the jobs not requiring unreliable resources can be moved out of the system and those requiring unreliable resources can be moved into the first-met FD resources in their remaining routes. Also, it can guarantee that all jobs that have finished their operations on unreliable resources can be moved out of the system. The DAP can guarantee that all jobs that are in the system after executing MBALand do not require failed resources can be moved out of the system. MBALtogether with the DAP is proved to be robust to the failures of unreliable resources.Comparison results with existing policies show that our policy is more permissive than existing ones. Moreover, it can handle the AMS where unreliable resources may fail when they are idle or working. Proposing an optimal robust DAP for the studied AMS is hard but significant, which needs to be studied further. Another one is to propose a robust DAP for those AMSs with multiply unreliable resource requisitions.