OPTIMAL MAINTENANCE POLICIES FOR DETERIORATING SYSTEMS UNDER VARIOUS MAINTENANCE STRATEGIES C. Teresa Lam and R. H. Yeh Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report No. 92-31 June 1992 Submitted to IEEE Transactions on Reliability Revised July 1993

Optimal Maintenance-Policies for Deteriorating Systems under Various Maintenance Strategies C. Teresa Lam* The University of Michigan, Ann Arbor R. H. Yeh* National Taiwan Institute of Technology, Taiwan Key Words - Continuous-time Markovian deterioration, Expected long run cost rate, Inspection and Replacement strategies, Iterative algorithms Reader Aids - Purpose: Present algorithms for deriving optimal maintenance policies Special math need for derivations: Markov probability theory, nonlinear optimization, dynamic programming Special math need to use results: Nonlinear optimization Results useful to: Reliability analysts and theoreticians *Research Supported in part by a grant from the Research Partnership Program, Horace H. Rackham School of Graduate Studies, University of Michigan. 1

Abstract - This paper presents algorithms for deriving optimal maintenance policies to minimize the expected long run cost rate for continuous-time Markovian deteriorating systems. The degrees of deterioration (except failures) of the system are known only through inspection. The time durations of inspection and replacement are non-negligible. The costs incurred are inspection cost, replacement cost, operating cost, and downtime (idle) cost. In particular, the replacement time, replacement cost and operating cost rate increase as the system deteriorates. Five maintenance strategies are considered - failure replacement, age replacement, sequential inspection, periodic inspection, and continuous monitoring strategies. Iterative algorithms are developed to derive the optimal maintenance policy and the corresponding cost rate for each strategy. Under sufficient conditions, structural optimal policies are obtained. 2

1. INTRODUCTION Most manufacturing systems continuously deteriorate due to usage or age and are subject to random shocks which result in unexpected failures. For example, a machine may continuously deteriorate due to cumulative wear, fatigue, corrosion, or erosion, and it may also suddenly fail due to accidental changes in temperature or electrical voltage. Due to the inevitable deterioration and random shocks, manufacturing systems may not retain in a condition in which goods of an acceptable quality can be produced. To restore a highly deteriorated or failed system is usually time-consuming and costly. Frequent inspection and repair/replacement might reduce the chances of high deterioration and failure, however, it also incurs unnecessary maintenance costs. Therefore, there are incentives to derive a maintenance policy to avoid failures or operating the system in an unacceptable condition while reducing the total cost. Maintenance policies of stochastically failing systems have been widely investigated in the literature. Valdez-Flores and Feldman [17] provided a survey of recent works and [8, 12, 14] are excellent reviews of earlier papers in this area. By assuming that the condition of a system is always known without inspection or inspection time is negligible, many previous works studied only replacement policies [1, 2, 15, 16, 18]. In practice, this assumption may be invalid. In this paper, we investigate maintenance policies for systems whose degrees of deterioration can be identified only through inspection. The deteriorating process is modeled by a multi-state continuous-time Markov process. Our objective here is to determine an optimal inspection and replacement policy such that the expected long run cost rate is minimized. To determine an optimal inspection and replacement policy, a particular strategy is usually pre-specified by maintenance planners under some practical considerations such as the 3

limitation of technology, the cost of equipment, and the simplicity of implementation. Five maintenance strategies are investigated in this paper - failure replacement, age replacement, sequential inspection, periodic inspection, and continuous monitoring strategies. Special cases of our model and strategies are given in [7, 9, 11, 13]. For these five strategies, we provide iterative algorithms to derive the optimal policies and their corresponding cost rates. The structures of the optimal maintenance policies are also investigated. 2. CHARACTERISTICS OF THE SYSTEM 1. At any point of time, the deteriorating process of the system can be classified into one of a finite number of states 0, 1,., n, n + 1. State 0 represents the initial new state of the system. State n + 1 represents the terminal (failure) state of the deteriorating process. The intermediate states 1, 2,.., n are ordered to reflect the degree of deterioration (in ascending order). 2. The transition from one state to another follows a continuous-time Markov process with an absorbing state n + 1. From state i, a direct transition can occur only to state i + 1 due to deterioration or to state n + 1 due to a random shock. 3. Each inspection can reveal the state of the system perfectly. 4. Failures can be detected immediately without inspection. A failed system must be replaced. 5. The repair/replacement cost and time are state-dependent. After the completion of each repair/replacement, the deteriorating process is renewed (back to state 0). 6. During an inspection or a repair/replacement, the system is neither operating nor deteriorating. 4

3. DESCRIPTION OF STRATEGIES The five inspection and replacement strategies considered here are as follows: 1. Under a failure replacement strategy, no inspection is performed and the system is replaced only when it fails. 2. Under an age replacement strategy, the deteriorating system is replaced at age t or at failures, whichever occurs first. Since the replacement cost and time are statedependent, if the system does not fail before age t, an inspection is performed so that we can repair/replace the system at lower cost in less time. 3. Under a sequential inspection strategy, the system is inspected sequentially to identify the current state of the system. Once the system is identified to be in state i, one of the following decisions is selected: replace the system immediately, or inspect the system ti units of time later. If the system fails before the next inspection, it is replaced immediately at the time it fails. 4. In the special case when we constrain all the ti in the sequential inspection strategy to be identical and independent of states, a sequential inspection strategy reduces to a periodic inspection strategy. 5. Under a continuous monitoring strategy, the deteriorating system is operating and being monitored continuously at the same time. The state of the system is known with certainty at all time. Once the system enters state i, the decision is either to replace the system immediately or to continue monitoring. 5

4. NOTATION S The set of all states of the system, S = {0, 1,.., n + 1}. JR+ The set of all nonnegative real numbers, R+ = [0, oo). ai The operating cost per unit time in state i E S \ {n + 1}. Ci The fixed repair/replacement cost in state i E S. ri The mean repair/replacement time in state i E S. M The fixed inspection cost. q The mean inspection time. m The loss per unit time when the system is not operating. ai The transition rate from state i to state n + 1 for i E S \ {n + 1}. /pi The transition rate from state i to state i + 1 for i E S \ {n, n + 1} (3n = 0). Ai The total transition rate out of state i E S \ {n + 1}, i.e., Ai = ai + i. Pij(t) The probability of the system presently in state i will be in state j after t units of time. Fi(t) The failure time distribution of the system starting from state i. Note that Fj(t) = n Pin+1(t) and Fi(t) = - Fi(t) = E Pi(t). j=i Qij(t) The expected time that the system spent in state j during [0, t] given it starts from state i, i.e., Qij(t) = P(u)du. Ai(t) The expected operating cost of the system during [0, t] given it starts from state i, n i.e., Ai(t)= EajQi,(t). j=i ^i The expected time to failure given the system starts from state i, i.e., i = ~ F,(u) du. Ei The time instant when the system is identified to be in state i E S. 6

R The decision to repair/replace the system immediately. I(t) The decision to inspect the system t E R+ units of time later. I(oo) The decision to operate the system without inspection until it fails. & A sequence of decisions selected at time instant Ei, i E S. D6(i) The decision at the time instant Ei under policy 6. In particular, we restrict ourselves to D6(n + 1) = R for all strategies. 0 The set of five strategies, f, a, s, p, and c which represent failure replacement, age replacement, sequential inspection, periodic inspection, and continuous monitoring strategies, respectively. AO The set of all policies, 6, under strategy 0 E 0 with Ds(n + 1) = R. X, (i) The expected time from Ei to the completion of next replacement under policy 8 of strategy 0 G 0. Y6(i) The expected cost from Ei to the completion of next replacement under policy 8 of strategy 9 E 0. 89* The optimal maintenance policy under strategy 0 E 0. g9" The optimal expected long run cost rate under strategy 9 E 0. 5. OPTIMAL POLICIES The objective here is to derive optimal maintenance policies to minimize the expected long run cost rate. Consider the renewal process formed by successive replacements and using the standard results in renewal theory, the expected long run cost rate is equal to Y6(0)/X|(O) for policy 8 under strategy 8 E 0. We want to find 68 E As such that 9 - inf X6() sY(O) (1) x6g ^ (0) XI;(0) ' 7

For each g E 1R+, define We(g) = inf [Y6(0) - gX(O0)]. From [11], solving Equation (1) is 6EAe equivalent to finding a g* E 1+ and a policy X E A6 such that Weo(g) = Y(0) - gX *(0) = O. It can be verified easily that Wo(g) is a continuous and nonincreasing function in g C R+ for all 9 E 0 [5]. Note that minimizing the unavailability is a special case of the problem considered here when m = 1 and Ci = a = M = 0 for all i E S. Before presenting algorithms to obtain optimal policies, let us first introduce the following sufficient conditions on the cost and time structures. Under these sufficient conditions, it will be shown that the optimal policies of various strategies have structural properties. (Al) 0 < Ao < Al <... < An (A2) 0 < ao < al <... < an (A3) 0 < ro rl <... < rn< rn+l -q Co + M C1 + M C,+ + M C,+1 (A4) 0< <...< < ro + q Tr + q rn+1 + q rn+l 'A5 I a a1 + (A5) -(Co mro) (C + mr) ro) < +. < -(Cn + mr) Ao A1- An Conditions (Al) to (A5) above are reasonable since they assume that it is more time consuming and expensive to replace system with deterioration, and the transition rates to higher states increase as the system deteriorates. Some of these conditions, especially condition (A5), may seem to be very restrictive. As we will see later, these conditions are not required in applying the algorithms to derive the optimal policies. However, if these conditions are satisfied, the optimal policies have certain structural properties which can help to facilitate the search of the optimal policies. The proofs of all the theorems presented in this section are given in the appendix. 8

* Failure Replacement Strategy: Under this strategy, Af = {6: = [I(oo), I(oo),., I(oo), R]}. The expected long run cost rate can be obtained easily as follows. * Yf(0) _Ao(oo) + Cn+C + mr+i f (OXf) Lo + rn+1 Since both Ao(oo) and plo are positive and finite, g* is also finite and it lies somewhere between the expected average operating cost rate Ao(oo)/[o and the expected average failure replacement cost rate m + Cn+i/rn+l. If Ao(oo)/ to > m + Cn+l/rn+l, it is easy to show that gf > m. This means that the cost rate of operating the system is greater than the loss per unit time in shutting down the system. To avoid triviality, we exclude this case and only consider gf < m in our study. * Age Replacement Strategy: Under this strategy, Aa = {6 =t: t E [0, oo]}. Given any age t E [0, oo] for replacement, X(O) = Xt(O) and Y6a(0) = Yta(0) can be calculated by the following equations. rt n+l Xta(0) = o Fo(u) du + qFo(t) + t) + Po), (2) j=O and n+l Yta(O) = Ao(t) + (M + mq)Fo(t) + E Poj(t)(C + mrj). (3) j=o Define ga(t) = Yta(O)/X((0), then g - inf ga(t). Since ga(t) is a continuous function tE[0,oo] of t with ga(oo) = g* and ga(O) = m + (M + Co)/(q + ro), g* exists and we have 0 < g* < min[g*,ga(0)]. Furthermore, let A(t,g) = Ya(0) - gXa(0). Then, finding the optimal expected long run cost rate g* and the optimal inspection time t* is equivalent to finding g* and t; such that Wa(g*) = inf A(t, g) = A(t*,g2) = 0. tE[0,oo] To obtain the optimal age t* and the optimal expected long run cost rate g* is straightforward. For each fixed g E [0,min[g,ga(0)]], ( A(t,g) is a continuous function of t with 9

A(O, g) = M + Co + (m - g)(q + ro) and A(oo, g) = Ao(oo) + Cn+i + (m - g)rn+1 - gL0o. It is clear that inf A(t,g) exists and its value is finite. Since Wa(0) = inf Y(O) > 0 and tE[0,oo] tE[O,oo] W,(g) < 0 when g E {fg,gga(0)}, g exists and can be obtained by the following iterative algorithm. Step 0: Select an initial value g, e.g., set g = min[g,ga(0)]. Step 1: Find t*(g) such that Wa(g)= inf A(t,g) A(t*(g),g). tE[0,oo] Step 2: If Wa(g) = 0, then g9 = g and t = t*(g). STOP. Otherwise set g = Y()(O)/X(g)(O), GOTO Step 1. The above algorithm is an example of a policy improvement algorithm as discussed in [6]. It has been proved in [6] that the sequence of g obtained from a policy improvement algorithm is monotonically decreasing and the algorithm converges in a finite number of iterations. The following theorem facilitates the search of the infimum of A(t, g) for each fixed g E [0,min[g;, 9a(0)]]. Theorem 1. Under condition (Al) to (A5), for each fixed g E [0, min[g*, g(0)]], the function A(t,g) has one and only one minimum value with respect to t E [0, oo]. Furthermore, if A(t*(g),g) = inf A(t,g), then t*(g) is unique. tE[O,oo] * Sequential Inspection Strategy: Under this strategy, A/ = {6: D6(i) = I(ti) or R, i E S, ti E [0, oo], Da(n + 1) = R}. Given any Da(i), X(i) and Y,/(i) can be calculated using Equations (4) and (4) and (5) below. _t n+1 Fi(u) du + qFi(ti) + E Pij(ti)Xf(j) if Ds(i) = I(ti) X (i) = o j=, (4) r{ if Da(i) = R and 10

n+1 A-(t1) +(Ml+ mq)F1(t-) -I EP,,(t.)Y68'(j) if D6(i')= 1(t1) Y,68 (i) = (5) CI + mr'1 if D6(i) = R When the transition rates of the continuous-time Markov process are finite and non-zero, and D6(i") $~ 1(0), it is easily shown that both XS(i) and Y68(i) are finite but unbounded on A,. Obviously, there are three trivial decisions at E0: 1(0), I(oo) or R. The corresponding expected long run cost rates are m + M/q, g*, and m + Co/ro, respectively. Let g, = min[m + M/q, g*, m + Co/ro]. The optimal expected long run cost rate g* is clearly bounded above bygmn Given any g C iR+, iE S, and S E A,, define V,6(ig) = Ys5i gX,(i). From Equations (4) and (5) above, we have V6(ig) { 6(i g,) t) if D6(i I (t) K1(g) if D6(i R where I' ~~~~n+1 gJt1( G6(i,g~1 1A-(t1) +I +j >Z 13(()V(jdu _q, i) IP11(t1) Mdt1g) 3=+1Pj(t) M~ = [M +(m -g_)q] and K1(g)= C + (m -g)r,, i C- S. Now, we want to finds;, and g* such that W,(g*) = inf V,6(o,g*) = V6;(o,g*) = 0. Since W,(O)= inf Y65(O) > 0 and a 6EA,. 6EA, W,(g)<0 whn g C{m + /q, g m ~ C0/r0}, there always exists a gE [0, g,,,in,] such that Wg)= 0. Furthermore, we know that V6(rn + 1, g) = Kn+j (g) for all 6 C AS, it can be verified easily G6 (n, g, tn) M + an -g9+K+1 9 1 - e-Antn An which is a decreasing function in 4n C R+? provided that g ~ m + M/q. The optimal policy 8and the corresponding g* can therefore be obtained by the following iterative algorithm. 11

Step 0: Select an initial value g C [0, g.~i] and construct a policy 8g E A, as follows. Step 1: Set V* (n + 1, g) = K,,+i(g) and Dbg(fl + 1) = R. Set V* (n, g) = mmnQs [g(n,g, oc), Kn (g)]. If V *(n, g) = S, G~(n,g, oo) < Kn (g), t hen D,6g,(f) = I (oo). If V*(n,g) =Kn(g), then Dbg(n) = R. Step 2: Fori7,=n -1n-2,,1,)0, Find t*(g) such that G* (It,g, t(g))= inf G*(Ii,g, t), where tE[0,00] G*(il g, t) =1 1 Ai(t) + ~iA(t) + n+1 tV F2g)g i(u) d Set V*(iZ, g) = mmn [G*(i, g, t~(g)), K1(g)]. If V*(i, g) = G*(i, g, t*(g)) < K2(g), then D,5g(,Z) =I(tV(g)). If V *(i, g) = K1 (g), t hen Dbg() R. Step 3: If V* (0, g) = 0, then g = g and &* = 8g. STOP. Otherwise, set g = Y4(0)!X48(0). GOTO Step 1. In Step 1 above, it is obvious that for all g E [0,g9min], D,6g(nl) E {I(oo), R}. Note that G*(i,Z g, t) defined in Step 2 above is a continuous function of t for all t E (0, co). Furthermore, for each fixed g, we have lim G* (i',g, t) = Ai(oo) + Kn+1 (g) - gpi which is t-.oo0 finite. Also, for i' E S \ {n + 1}, 0o ifO K<g < m +M/q lim.G* (i',g,t) — + a + aiV*(n+1, g) +QiV*(i+1, g) -g> -o if g= m +M/q (-00 if g > m +M/q Therefore, for each g E [0, m + M/ q], inf G* (i,, g, t) exists and is finite, and it may occur tE[0,00] at t = 0 or co. Step 2 above is therefore justified. Theorem 2. If conditions (Al) to (A5) hold, then 8g constructed in Step 2 of the algorithm 12

above has the following structures for each fixed g E [0, g9mn]. 1. There exists a critical state k,(g) E S such that Dbg(i) =R if ka(g) < i n~, D6g(l) = I(t*(g)) if 0 i < k(g). 2. co > te(g) ~ t*(g) > 0 for 0 < i~ j < ks(g). Theorem 3. Under conditions (Al) to (A5), for any g E [0,gmin] and 7 E S \{n + 1}, G It, g, t) has one and only one minimum value in t C [0, oo]. Furthermore, if G*(i g, t(g)) = inf G*(i, g, t), then t* (g) is unique. tE[O,oo] Periodic Inspection Strategy: As mentioned before, periodic inspection strategy is a special case of sequential inspection strategy, i.e., AP = {6: D6(i) = 1(t) or R, i c S, t E [0, oo], D6(n + 1) = R} which is a subset of A,. Therefore, gP is bounded below by g* and also bounded above by g,,. Given an inspection period t, X6P(i) and Y61(i) can be calculated using Equations (4) and (5) with ti = t. Using the same argument given for sequential inspection strategy, the following iterative algorithm can be used to search for t*, 3* and g;. Step 0: Select an initial value g E [0, gmi] Step 1: Select an initial value t, e.g., set t = po and construct a policy 8g as follows. Step 2: Set V*(n + 1, g, t) = Kn+j(g) and D,6(n + 1) = R. Step 3: For i = n, n - 1,.. ),1, 0, Set V*(i, g, t)= min [g*(i, g, t), K2(g)],where ( n+1 Jt g*(lg t) = i-(t) Ai(t) + IF(t) + P1(t)V(jgt)- g P F(u) If V*(i, g, t)= *(ij, g, t) < K,(g), then D6,(i) = 1(t). 13

If V*(i,g,t) = Ki(g), then D6g(i) = R. Step 4: If V*(0, g, t) achieves its infimum at t, then GOTO Step 5. Otherwise, update t by Fibonacci or Secant search methods and GOTO Step 2. Step 5: If V*(0,g,t) = 0, then t = t,;p = 6g, and gp = g. STOP. Otherwise, set g = YVP(O)/XP (0). GOTO Step 1. Theorem 4. If conditions (Al) to (A5) hold, then 6g constructed in Step 3 of the algorithm above has the following structures for each fixed g E [0, g9n] and t E (0, oo). 1. There exists a critical state kp(g) E S such that D6(i) = R if kp(g)< i <n+l, Ds,(i) = I(t) if 0 < i < k(g), 2. If Gag(n, g, oo) < Kn(g), then Ds,(i) = I(oo) for all i E S \ {n + 1}. The following theorem compares the optimal cost rates of the four strategies considered so far. Theorem 5. gf > g9 > g; > g. * Continuous Monitoring Strategy: Under this strategy, since the current state of the system is always known, we only need to restrict ourself to the set of all policies S such that Da(i) = R if k < i < n + 1, and D6(i) = CM (continue monitoring) if 0 < i < k for some critical state k E S. For easier interpretation, let X6(i) = X^(i) and Y6C(i) = Yc(i) if k e S is the critical state for replacement. They can be calculated recursively using the following equations. - -rn+ + i +1) if 0 < i < < n + X^(i) = A i Ai rk if i = k 14

and X + (Cn+l + mrn+l) + Y( +1) ifO<i<kc<n+l YVd( i)i =; A^ Ck + mrk if i = k Let gc(k) = Yk/Xc. We want to find a k* E S such that g*- inf gc(k) = inf kc = XY' kES kES Xk X see [4]. 6. CONCLUSION Obviously, we have gc(0) = m + Co/ro < oo and 7c(n + 1) = g* < oo. Therefore, the value of In this finitpaper, we present algorithms to derive optimal ma1 Sintenane is policies for five diffnumber of states the optimal cost rate gsufficient cond the optimal policy k (A), we show that the optimal policies C 4 such that c(help) is minimal. It has been shown that under appropriate conditions, gh < gc [4]. For a detail theoretical comparison of continuous and sequential inspection strategpreferred if see [4]. 6. CONCLUSION In this paper, we present algorithms to derive geneoptimral modaintenance policies for five differmuch simpler. ent strategies. Under sufficient conditions (Al) to (A5), we show that the optimal policies have structural properties. These structural properties are summarized in Theorems 1 to 4 and they help to simplify the numerical search of the optimal cost rates and the corresponding optimal policies. Theorem 5 indicates that sequential inspection strategy is preferred if it is applicable in practice. It is worth pointing out here that although Theorems 2 to 4 in this paper are extension of [9, 11] for a more general model, the proofs of our theorems are much simpler. Even though conditions (Al) to (A5) may be difficult to obtain in practice, the iterative algorithms developed in this paper are still applicable when these conditions are not satisfied. Using these algorithms, maintenace planners can compute and compare the optimal cost 15

rates of different maintenance strategies. This allows them to select a maintenance strategy according to their practical considerations. Hence, results in this paper are both of practical and theoretical interest. APPENDIX Since the transitions of the deteriorating system follow a continuous-time Markov process, the transition probabilities P13(t), i", j E S and t E JR+ satisfies the following Kolmogorov 's equations. Kolmogorov 's forward equations: -P11(t) = -AsPii(t) = -Aie~i o dt d - P13( = -A3Pi3(t) + Pi3.1Pi,j-1(t) for 0 K i < j n, dt d foOKnm ~- F1(t) = ZaPs3 (t) fo _ i<n Kolmogorov 's backward equations: d -P~t) = -11()+i1113t for 0 Ki K' < dt d Fj(t) = AAW (t- jp+1(t) - -AiF1(t) + 35Fj+i(t) +ai for 0K<i <n. Proof of Theorem 1: Fori C5,let b,(g) = a2-AiK1(g)+/31Ki+i(g)+a1[Kn+i(g)-M] where M = M+(m-g)q and K1(g) = C1 + (m - g)r2.. Under conditions (Al) to (A5), it is easy to show that b3(g) is nondecreasing in y ~ n+1 o ~O 5.UigKlooo's forward equations, for each fixed g E [0, minjg* ga(O)}], we have dn -jA(t7 g) = E Po3(t) [b3(g) - g]. dt ~~j=Q 16

Since bj(g) is nondecreasing in j, bj(g) - g is nondecreasing in j and changes its sign at most once from negative to positive. Furthermore, Poj(t) is a total positive function of order 2 (TP2) function in j S \ {n + 1} and t E [0, oo) [5, 10, 11]. Using the variation diminishing property of TP2 functions [3], dA(t,g) changes its sign at most once in t from negative to dt d d positive. If -A(t, g) changes its sign at t*(g) e (0, oo), then t*(g) is unique since -A(t, g) is dt dt a linear combination of a finite number of exponential distributions and it is not a constant function of t in any open interval unless it is a constant for all t E R+. If ~dA(t, g) does not d change its sign, then ~-A(t, g) is either positive or negative for all t E [0, oo]. In this case, dt t*(g) is either 0 or oo. L Proof of Theorem 2 part 1: For each fixed g E [0, ga(0)] (note that ga(0) > g.min) and i E S \ {n + 1}, define, n+l t i (t) = A,(t) + MF,(t) + Pil(t)KI(g) - g F,(u) du - Ki(g). l=i We know that V*(j, g) = min [inf G(j, g,t) Kg), i.e., V*(j, g) < K(g) for all j E S. Hence, 4,(t) > [1 - Pi,(t)] [G*(i, g, ) - Ki(g)] (A.1) whose equality holds only when V*(j, g) = Kj(g) for all j > i. Using Kolmogorov's forward equations and the definition of Qij(t), Di(t) can be rewritten as follows. n,(t) = M + E Qij(t) [bj(g) - g] j=i n ti _ = (jF(u)du) 3= —t- -+ -g. ~ o,Fj (d, ) E QiU(t) U=-i 17

Since bj(g) is nondecreasing in j E S \ {n + 1} under conditions (Al) to (A5) for each fixed 9 E [0,ga(0)], it follows that given any arbitrary c E +, bj(g) - c changes its sign at most once in j from negative to positive. Given any t, Qij(t) is TP2 function in i and j E S\{n+l} / n [11] which in turn implies that Qij(t) / Qiu(t) is also TP2 in i and j g S \ {n + 1}. Using u=i n / n the variation diminishing property of TP2 functions, j Q(t(t)[bj(g) - c] j/I Q(t) changes j=7 / U=i its sign at most once in i and the only possible change is from negative to positive. Since c n / n is arbitrary, this implies that E Qij(t)b,(g) / Qiu(t) is nondecreasing in i. Furthermore, j=i u=i it is easy to show that M / F1(u) du is nondecreasing in i when g < m + M/q [5, 10]. t Since g is a constant and j Fi(u) du is positive, we can conclude that 4i(t) changes its sign at most once in i and the only possible change is from negative to positive. Suppose there exists an i E S \ {n + 1} such that Da6(i) = R, i.e., G*(i,g,t(g)) = inf G*(i,g,t) > Ki(g). From Equation (A.1), we have 41(t) > 0 for all t E [0,oo]. We tE[o,oo] can now conclude that for all j > i and t E [0, oo], we have Ij(t) > 0. Since V*(n + 1,g) = Kn+1(g), it follows from Equation (A.1) that G*(n,g,t) > Kn(g) and Da(n) = R. Repeat this argument for j = n- 1, n- 2,..., i + 1, we have D6(j) = R for all j > i. Before the proofs of Theorem 2 part 2 and Theorem 3 are given, let us define ri = a - AV*(i,g)+ p/V*(i + 1,g) + ai [V(n + 1,g)- M] - g and show the following Lemma holds. Lemma A. 1. For any g E [0, m + M/q], rI changes its sign at most once from negative to positive in i E S \ {n + 1}. Proof. Using Kolmogorov's backward equations, we have [1- P(t)] dtG(ig,t) = r + c + [V(i g) - G'(i g,t)] [t 18

+ /i [1 - P+1,,i+(t)] [G*(i + 1,, t) - V*(i + 1, g)]. (A.2) Given g E [0,m + M/q], it is clear that G*(i + 1,g,t) > V*(i + 1,g) and M > 0. Since -G*(i, gt) 0, it follows that ri + AX [V*(i, g) - G*(i, g, t(g))] < 0. If there exists dt t)! t=t!(g) an i E S\{n+l} such that ri > 0, then V*(i,g)-G*(i,g, t(g)) < 0 which implies Da6(i) = R and V*(i,g) = K,(g). From Theorem 2 part 1, we know that if D6a(i) = R, then Da6(j) = R for all j > i. In this case, j = bj(g) - g for all j > i. Since bj(g) is nondecreasing in j, rj > 0 for all j > i. Result follows. D Proof of Theorem 2 part 2 and Theorem 3: Using Kolmogorov's forward equations, we have d n [1 - PG(t)] 'G*(ig, t) = E Pi (t)rj + AiP.i(t) [V*(ig) - G(i,g, t)] (A.3) d~t ^j=i and n [1-Pii+,,+(t)] [G'(i + 1,g, t)- V*(i + 1,g)]= M + E Qi+1,j(t)rj. (A.4) j=i+l Substituting Equation (A.4) into (A.2), we have Ai [V*(i,g) - G*(ig, t)] = [1 - Pi(t)] -G*(i,g, t) - r. - AiM - E Q+,,j(t)rj. j=i+l Equation (A.3) can now be rewritten as (,)-, [1- P1(t)]2 d g t [ P.j(t) A, Wi (t) G*(i, gt) = -M+ E A ) - Qi+li(t) r AiX,~"P,(t) =,+ AiP(t) _Ai ] Using Kolmogorov's backward equation, we have d /3i [1 - P"(t)] P+,(t). *Wi(t)= piw E Pi+,(t)ri. (A.5) (t) P(t) j=ii+ From Lemma A.1, we know that ri changes its sign at most once from negative to positive in i. Since Pi+l,3(t) is TP2 function in j and t, using the variation diminishing property of 19

dt to positive in t. Furthermore, since IVV1(O) = M< 0, VV1(t) changes its sign at most once d from negative to positive in t and so does - G* (i, g, t). Using the same argument given in dt the proof of Theorem 1, we can show that t*(g) is unique. Let U1(t) = [1 - P1i(t)] G*(i, g, t). Using Kolmogorov's forward equations, we have dn - ui 'Pij t) r+ AtPti(t)V*(i,g). dt ()=Zd3J 3=1 Equation (A.5) can therefore be rewritten as dVV(t1-38 [1 - P1i(t)] [d 1,()-A-,ii,()*ZIg)] (A.6) By the definition of W1+1(t) and Ui+1(t), it is easily to verify that [1 - Pi+11,.+1(t)][ d1 =i1 Ai+1P1+1,j+1(t) [dt U1%t A1 iP++it)G( ~) For i < k, (g) - 1, we know that W,+j (t 1 (g)) = 0 and G* (i + 1, g, t* 1(g)) =V* (i + 1, g). d d~~~~~~+i These imply -VV1t) 0. Since 1'V(O) < 0, W1(t!(g)) = 0 and -14)1(t) changes dt Wdt t it+1(g') its sign at most once from negative to positive in t, it is obvious that W2v(t* 1(g)) < 0 and Proof of Theorem 4: The same argument used in the proof of Theorem 2 part 1 can be used to prove Theorem 4 part 1. Theorem 4 part 2 is a direct consequence of Theorem 2 part 2. II1 Proof of Theorem 5: We only need to show that g* > gP. Let S1 = [R, R,..., R] and 82 = [I(t*), R, R,.. R]. Obviously 81, S2 E AP, and the expected long run cost rates of these two policies are given by Y1V,(0) - M+co = _ 0)r 20

and for all t, E [0, oo] n+l Ao(t:) + (M + mq)Fo(t,) + Ej Poj(t*)(Cj + mrj) Y62(0) j=1 92 -t -+1 = XP t(0) j Fo(u) du + qFo(t*) + E Poj(t*)rj 3=1 Now for all t, E [0, oo], it is clear that n+l Ao(t*) + (M + mq)Fo(ta) + E Poj(t,)(C + mrj) + Poo(t:)(Co + mro) * j=1 gar t*n+l j Fo(u) du + qFo(t:) + E Poj(ta)rj + Poo(t)ro j=1 > min(gl,g2) >g. References [1] R. E. Barlow, F. Proschan, Mathematical theory of reliability, 1965; John Wiley & Sons. [2] W. J. Hopp, S. Wu, "Machine Maintenance with Multiple Maintenance Actions", IIE Trans., vol 22, 1990, pp 226-233. [3] S. Karlin, Total Positivity, Vol. 1, 1968; Stanford University Press, Stanford. [4] C. T. Lam, R. H. Yeh, "Comparison of Sequential and Continuous Inspection Strategies for Deteriorating Systems", To appear in Advances in Applied Probability, June 1994. [5] C. T. Lam, R. H. Yeh, "Supplementary Results in the Comparison of Various Maintenance Strategies for Deteriorating Systems", Technical Report 92-33, University of Michigan, 1992. [6] C. T. Lam, R. H. Yeh, "Optimal Replacement Policies for Semi-Markovian Deteriorating Systems", Technical Report 92-41, University of Michigan, 1992. 21

[7] H. Luss, "Maintenance Policies when Deterioration can be Observed by Inspections", Operat. Res., vol 24, 1976, pp 359-366. [8] J. J. McCall, "Maintenance Policies for Stochastically Failing Equipment: A Survey", Management Science, vol 11, 1965, pp 493-524. [9] H. Mine, H. Kawai, "An Optimal Inspection and Replacement Policy", IEEE Trans. Reliability, vol 24, 1975, pp 305-309. [10] H. Mine, H. Kawai, "An Optimal Inspection and Replacement Policy of a Deteriorating System", J. Operat. Res. Japan, vol 25, 1982, pp 1-15. [11] M. Ohnishi, H. Kawai, H. Mine, "An Optimal Inspection and Replacement Policy for a Deteriorating system", J. Appl. Prob., vol 23, 1986, pp 973-988. [12] W. P. Pierskalla and J. A. Voelker, "A Survey of Maintenance Models: The Control and Surveillance of Deteriorating Systems", Naval Research Logistics Quarterly, vol 23, 1976, pp 353-388. [13] B. Sengupta, "Maintenance Policies under Imperfect Information", European J. Opl. Res., vol 5, 1980, pp 198-204. [14] Y. S. Sherif and M. L. Smith, "Optimal Maintenance Models for Systems Subject to Failure-A Survey", Naval Research Logistics Quarterly, vol 28, 1981, pp 47-74. [15] S. H. Sim and J. Endrenyi, "Optimal Preventive Maintenance with Repair", IEEE Transactions on Reliability, vol 37, 1988, pp 92-96. [16] S. H. Sim and J. Endrenyi, "A Failure-Repair Model with Minimal & Major Maintenance", IEEE Transactions on Reliability, vol 42, 1993, pp 134-140. 22

[17] C. Valdez-Flores and R. M. Feldman, "A Survey of Preventive Maintenance Models for Stochastically Deteriorating Single-Unit Systems", Naval Research Logistics, vol 36, 1989, pp 419-446. [18] A. P. Wood, "Optimal Maintenance Policies for Constantly Monitored Systems", Naval Research Logistics, vol 35, 1988, pp 461-471. 23