OPTIMAL REPLACEMENT POLICIES FOR MULTI-STATE DETERIORATING SYSTEMS C. Teresa Lam and R. H. Yeh Department of Industcial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report No. 92-41 June 1992 Submitted to Naval Research Logisitcs (Revised, February 1993)

Optimal Replacement Policies for Multi-State Deteriorating Systems C. Teresa Lam and R. H. Yeh Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109 Abstract In this article we consider state-age-dependent replacement policies for a multi-state deteriorating system. We assume that operating cost rates and replacement costs are both functions of the underlying states. Replacement times and sojourn times in different states are all statedependent random variables. The optimization criterion is to minimize the expected long run cost rate. A policy improvement algorithm to derive the optimal policy is presented. We show that under reasonable assumptions, the optimal replacement policies have monotonic properties. In particular, when the failure rate functions are nonincreasing or when all the replacement costs and the expected replacement times are independent of state, we show that the optimal policies are only state-dependent. Examples are given to illustrate the structure of the optimal policies in the special case when the sojourn time distributions are Weibull. 1

1. INTRODUCTION This article studies the optimal replacement policies for a multi-state deteriorating system. We assume that the system is subject to both deterioration and random shocks. The operating condition of the system is characterized by the degree of deterioration and can be classified into a finite number of states. In each state, the system either gradually deteriorates to the next higher state or suddenly fails due to random shocks. Without maintenance action, the system will eventually fail. It is assumed that the system is monitored continuously such that the current state of the system is always known. When failures occur, the system must be replaced with a new identical system. The system can also be replaced at any point of time. The cost and time required to replace the system depend on the state of the system. In general, the operating cost rate, replacement cost, and replacement time increase as the system deteriorates. Therefore, it is desirable to replace the system before it fails to avoid operating or replacing the system in a highly deteriorating condition. Maintenance policies of stochastically failing systems have been widely investigated in the literature. The papers by McCall [8], Pierskalla and Voelker [12], and Valdez-Flores and Feldman [14] are excellent reviews of the area. Many papers in the literature concentrate on modeling the deteriorating process of a stochastically failure system by a Markov process because of the tractability of the resulting mathematical problems. For example, Luss [7], Mine and Kawai [9, 10], and Ohnishi et al. [11] investigated optimal inspection policies and Anderson [1], Kolesar [6] and Wood [15] studied optimal replacement policies for Markovian deteriorating systems. Under the Markovian formulation, the deterioration of the system is indicated only by the changes of states. It is assumed that the performance of the system within each state does not age, i.e., the probability of moving to a less desirable state does not increase in time or equivalently the failure rate function of the sojourn time distribution in each state is independent of time. Unfortunately, in practice this assumption may be invalid. The use of a semi-Markov process to model a deteriorating system has been studied before. Feldman [2] and Gottlieb [4] both used a semi-Markov process to model the cumulative damage process of a system that is subject to random shocks. Feldman [2] only considered control limit replacement policies and Gottlieb [4] investigated conditions under which a control limit replace2

ment policy is optimal when the failure rate function need not be increasing and replacement can be made at any time. Furthermore, So [13] used a parametric analysis to establish sufficient conditions for the optimality of control limit replacement policies for semi-Markovian deteriorating systems. The above papers focused on state-dependent policies, that is, an optimal replacement policy is restricted to the class of policies that a replacement action is taken only at transition times. In this paper, we allow a replacement policy to be state-age-dependent. In other words, the system can be replaced at any point of time. The problem we consider in this paper is closely related to the paper by Kao [5] and Feldman and Joo [3]. Kao studied both state-dependent and state-age-dependent replacement policies for a deteriorating system that is modeled by a semi-Markov process whose sojourn times in different states follow discrete distributions. He used policy iteration methods to derive optimal policies. He also showed that under sufficient conditions, the optimal state-dependent replacement policies are of control limit type. However, he did not investigate the structural properties of the optimal state-age-dependent replacement policies. Feldman and Joo [3] considered state-age-dependent replacement policies for a shock process. They developed an algorithm for finding the optimal replacement policy under some regularity conditions. They numerically showed that the algorithm is more efficient than Kao's or Gottlieb's algorithms. However, they assumed replacement is instantaneous and there are only two types of replacement costs, after or before failures. Furthermore, it is assumed that the times between shocks form a sequence of independent and identically distributed random variables. In this paper, we assume that replacement times are random. Replacement cost, operating cost, replacement time distributions and sojourn time distributions in different states are all statedependent. The goal of this study is to investigate optimal state-age-dependent replacement policies that minimize the expected long run cost rate. We show that under reasonable assumptions on operation cost rates, replacement costs, expected replacement times and failure rate functions, the optimal state-age-dependent replacement policies have monotonic properties. Furthermore, sufficient conditions for the existence of a state-dependent policy that is optimal over the set of all state-age-dependent policies are given. In particular, we show that if the failure rate function in each state is nonincreasing or if the replacement costs and the expected replacement times are 3

independent of state, then the optimal policies are only state-dependent. The remainder of this paper is organized as follows. The model and the mathematical formulation of the problem are given in Section 2. An iterative algorithm is given in Section 3 to derive the optimal state-age-dependent replacement policy. In Section 4, we study the structures of the optimal policies under various assumptions. In Section 5, we investigate the special case when all the sojourn time distributions are Weibull. 2. MATHEMATICAL FORMULATION Consider that the deterioration of a system at any point of time can be classified into one of a finite number of states 0, 1, *, n, n + 1. State 0 represents the process before any deterioration takes place, i.e., it is the initial new state of the system. The intermediate states 1,2,-* -, n are ordered to reflect their relative degree of deterioration (in ascending order). State n + 1 represents the terminal state (failure) of the deteriorating process. It is assumed that the time for the system to stay in state i follows a general absolutely continuous distribution Fi with finite mean pi and probability density function fi. Also, assume that Fi(O) = 0 and Fi(t) < 1 for all t E [0, oo). Let hi = fi/Fi, i.e., hi is the failure rate function of the sojourn time in state i. The deteriorating process of the system is characterized by a semi-Markov process with state space S = {0,, *, n, n + 1}. From state i, the deteriorating process will make a direct transition to state i + 1 with probability pi (pn = 0) due to gradual deterioration, or to state n + 1 with probability 1 - pi due to a random shock. It is clear that we only need to consider the case when pi > 0 for all i E {0, 1,. -,n - 1}, otherwise we can reduce the number of states. A flow diagram of such a system is illustrated in Figure 1. We assume that the replacement costs and times depend on the current state of the system. If the system is replaced in state i E S, the replacement cost is c, and the replacement time follows a distribution function Ri with a finite mean value ri. After the completion of each replacement, the system is renewed (back to state 0). During a replacement, the system is neither operating nor deteriorating and there is a loss of m per unit time. Let S, denote the set of all the operating states, i.e., Sn = {0,1, * *, n}. When the system operates in state i E Sn, the operating cost is ai per unit time. 4

Here we assume the deterioration system is monitored continuously which means that the current state of the system is always known. A state-age-dependent replacement policy is described as follows. If Ei represents the time instant when the system enters state i, then at Ei we make a decision to replace the system ti units of time later if it remains in state i. If the system moves to the state i + 1 before ti units of time, a new decision is made at Ei+l. If the system fails (enters state n + 1) before ti units of time, it is replaced immediately after it fails. A state-agedependent replacement policy, 6, is a sequence of decisions selected at Es, i E S. In other words, 6 = (6(0),(1),...,6(n),6(n+ 1)) = (totl,..., tnt,n+l) which specifies the maximum time allowed for the system staying in each state. In particular, if ti = 0 for some i E S, then the system is replaced as soon as it enters state i. On the other hand, if ti = oo, the system will not be replaced as long as it remains in state i. Obviously, a state-dependent replacement policy is a special case of a state-age-dependent replacement policy when t1 is either 0 or oo for all i E S. Furthermore, since a failed system must be replaced, it is sufficient to consider the class of all replacement policies A with 6(n + 1) = tn+l = 0. Our objective is to find an optimal state-age-dependent replacement policy 6* that minimizes the expected long run cost rate. For an infinite time span, it is equivalent to minimizing the expected cost rate of a maintenance cycle which is defined as the time interval from the completion of one replacement to the next. Let Cs(i) and Ts(i) be respectively the expected cost and time from Ei to the completion of next replacement under the policy 6 E A. They can be calculated recursively using the following equations with T6(n + 1) = rn+l and C6(n + 1) = cn+l + mrn+i. T6s(i) = Fi(u) du + Fi(ti)ri + Fi(ti) [pTs(i + 1) + (1 - pi)T6(n + 1)], (1) Cs(i) = a, Fi(u) du + Fi(ti)(ci + mri) + Fi(ti) [piCs(i + 1) + (1 - pi)Cs(n + 1)]. Since Ii is finite, it is obvious that both T6(i) and Cs(i) are finite for all ti E [0,oo) and i E S. The objective here is to find 6* = (6'(0), -, b*(n + 1)) = (to, t*, 0) E A such that g*=inf C6(0).(O) (2) g' ^i oy-rfor (2) Let W(g) = inf [C(0) - gT6(0)]. W(g) is clearly a continuous and nonincreasing function in g E (OEA oo). From Ohishi et al. [11], solving Equation (2) is equivalent to finding a E [, oo) and 5

a policy 6' E A such that W(g*) = inf [Cs(O) - gT6(O0)] = C5.(O) - g*'T.(O) = 0. SEA Note that when m = 1, a, = 0 for i E S,, and ci = 0 for i E S, Ts(0) is the expected cycle time and Cs(0) becomes the expected replacement (idle) time of a maintenance cycle. In this case, the expected long run cost rate becomes the expected long run fraction of time that the system is idle which is known as the unavailability of the system. Minimizing unavailability of the system is therefore a special case of the problem considered here. 3. OPTIMAL POLICIES In this section, we provide an algorithm to find the optimal state-age-dependent replacement policy. Clearly, there are two trivial policies: Sr = (0,0,-, 0) (replacement all the time) and 6f = (0,oo,...,oo,0) (replacement only at failures). Let g, and gf represent the corresponding expected long run cost rates of these two policies. Then, we have gr =m+ - r0 and gf =n i-1 E nI I pj l i + r,+ l i= \j=O / -1 with II P = 1. The optimal expected long run cost rate g* is therefore bounded above by the j=o minimum of g, and gf. For any i E S and g E [0, oo), define Ki(g) = ci + (m - g)ri and Vs(i,g) = Ca(i) - gTs(i) for any 6 E A. Here, Ki(g) represents the expected relative replacement cost (to g) in state i and Vs(i,g) represents the expected relative cost from state i to the completion of next replacement under the policy 6. Using Vs(n + 1,g) = Kn+l(g) and Equation (1), we have V6(i,g) = (ai - g) Fi(u)du + Fi(ti)Ki(g) + F(ti) [pV6(i + 1,) + (1 - pi)K+(g)] 6

for all i E S,. Given a policy 6 E A, a fixed g E [0, o) and an i E S,, define a function t I v(ig, t) such that v6(i,g,t) =(a g) j F(u) du + (t)K(g) +(t)[p (i+, g) + (1 - pi)Kn(g)] for all t E [0,o). Note that v6(i,g,t) is a continuous function of t E (0, oc) with limv,(ig,t) = Ki(g) t —+O and lim v,(i,g,t) = (ai - g)ij + [piVs(i + 1,g) + (1 - pi)Kn+l(g)]. t-0oo Since Vs(n + 1,g) = Kh,+i(g) for all 6 E A, by backward induction lim v6(i,g,t) is finite for all t- oo i E Sn. Hence, inf v,(i,g,t) exists and its value is finite. Since the system can only deteriorate, a tE([,oo) stationary policy 6g satisfying W(g) = inf Vs(0,g) = Vs(0,g) can be constructed by the following SEA Backward Procedure (BP). Step 1: Set 6g(n + 1) = t,n+ = 0 and V6g(n + l,g) = Kn+1(g). Step 2: For i = n,n - l,...,1, 0, Find the smallest nonnegative real number ti such that v6 (i, gt) = inf V6g(i,g,t). Set 6g(i) = t, and V,(i,g) = vg(i,g, t). v9 tE[0,oo) Observe that W(O) = inf C6(0) and W(g) < 0 whenever g E {g,rgf}. Since W(g) is continuous 6EA and nonincreasing in g E (0, oo), there always exists a g E [0,min(gr, gf)] and a corresponding 6g such that W(g) = 0. Furthermore, 6* = 6g and g* = g and they can be obtained using the following Policy Improvement Algorithm (PIA). Step I: [Initial Criteria] Select a tolerance limit e > 0 and an initial policy 6~, e.g., 6r. Set k = 0 and gk = g, if k = 6r. Step II: [Policy Improvement Routine] Use gk to construct a policy 6k+l following BP above. Step III: [Stopping Criterion] If W(gk) 1=1 Vsk+l(O,gk) I< c, then STOP. Set 6* = 6k+l and g* = gk Step IV: [Value Determination Routine] Set gk+l = C6k+l (0)/Trk+i (0), k = k + 1 and GOTO step II. 7

We now discuss the conditions under which the above algorithm converges to the optimal policy in a finite number of iterations. For simplicity of notation, define v(ig,t) = v6 (i,g,t) where 6g is the policy constructed using BP for the fixed g E [0,oc). By differentiating v(i,g, t) with respect to t, we have d dtv(i,g,t) = (ai - g)F(t) + fi(t)ri(g) = F,(t)[(a, - g) + hi(t)r(g)] (3) where rF(g) = piVsg(i + l,g) + (1 - pi)Kn+l(g) - Ki(g). It is obvious that the characteristics of the failure rate function hi plays an important role in deriving the optimal time for replacement in state i. If hi is monotonic increasing or decreasing, then dv(i,g,t) changes sign at most once in t E [0, ). Hence v(i,g, t) has at most one minimum value in t and t may be 0 or oo. This means that provided the failure rate functions are all monotonic, we would always be able to compute numerically the policy 69 for any fixed g E [0, o) to the desired accuracy in a finite number of iterations. From Steps II and IV, we have W(gk) = C6k+l(0) - gkTsk+1(0) < Csk(0) - gkT6s(0) = 0 = Ck+1 (0) - gkTk+l (0). Hence, gk > gk+l > 0. Furthermore, gk = gk+l if and only if W(gk) = 0. These mean that PIA above strictly reduces the cost rate monotonically until the stopping criterion is satisfied. Since the sequence go, gl, g2, *' is monotonic decreasing and bounded below by 0, it converges to a certain limiting value g'. We know that the function W(g) is continuous and nonincreasing in g, it follows that W(go), W(gl),... is a monotonic increasing sequence and it converges to W(g'). It remains to show that W(g') = 0. This is clear since I W(gk) 1=1 Cs+(O) - gkT6+l() - [C+ (0) - gk+lT+ (0)] 1< (gk _ gk+l) sup Ts(0) - 0 SEA as k -- oo. Hence, g' = g* and PIA converges to the optimal policy. Given any tolerance limit e > 0, there always a finite k such that I W(gk) i< c. Therefore, the algorithm converges in a finite number of iterations. 4. PROPERTIES OF OPTIMAL POLICIES In this section, we discuss properties of the optimal state-age-dependent policy 6* = (t,., t*, 0) which is obtained using PIA given in Section 3. Theorems 1 to 2 investigate conditions under which 8

6* is only state-dependent. Theorem 3 presents reasonable assumptions such that the optimal time for replacement becomes shorter and shorter as the system deteriorates. These properties facilitate the search of the optimal state-age-dependent policy. THEOREM 1: If c, = c and r; = r for all i E S and ai is nondecreasing in i E S,, then there exists a unique critical state k* E S such that 6*(i) = oo if 0 < i < k* and 6*(i) = 0 if k' < i < n + 1. In particular, k* = j if and only if a-j_ < g* < aj where j E S with a- = -oc and a,+l = oc. PROOF: Let K = c + (m - g*)r. From Equation (3), we have dt v(ig*, t) = Fi(t) {(a, - g*) + hi(t)pi [V6.(i + 1,9 ) - K]}. (4) We can now consider the following two cases. Case I: g* > aj for some j E Sn d Since Vs.(i,g*)- K < 0 for all i E S and ai- g* < 0 for any i < j, we have dv(i,g', t) < O for all t E [0, oo) and i < j. This implies that 6*(i) = oo for all i < j. Case II: g* < aj for some j E Sn In this case, we have dv(n,g',t) = (an - g*)Fn(t) > 0 for all t E [0,oo) which implies that Vs.(n,g*) = v(n,g*,O) = K and 6*(n) = 0. Repeat this argument recursively for n - l,n - 2, *, j + 1,j, we have 6*(i) = 0 for all i > j. Since g* E [0,min{g,,gf}] and ai is nondecreasing in i E Sn, it is clear from Case I and Case II that there exists a unique critical state k* E S such that 6*(i) = oo for all 0 < i < k* and 6*(i) = 0 for all k* < i < n + 1. Furthermore, if ai-1 < g* < aj, then Case I and Case II together imply that k* = j. Conversely, if k* = j, then we know that 6*(i) = oo for all 0 < i < j and 6*(i) = 0 for all j < i n+ 1. This means that Vs.(i,g*) = K for allj < i < n+, dv(i,g*,t) < O for allt E [0,oo) d and 0 < i < j, and Tv(i,g*,t) > 0 for all t E [0,oo) and j < i < n. Recall that 0 < Fi(t) < 1 for all i E Sn. It follows from Equation (4) that aj-1 < g* and aj > g*. This completes the proof of the theorem. J Theorem 1 above tells us that in the special case when the replacement costs and the expected replacement times are all identical and independent of state, the optimal time for replacement at 9

any state i E S is either 0 or oo. This means that in this special case, the optimal state-agedependent policy is in fact only state-dependent. Furthermore, the optimal state-dependent is of control limit type with critical state k*. For any k E S, let 6k be the state-dependent replacement policy such that 6k(i) = Do for i < k and 6k(i) = 0 for i > k and g(k) be the corresponding expected long run cost rate. Then, g(k) can be easily calculated using the following equation. k-1 i-i1 E i(i Pj aitui + c + mr g(k) - E ( Pj p +r i= \j =0 -1 with TJ pi = 1. Theorem 1 tells us that the critical state k* is the state k E S such that ak-1 < j=o g(k) < ak and g* = g(k*). Note that only the first moment pi of the sojourn time distributions in different states are involved in deriving the optimal state-age-dependent replacement policy in this special case. THEOREM 2: (A) If hi(t) = Ai for all t E [0, oo) and i E Sn, then 6*(i) e {0, oo} for all i E S. (B) If (i) hi(t) is a nonincreasing function in t E [0, oo) for all i E Sn, (ii) 0 < ao < al <... < an, (iii) 0 < ro < rl <... < rn < rn+i, and (iv) 0 = co < cl <... cn < cn+l, then 6*(i) E {0, oo} for all i E S. In Theorem 2 above, hi(t) = Ai for all t E [0, oo) is the same as saying that the sojourn time distribution in state i, Fi, is exponentially distributed with parameter Ai. Assumption (i) tells us that F, is a decreasing failure rate distribution (DFR). In assumptions (ii) to (iv), we assume that the operating cost rate increases as the system deteriorates, the expected replacement times are all strictly positive and it is more expensive and time consuming to replace the system with deterioration. co is assumed to be equal to 0 since state 0 is the initial new state of the system before any deterioration takes place. These assumptions are reasonable for deteriorating systems. For simplicity of notation in the proof of Theorem 2 below, we let Ki = Ki(g*) for i E S. Also, let ri = rI(g*) and bi = piKi2i + (1 - pi)Kn+1 - K, for all i E Sn. Since we assume co = 0, it 10

follows that m = g, > g*. Under assumptions (iii) and (iv), it is clear that Ki is nondecreasing in i E S and bi is nonnegative for all i E S,. PROOF OF THEOREM 2: (A) From Equation (3), we have d v(i,g*,t) = (ai - g* + A r) exp(-A t). dt Note that ai - g* + AXi is independent of t. Hence, v(i, g*, t) is either nonincreasing or nondecreasing for t E [0, o). This implies that 6*(i) E {0,oo} for all i E S. (B) We consider the following three cases. Case I: If a, > g*, then assumption (ii) implies that aj > g* for all j > i. By definition, rn = bn = Kn+1 - Kn which is always nonnegative. From Equation (3), we have dTv(n,g*,t) > 0 for all t E [0,oo), i.e., t* = 0 and Vs.(n,g*) = Kn. Hence, rn-i = bn- which is nonnegative. Repeat the above argument for j = n - 1,., i, we can show that dv(j, g*,t) > 0 for all t E [0, oo) and this means that ti = 0 for all j > i. Case II: If ai < g* and ri > 0, then from Equation (3), Tv(i,g*,t) changes its sign at most once in t E [0, oo) from positive to negative since hi(t) is a nonincreasing function in t. This result implies that the infimum of v(i, g*,t) is either v(i,g*,0) or v(i,g*, oo). In other words, t, is one of the end points, 0 or oo. Case III: If a, < g* and ri < 0, then dv(i,g*,t) < O0 for all t E [0,oo), which implies that the infimum of v(i,g*,t) is v(i,g*, oo) and t = oo. These three cases indicate the optimal decision 6*(i) is either 0 or oo. D Given any 6 E A, if k = min{i: 6(i) = 0}, then the system is replaced as soon as it enters the iES critical state k or at failure. This together with Theorem 2 tell us under the given conditions, the optimal state-age-dependent policy, 6*, constructed using PIA in Section 3 is only state-dependent. Hence, to find the optimal state-age-dependent replacement policy, it is sufficient to consider the set of all state-dependent replacement policies {6k: k E S}. The expected long run cost rate g(k) 11

can be calculated by the following equation. k-1 i-1 k-1 k-1 Ein (I)pji ai, i + 1( P (ck + mrk) + 1- pj (Cn+l + mrn+l) i=o \j=o \/=0 j=o i= \j= o \= / j=o The optimal expected long run cost rate g' can be obtained by searching a k* E S such that g* = g(k*) = ming(k). kES THEOREM 3: In addition to assumptions (ii) to (iv) of Theorem 2, if (I) hi(t) is a nondecreasing function in both i E Sn and t E [0,oo), (II) 1 > po ~ pi >... > p>n- > Pn = 0, and (III) PiCi+l + (1 - Pi)cn+i - c, and piri+l + (1 - pi)rn+l - ri are both nondecreasing in i E Sn, then there exist h* and k* with 0 < h* < k* < n + 1, such that oo if i < h*, 5*(i) = ( t? if h < i < k*, 0 ifk* < i < n +. Furthermore, oo > t? > t> > 0 for h* < i < j < k*. Assumption (I) tells us that F, is an increasing failure rate distribution (IFR) for all i E Sn and the failure rates also increase with deterioration. In assumption (II), we assume that the probability of transition into failure state from intermediate states are nondecreasing as the system deteriorates. Assumption (III) means that the expected marginal replacement costs and times increase as the system deteriorates. Theorem 3 tells us that under reasonable assumptions, the optimal state-age-dependent replacement policy has the monotonic property in which the optimal time for replacement becomes shorter and shorter as the system deteriorates. PROOF OF THEOREM 3: Under assumption (III), it is clear that bi is nondecreasing in i E Sn. Define 1 d W,(t) = F-(t)dv(i,g,t) = a - g* + h(t)ri. (6) We will use backward mathematical induction to show that (a) Wi(t) in nondecreasing in i E S, for all t E [0, oo), and (b) t? is nonincreasing in i E Sn. 12

For state n, it is clear that Fn = b, = K,n+ - K, > 0. Using Equation (6) above, we have the following two cases. Case I: If an > g*, then dv(n,g',t) > 0 for all t E [0,oo) and t* = 0 from the Proof of Theorem 2 (B) Case I. d Case II: If a, < g', then tv(n,g*,t) changes its sign at most once in t E [0,oo) from negative to dt positive since h,(t) is a nondecreasing function in t. Hence, -v(n,g*,t) < 0 for all t E [0, t). Cases I and II above imply that v(n, g, t) < for all t E (0, t) and therefore dv(n, g*, u) du <0. Next observe that Vs6(i, g*)= v(i, g*,) = R dv(ig*u)du+Ki and hence, Jo du ri = Pi | d v~i + 1, g*, u) du + bi. (7) From the assumptions given in the theorem, we know that an > an-_, and bn > bn-1 > 0. If hi(t) is nondecreasing in i, then hn(t) > hn_-(t) for t E [0,oo). Hence, from Equations (6) and (7), Wn(t) > Wn-l(t) for t E [0,oo). This result in turn implies t*_1 > t*. For some state k E Sn \ {0, 1}, assume the following two conditions hold for all i > k. (Cl) d v(i,g*,t) < 0 for all t E (0,t?), and (C2) Wi(t) > Wi-l(t) for all t E [0,oo). We have shown that conditions (C1) and (C2) both hold for k = n. Note that condition (C2) indicates that t*_ > t? for all i > k and d ___ _t) d d v(i, g*- lg*,t) > F(8) d-t' i-l(t) dtv(i-,13 13

for all t E [0, o). In the following discussion, we show that conditions (Cl) and (C2) also hold for i = k - 1. Using Equation (6), consider the following three cases. Case I: If ak_- > g*, then -v(k - 1,g', t) > 0 for all t E [0, oo) and tk_- =.t = = - 0 from the proof of Theorem 2 (B) Case I. Case II: If ak._ < g* and rk_- > 0, then dv(k-, g*, t) changes its sign at most once in t E [0, o) d from negative to positive since hk_1(t) is a nondecreasing function in t. Hence, dv(k - 1,g<, t) < 0 for all t E [0, t_). Case III: If ak-1 < 9g and rk-1 < 0, then dv(k - 1,g*,t) < 0 for all t E [0, o) and t*_ = oo. These three cases indicate that d -v(k- 1, g,t) < 0 for all t E (0, t_). Since Fi(t) = exp - j hs(u)du] and hi(t) is nondecreasing in i, it is clear that F(t) Fi(t) is nonincreasing in i and Fi(t) < Ifor all i E S, and t E [0,oo). Using (C1) and Equation (8), we have 0> dv(k,g*,t) > k() - 1,g*,t) > dv(k - 1,g* t) - dt Fk-_l(t) dt dt for all t E (O, t) C (O,t._l). Therefore, 0> d v(k,g*,u)du> k (k - lg u)du > d v(k -,g,u)du. d du - Oo du It follows from assumption (II) that t* d /ft l d O > Pk- I v(k,g,u)du > pk-2 v(k - 1, g, u)d Jo d Jo du and therefore Wk-l(t) > Wk-2(t) for all t E [0,oo). Again, this result implies t _2 > t_1. We have shown that if conditions (Cl) and (C2) hold for all i > k E Sn \ {0, 1}, then they also hold for all i > k - 1 E Sn \ {0, n}. By the principle of mathematical induction, the proof of the theorem is completed. D 14

5. Special Case In this section, we investigate the special case when the sojourn time distribution in state i, Fi, follows a Weibull distribution for all i E S,. Weibull distribution is chosen here since it includes Exponential distribution as a special case and both Weibull and Exponential distributions are widely used in probabilistic reliability modeling. Let Fi be a Weibull distribution with a scale parameter cai > 0 and a shape parameter ); > 0, i.e., 1 - exp(-atit'i) t > 0 Fi(t) = - 0 otherwise The failure rate function is given by hi(t) = ai^ta'-' for all t E [0,oo). It is clear that Fi is an IFR distribution if and only if pi 2 1. When 3i = 1, it reduces to an exponential distribution with a constant failure rate ai. Fi is a DFR if and only if Oi < 1. From Theorem 2, we know that when /i < 1 for all i 6 S,, we only need to consider state-dependent policies. When Oi > 1 for all i E S, PIA can be used to find g* and 6*. In particular, d dtv(i,g,t) = (a, - g + it-r) exp(-ait) = 0 (g - ai \/('-) can be solved explicitly with solution equal to 0, oo or ( a Pri For example, consider a 5-state system (n = 3) with Weibull sojourn time distributions. Let ao = 1, al = 1.5, a2 = 2, a3 = 2.5, uo = 100, ti1 = 90, 2 = 80, 03 = 70, Co = 0, cl = 20, c2 = 60, c3 = 120, c4 = 200, ro = 10, ri = 11, r2 = 13, r3 = 16, r4 = 20, po = Pi = P2 = 0.9, and m = 15. Note that the above cost and time parameters satisfy the assumptions given in Theorems 2 and 3. Depending on the shape and scale parameters of the Weibull sojourn time distributions, we have the following rmults. 1. [Exponential Case] ai = l/iu and pi = 1 for all i 6 Sn: It is readily verified that g(0) = 15, g(1) = 2.83, g(2) = 2.68, g(3) = 2.85, and g(4) = 3.09. Hence, k* = 2, g* = 2.68. 2. [DFR Case] ai = I2g7i and /i = 0.5 for all i E Sn: From Equation (5), g(k) depends only on the first moment pi of the sojourn time distributions in different states, the optimal policy and cost rate are therefore the same as in the exponential case. 15

3. [IFR Case] a, = 7r/(2pI)2 and O3 = 2 for all i E S. By applying PIA, we have 6*(0) = 312.03, b*(1) = 66.54, 6*(2) = 20.79, b*(3) = 1.50, 6*(4) = 0, and g* = 2.56. Note that the optimal policy is of control limit type and the optimal times for replacement decrease as the system deteriorates. References [1] Anderson, M. Q., "Monotone Optimal Preventive Maintenance Policies for Stochastically Failing Equipment," Naval Research Logistics Quarterly, 28, 347-358, (1981). [2] Feldman, R. M., "Optimal Replacement with Semi-Markov Shock Models," Journal of Applied Probability, 13, 108-117 (1976). [3] Feldman, R. M., and Joo, N. Y., "A State-age Dependent Policy for A Shock Process," Cornmum. Statist. - Stochastic Models, 1, 53-76 (1985). [4] Gottlieb, G., "Optimal Replacement for Shock Models with General Failure Rate," Operations Research, 30, 82-92, (1982). [5] Kao, E. P. C., "Optimal Replacement Rules when Changes of States are Semi-Markovian," Operations Research, 21, 1231-1249 (1973). [6] Kolesar, P., "Minimum Cost Replacement under Markovian Deterioration," Operations Research, 12, 694-706 (1966). [7] Luss, H., "Maintenance Policies when Deterioration can be Observed by Inspections," Operations Research, 24, 359-366 (1976). [8] McCall, J. J., "Maintenance Policies for Stochastically Failing Equipment: A Survey," Management Science, 11, 493-524 (1965). [9] Mine, H., and Kawai, H., "An Optimal Inspection and Replacement Policy," IEEE Transactions on Reliability, 24, 305-309 (1975). [10] Mine, H., and Kawai, H., "An Optimal Inspection and Replacement Policy of a Deteriorating System," Journal of Operations Research Society of Japan, 25, 1-15 (1982). 16

[11] Ohnishi, M., Kawai, H., and Mine, H., "An Optimal Inspection and Replacement Policy for a Deteriorating System," Journal of Applied Probability, 23, 973-988 (1986). [12] Pierskalla, W. P., and Voelker, J. A., "A Survey of Maintenance Models: The Control and Surveillance of Deteriorating Systems," Naval Research Logistics Quarterly, 23, 353-388 (1976). [13] So, K. C., "Optimality of Control Limit Policies in Replacement Models," Naval Research Logistics, 39, 685-697 (1992). [14] Valdez-Flores, C., and Feldman, R. M., "A Survey of Preventive Maintenance Models for Stochastically Deteriorating Single-Unit Systems," Naval Research Logistics, 36, 419-446 (1989). [15] Wood, A. P., "Optimal Maintenance Policies for Constantly Monitored Systems," Naval Research Logistics, 35, 461-471 (1988). 17

C New Failed Fo (l) FC(t) 2nt) ^\ PO ^\ Pi /^\O~~e t~ Po P- C1 5 en z /- P o Y ^ )/ I New 1: A flow diagram of a deteriorating syFailed Figure 1 A flow diagram of a deteriorating system