Integrating equipment investment strategy with maintenance operations under uncertain failures

Abstract

This paper studies the issue of coordinating equipment maintenance operations with capital investment strategy in the presence of random equipment failures. The traditional approach, developed by Kamien and Schwartz (KS) in their celebrated paper published in 1971, is to formulate the problem as a deterministic optimal control problem with the probability of machine failure as the state variable. With this approach, the optimal policy is deterministic. As a major departure from the KS approach, we explicitly model the underlying stochastic process of machine failures. Our analysis of the stochastic dynamic programming model offers new insights into the problem. Under a long planning horizon with a limited replacement opportunity, each individual machine serves as a revenue generator and contributes a significant amount to the profit of the system. In contrast, when the replacement budget is quite generous over a relatively short planning horizon, adding one extra machine only helps as a backup for unexpected failures of the machines purchased before it. An interesting result derived from this comparison is that a deterministic policy turns out to be optimal for the former, while a state-contingent policy must be applied to the latter. In other words, the deterministic KS approach does not work in general when a chain of machine replacement is considered. We further characterize the effects of the discount rate, productivity deterioration, learning, decision delay, and technology advancement on the optimal policy.

Appendix

1.1 Summary of notation

$$\begin{aligned}&X_{x,t}(s) = \hbox {the mode of the current machine at age}\,s\, \hbox {given that its mode at age}\,t\,\hbox {is}\,x.\\&Z = \hbox {time to the end of horizon since the last replacement.}\\&J = \hbox {junk value of a machine.}\\&R = \hbox {revenue rate when machine is working.}\\&C = \hbox {purchase price of a machine,}\\&S(t) = \hbox {sale value of a machine at age}\,t.\\&u(t) = \hbox {intensity of maintenance effort at age}\,t.\\&M(u)h = \hbox {cost of maintenance with effort}\,u\,\hbox {when the natural failure rate is}\,h.\\&\pi (u,s)= R- M(u)h\,\hbox {profit rate at age}\,t\,\hbox {with maintenance effort}\,u.\\&I = \hbox {time to the end of the horizon when a new machine is purchased. }\\&\theta _{x,t} = \hbox {the age of the current machine when it fails, given that its state at age}\,t\,\hbox {is}\,x,\\&\hbox {where}\,x=1\,\hbox {means working and}\,x=0\,\hbox {means not working. }\\&\theta ^j_{x,t} = \hbox {the age of the}\,j\,\hbox {th machine when it fails, given that its state at age}\,t\,\hbox {is}\,x,\\&\hbox {where}\,x=1\,\hbox {means working and}\,x=0\,\hbox {means not working}.\,\theta ^j_{x,t}, j \ge 1,\\&\hbox {are independent copies of}\,\theta _{x,t}.\\&F_t(s) = \hbox {the probability that the current machine fails at age}\,s\ge t\\&\hbox {given that it is working at age}\,t. \\&f_t(s) = \hbox {the density corresponding to}\,F_t(s). \\&r = \hbox {the discount rate}, r \ge 0. \end{aligned}$$

1.2 Derivation of the variational inequalities

The case of $m=\infty$ in (9).

Let $v(\tau , x, Z)$ be the optimal profit at time $\tau$ when the machine status is $x \in \{0,1\}$, and the last machine is purchased at time $Z \in [0, \tau ]$. If there is a working machine at time $\tau$, the age of the machine is $\tau -Z$. If there is no working machine in the system, i.e., $x = 0$, then

$$\begin{aligned} v(\tau , 0, Z) = \max _{\tau \le I \le {\varUpsilon }} e^{-r(I-\tau )}[v(I, 1, I) - C]^+. \end{aligned}$$

We note that the right-hand side is independent of $Z$.

The optimality condition for the problem defined in (9) can be derived as

$$\begin{aligned} \left\{ \begin{array}{l} \displaystyle -\frac{\partial v}{\partial \tau } \ge H(v, \tau , x, Z), \;\;\; v \ge G v, \\ \displaystyle \bigg (-\frac{\partial v}{\partial \tau }- H(v, \tau , x, Z)\bigg )(v - G v) = 0,\;\;\; v({\varUpsilon },x,Z) = 1\!1_{\{x=1\}} S({\varUpsilon }-Z). \end{array} \right. \end{aligned}$$

(47)

where

$$\begin{aligned} H(v, \tau , x, Z)= & {} \left\{ \begin{array}{ll} 0 &{} \text{ if } x = 0,\\ \displaystyle r - R + h(\tau -Z)\min _{0\le u \le 1}\{M(u) \\ \;\;\;+[v-J+v(\tau ,0,Z)](1-u) \} &{} \text{ if } x = 1. \end{array}\right. \\ G v (\tau , x, Z)= & {} \left\{ \begin{array}{ll} \displaystyle \max _{\tau \le I \le {\varUpsilon }} e^{-r(I-\tau )}[v(I, 1, I)-C]^+ &{} \text{ if } x = 0,\\ S(\tau -Z) + v(\tau ,0,\tau ) &{} \text{ if } x = 1. \end{array}\right. \end{aligned}$$

Let $t = \tau - Z$ be the age of the most recently purchased machine. We further define $V(t,Z) = v(t+Z, 1, Z)$ and $V^H(t,Z) = v(t+Z, 0, Z).$

Our result in Proposition 1 suggests that $V^H(t,Z) = [V(0,Z-t)-C]^+$. Thus, we only need to work with $V(t,Z)$. The conditions in (47) become

$$\begin{aligned} \left\{ \begin{array}{l} \displaystyle -\frac{\partial V}{\partial t} \ge H(V, t, Z), \;\;\; V \ge G V, \\ \displaystyle \bigg (-\frac{\partial V}{\partial t}- H(V, \tau , Z)\bigg )(V - G V) = 0,\;\;\; V({\varUpsilon },Z) = 1\!1_{\{x=1\}} S({\varUpsilon }-Z). \end{array} \right. \end{aligned}$$

(48)

where

$$\begin{aligned} H(V, t, Z)= & {} r V(t, Z) - R + h(t)\min _{0\le u \le 1}\{ M(u)+[V(t,Z)-J+V(0,Z-t)](1-u)\}, \\ G V (t, Z)= & {} S(t) + [V(0,Z-t)-C]^+. \end{aligned}$$

Next, we provide details for deriving the relation (48). Since most of our discussion also involve a finite number $m$ of replacement opportunities, which is a more general case than that for the unbounded $m,$ we derive the variational inequalities for $m < \infty .$

Derivation of the variational inequality (17)–(20).

From (16), we have

$$\begin{aligned} V(t, k, Z) \ge \mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1}\bigg [ G(t; T, u(\cdot )) + \mathbb {E}e^{-r(T\wedge \theta _{1,t}-t)}[V(0, k-1, Z- T\wedge \theta _{1,t})-C]^+\bigg ]. \end{aligned}$$

Since $1\!1_{\theta _{1,t} > t+\delta }+1\!1_{\theta _{1,t} \le t+\delta }=1$, $1\!1_{\theta _{1,t} \le t +\delta } 1\!1_{\theta _{1,t} >T} = 0$, and $T \wedge \theta _{1,t} = \theta _{1,t}$ under the event $\{\theta _{1,t} \le t + \delta \}$, we have

$$\begin{aligned} V(t,k,Z)\ge & {} \mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1} \mathbb {E}\bigg \{ 1\!1_{\theta _{1,t} > t+\delta } \bigg [ \int ^{T\wedge \theta _{1,t}}_t e^{- r(s-t)} \pi (u(s),s) d s\\&+\, e^{-r(T \wedge \theta _{1,t}-t)}[ ( J +(V(0,k-1,Z-\theta _{1,t})-C)^+) 1\!1_{\theta _{1,t}\le T}\\&+\,(S(T) +(V(0,k-1,Z-T)-C)^+ ) 1\!1_{\theta _{1,t}> T}]\bigg ]\\&+\, 1\!1_{\theta _{1,t} \le t+\delta } \bigg [\int ^{\theta _{1,t}}_t e^{-r(s-t)} \pi (u(s),s) d s\\&+ \,e^{-r(\theta _{1,t} -t)} (J+ (V(0,k-1,Z-\theta _{1,t})-C)^+)\bigg ] \bigg \}. \end{aligned}$$

Since $t + \delta \le T \wedge \theta _{1,t}$ when $\{\theta _{1,t} > t + \delta \}$, we can break up the first integral on the right-hand side from $t$ to $t+\delta$ and from $t+\delta$ to $T \wedge \theta _{1,t}$, and rearrange the terms to write

$$\begin{aligned} V(t,k,Z)\ge & {} \mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1} \mathbb {E}\bigg \{ 1\!1_{\theta _{1,t} > t+\delta } \int ^{t+\delta }_t e^{- r(s-t)} \pi (u(s),s) d s \nonumber \\&+\, 1\!1_{\theta _{1,t}\le t+ \delta } \bigg [ \int ^{\theta _{1,t}}_t e^{- r(s-t)} \pi (u(s),s) d s\nonumber \\&+\, e^{-r(\theta _{1,t}-t)} ( J +(V(0,k-1,Z-\theta _{1,t})-C)^+)\bigg ] \nonumber \\&+\, e^{-r\delta }1\!1_{\theta _{1,t} > t + \delta } \bigg [\int ^{T\wedge \theta _{1,t}}_{t+\delta } e^{- r(s-(t+\delta ))} \pi (u(s),s) d s\bigg ] \nonumber \\&+\, e^{-r\delta }e^{-r(T \wedge \theta _{1,t}-(t+\delta ))}\bigg [ ( J +(V(0,k-1,Z-\theta _{1,t})-C)^+) 1\!1_{\theta _{1,t}\le T}\nonumber \\&+\,(S(T) +(V(0,k-1,Z-T)-C)^+ ) 1\!1_{\theta _{1,t}> T}\bigg ] \bigg \}. \end{aligned}$$

(49)

Note that the intervals of integration $[t,t+\delta ]$ and $[t, \theta _{1,t}]$ under the event $\{\theta _{1,t} \le t + \delta \}$ are of length $\delta$ or smaller. Also, $E1\!1_{\theta _{1,t}\le t+\delta } = h(t) (1-u(t))\delta$. Thus, by discarding the higher-order terms in $\delta$, we can write the first two terms inside the maximum as

$$\begin{aligned}{}[\pi (u(t),t) + (J + (V(0,k-1,Z-t)-C)^+ )h(t)(1-u(t))]\delta . \end{aligned}$$

As for the third and the fourth terms inside the maximum, we observe that if $\theta _{1,t} > t + \delta$, then $\theta _{1,t} = \theta _{1,t+\delta }$. Also $e^{-r\delta } \approx 1 - r \delta$. Thus, these two terms can be written as

$$\begin{aligned}&(1-r\delta ) \mathbb {E}\bigg \{ 1\!1_{\theta _{1,t} > t + \delta } \bigg [\int ^{T \wedge \theta _{1,t+\delta }}_{t+\delta } e^{-r(s-(t+\delta ))}\pi (u(s),s) d s\bigg ]\\&\quad +\, e^{-r(T \wedge \theta _{1,t+\delta } - (t +\delta ))}\bigg [ ( J +(V(0,k-1,Z-\theta _{1,t+\delta })-C)^+)1\!1_{\theta _{1,t+\delta }\le T}\\&\quad +\, (S +(V(0,k-1,Z-T)-C)^+)1\!1_{\theta _{1,t+\delta }> T}\bigg ] \bigg \}\\&= (1-r\delta ) \mathbb {E}\bigg \{\int ^{T\wedge \theta _{1,t+\delta }}_{t+\delta } e^{-r(s-(t+\delta ))}\pi (u(s),s)ds\\&\quad +\, e^{-r(T\wedge \theta _{1,t+\delta }-(t+\delta ))}\bigg [ ( J +(V(0,k-1,Z-\theta _{1,t+\delta })-C)^+)1\!1_{\theta _{1,t+\delta }\le T}\\&\quad +\, (S +(V(0,k-1,Z-T)-C)^+)1\!1_{\theta _{1,t+\delta }> T} \bigg ]\bigg |\theta _{1,t} > t+\delta \bigg \} [1 - h(t)(1-u(t))\delta ]. \end{aligned}$$

Now we can rewrite (52) as

$$\begin{aligned} V(t,k,Z)\ge & {} \max _{0 \le u \le 1}\bigg \{ [\pi (u,t) + (J + (V(0,k-1,Z-t)-C)^+ )h(t)(1-u)]\delta \\&+\, (1-r \delta )[1 - h(t)(1-u(t))\delta ]\mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1} \mathbb {E}\bigg \{ \int ^{T \wedge \theta _{1,t+\delta }}_{t+\delta } e^{-r(s-(t+\delta ))}\pi (u(s),s) d s\nonumber \\&+\, e^{-r(T\wedge \theta _{1,t+\delta }-(t+\delta ))}\bigg [ ( J+(V(0,k-1,Z-\theta _{1,t+\delta })-C)^+)1\!1_{\theta _{1,t+\delta }\le T}\nonumber \\&+\, (S +(V(0,k-1,Z-T)-C)^+)1\!1_{\theta _{1,t+\delta }> T} \bigg ] \bigg | X_{1,t}(t+\delta ) =1\bigg \} \bigg \}\nonumber \\= & {} \max _{0 \le u \le 1}\bigg \{ [\pi (u,t) + (J + (V(0,k-1,Z-t)-C)^+ )h(t)(1-u)]\delta \nonumber \\&+\, (1-r \delta )[1 - h(t)(1-u(t))\delta ]V(t+\delta ,k,Z)\bigg \}\nonumber \\= & {} \max _{0 \le u \le 1}\bigg \{ [\pi (u,t) + (J + (V(0,k-1,Z-t)-C)^+ )h(t)(1-u)]\delta \nonumber \\&+\, (1-r \delta )[1 - h(t)(1-u(t))\delta ][V(t,k,Z) + V_t(t,k,Z)\delta ]\bigg \}. \nonumber \end{aligned}$$

(50)

By subtracting $V(t,k,Z)$ from both sides, dividing by $\delta$, and then letting $\delta \rightarrow 0$, we obtain

$$\begin{aligned} 0\ge & {} \max _{0\le u\le 1} \bigg \{ \pi (u,t) + (J + (V(0,k-1,Z-t)-C)^+ )h(t)(1-u)\\&-\,[r + h(t)(1-u)]V(t,k,Z) + V_t(t,k,Z)\bigg \}. \end{aligned}$$

By rearranging the terms, we obtain

$$\begin{aligned} 0\ge & {} V_t(t,k,Z) - r V(t,k,Z)+ R\nonumber \\&-\, h(t)\min _{0\le u\le 1} \bigg \{ M(u) + [V(t,k,z) -(J + (V(0,k-1,Z-t)-C)^+ )](1-u) \bigg \}.\nonumber \\ \end{aligned}$$

(51)

Thus, we obtain the variational inequalities (18)–(20) for the problem.

Derivation of ( 34 )–( 38 ) for the case of delayed replacement.

The optimal value function satisfies

$$\begin{aligned} V(t, k, Z)\ge & {} \mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1}\bigg [ G(t; T, u(\cdot )) + \mathbb {E}e^{-r(T\wedge (\theta _{1,t}+{\varDelta })-t)}[V(0, k\nonumber \\&\quad -1, Z- T\wedge (\theta _{1,t} + {\varDelta }))-C]^+\bigg ]. \end{aligned}$$

Since $1\!1_{\theta _{1,t} > t+\delta }+1\!1_{\theta _{1,t} \le t+\delta }=1$, $1\!1_{\theta _{1,t} \le t +\delta } 1\!1_{\theta _{1,t} >T} = 0$, and $T \wedge \theta _{1,t} = \theta _{1,t}$ under the event $\{\theta _{1,t} \le t + \delta \}$, we have

$$\begin{aligned} V(t,k,Z)\ge & {} \mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1} \mathbb {E}\bigg \{ 1\!1_{\theta _{1,t} > t+\delta } \bigg [ \int ^{T\wedge \theta _{1,t}}_t e^{- r(s-t)} \pi (u(s),s) d s\\&+\, e^{-r(T \wedge \theta _{1,t}-t)}[ J1\!1_{\theta _{1,t}\le T } + S(T) 1\!1_{\theta _{1,t}> T}]\\&+\,e^{-r(\theta _{1,t} + {\varDelta }- t)} (V(0,k-1,Z-(\theta _{1,t}+{\varDelta }))-C)^+ 1\!1_{\theta _{1,t}+{\varDelta }\le T}\\&+\,e^{-r(T- t)} (V(0,k-1,Z- T)-C)^+ 1\!1_{\theta _{1,t}+{\varDelta }> T}\bigg ]\\&+\, 1\!1_{\theta _{1,t} \le t+\delta } \bigg [\int ^{\theta _{1,t}}_t e^{-r(s-t)} \pi (u(s),s) d s+ e^{-r(\theta _{1,t} -t)} J\\&+\, e^{-r(\theta _{1,t}+{\varDelta }-t)}(V(0,k-1,Z-(\theta _{1,t}+{\varDelta }))-C)^+ 1\!1_{\theta _{1,t}+{\varDelta }<T} \\&+\, e^{-r(T-t)}(V(0,k-1,Z-T)-C)^+ 1\!1_{\theta _{1,t}+{\varDelta }\ge T} \bigg ] \bigg \}. \end{aligned}$$

Note that the last term involves $T$. This is the major distinction in the derivations of VI for this model when compared to the base model. We need to consider two cases:

Case 1: $T > t + {\varDelta }$.

In this case the event $\{\theta _{1,t}+{\varDelta }\ge T\}$ has a zero probability given $\{\theta _{1,t} < t +\delta \}$. Moreover, since $t + \delta \le T \wedge \theta _{1,t}$ when $\{\theta _{1,t} > t + \delta \}$, we can break up the first integral on the right-hand side from $t$ to $t+\delta$ and from $t+\delta$ to $T \wedge \theta _{1,t}$, and rearrange the terms to write

$$\begin{aligned} V(t,k,Z)\ge & {} \mathop {\max _{t+\delta \le T \le Z}}_{0 \le u(\cdot ) \le 1} \mathbb {E}\bigg \{1\!1_{\theta _{1,t} > t+\delta } \int ^{t+\delta }_t e^{- r(s-t)} \pi (u(s),s) d s \\&+\, 1\!1_{\theta _{1,t} \le t+\delta } \bigg [\int ^{\theta _{1,t}}_t e^{-r(s-t)} \pi (u(s),s) d s \\&+\, e^{-r(\theta _{1,t} -t)} (J+ e^{-r{\varDelta }}(V(0,k-1,Z-(\theta _{1,t}+{\varDelta }))-C)^+)\bigg ]\\&+\, 1\!1_{\theta _{1,t} > t+\delta } \bigg [ \int ^{T\wedge \theta _{1,t}}_{t+\delta } e^{- r(s-t)} \pi (u(s),s) d s \\&+\, e^{-r(T \wedge \theta _{1,t}-t)}[ J1\!1_{\theta _{1,t}\le T} + S(T) 1\!1_{\theta _{1,t}>T}]\\&+\,e^{-r(\theta _{1,t} + {\varDelta }- t)} (V(0,k-1,Z-(\theta _{1,t}+{\varDelta }))-C)^+ 1\!1_{\theta _{1,t} +{\varDelta }\le T}\\&+\,e^{-r(T - t)} (V(0,k-1,Z- T)-C)^+ 1\!1_{\theta _{1,t}+{\varDelta }> T}\bigg ] \bigg \}. \end{aligned}$$

Note that the intervals of integration $[t,t+\delta ]$ and $[t, \theta _{1,t}]$ under the event $\{\theta _{1,t} \le t + \delta \}$ are of length $\delta$ or smaller. Also, $E1\!1_{\theta _{1,t}\le t+\delta } = h(t) (1-u(t))\delta$. Thus, by discarding the higher-order terms in $\delta$, we can write the first two terms inside the maximum as

$$\begin{aligned}{}[\pi (u(t),t) + (J + e^{-r{\varDelta }}(V(0,k-1,Z-t-{\varDelta })-C)^+ )h(t)(1-u(t))]\delta . \end{aligned}$$

Then, similar arguments as before lead to the inequality

$$\begin{aligned} 0\ge & {} V_t(t,k,Z) - r V(t,k,Z)+ R- h(t)\min _{0\le u\le 1} \bigg \{ M(u) + [V(t,k,z) \nonumber \\&-(J + e^{-r{\varDelta }}(V(0,k-1,Z-t-{\varDelta })-C)^+ )](1-u) \bigg \}. \end{aligned}$$

(52)

Case 2: $T \le t + {\varDelta }$.

In this case, if a machine fails before $T$, the replacement happens exactly at $T$. Therefore, we should derive the profit function for a given replacement time $T$. A similar argument as the above leads to the ordinary differential Eq. (39) with the boundary condition (40).

1.3 Proofs

Proof of Proposition 1

It is clear that the result follows if we can prove that $V(0,k,Z)$ is increasing in $Z$ for each $t$ and $k$. Note that the result is clearly true for $k = 0$, since (12) is optimized over a larger feasible set when $Z$ is larger. Suppose that the result is true for $k-1$. Let ${\varGamma }= Z-I$, then

$$\begin{aligned}&\max _{{\varGamma }\ge T\wedge \theta _{1,t}} e^{-r({\varGamma }-t)}[V(0, k-1, Z- {\varGamma })-C]^+\\&\quad =e^{-r({\varGamma }^o-t)}[V(0, k-1, Z- {\varGamma }^o)-C]^+\\&\quad \le e^{-r({\varGamma }^o-t)} [V(0, k-1, Z+\delta - {\varGamma }^o)-C]^+\\&\quad \le \max _{{\varGamma }\ge T \wedge \theta _{1,t}} e^{-r({\varGamma }-t)}[V(0, k-1, Z+\delta - {\varGamma })-C]^+ \end{aligned}$$

where ${\varGamma }^o$ is the maximizer of the first expression.

Now denote $(T^o, u^o(\cdot ))$ to be the optimal solution for $V(t,k,Z)$. Thus,

$$\begin{aligned} V(0,k,Z+\delta )\ge & {} G(0; T^o, u^o(\cdot )) + \mathbb {E}\max _{{\varGamma }\ge T^o\wedge \theta _{1,t}}e^{-r{\varGamma }}[V(0, k-1,Z+\delta - {\varGamma })-C]^+\\\ge & {} G(0; T^o, u^o(\cdot )) + \mathbb {E}\max _{{\varGamma }\ge T^o\wedge \theta _{1,t}}e^{-r{\varGamma }} [V(0, k-1, Z- {\varGamma })-C]^+\\= & {} V(0,k,Z). \end{aligned}$$

$\square$

Proof of Proposition 2

Part (i) follows from a similar argument as that in Proposition 1. We prove iii) first. Let $W(t,k,Z)$ be the optimal profit if the current machine is not salvaged at age $t$. Then, $V(t,k,Z)= \max \{W(t,k,Z), S(t) + (V(0,k-1,Z-t)-C)^+\}.$ Hence, we need to show that

$$\begin{aligned} \max \{W(t+\delta ,k,Z+\delta ), S(t+\delta ) + (V(0,k-1,Z-t)-C)^+\} \\ \le \max \{W(t,k,Z), S(t) + (V(0,k-1,Z-t)-C)^+\}. \end{aligned}$$

Since $S(\cdot )$ is decreasing, we only need to show that $W(t+\delta ,k,Z+\delta ) \le W(t,k,Z).$ Suppose $W(t+\delta ,k,Z+\delta ) > W(t,k,Z)$ for some $\delta >0$. Note that $W$ satisfies (19) with equality. Thus,

$$\begin{aligned}&W(t+\delta ,k,Z+\delta ) - r W(t+\delta ,k,Z+\delta ) + R \\&\quad = h(t+\delta )\min _{0\le u \le 1} \bigg \{M(u) + [W(t+\delta ,k,Z+\delta ) \\&\qquad -(J+V(0,k-1,Z-t)-C)^+](1-u)\bigg \}. \end{aligned}$$

Let $u^\delta$ be the optimal solution on the right-hand side. Then,

$$\begin{aligned}&W_t(t+\delta ,k,Z+\delta ) - r W(t+\delta ,k,Z+\delta ) + R \\&\quad = h(t+\delta ) [M(u^\delta ) + [W(t+\delta ,k,Z+\delta )-(J+V(0,k-1,Z-t)-C)^+](1-u^\delta )]\\&\quad \ge h(t) [M(u^\delta ) + [W(t,k,Z)-(J+V(0,k-1,Z-t)-C)^+](1-u^\delta )]\\&\quad \ge h(t)\min _{0\le u \le 1} \bigg \{M(u) + [W(t,k,Z)-(J+V(0,k-1,Z-t)-C)^+](1-u)\bigg \} \\&\quad = W_t(t,k,Z) - r W(t,k,Z) + R. \end{aligned}$$

The first inequality follows from the induction hypothesis and the fact that $h(\cdot )$ is increasing. We deduce that

$$\begin{aligned} 0\le & {} W_t(t+\delta ,k,Z+\delta ) - r W(t+\delta ,k,Z+\delta )-[W(t,k,Z) - rW(t,k,Z)] \\= & {} \frac{d}{dt} e^{-r t}\bigg [ W(t+\delta ,k,Z+\delta ) - W(t,k,Z) \bigg ]. \end{aligned}$$

Since $W(t+\delta ,k,Z+\delta ) > W(t,k,Z)$, we have $e^{-r s}[W(s+\delta ,k,Z+\delta ) - W(s,k,Z)]>0 \text{ for } \text{ any } s>t.$ However, when $t=Z$,

$$\begin{aligned} e^{-r t}\bigg [W(t+\delta ,k,Z+\delta ) - W(t,k,Z) \bigg ]\bigg |_{t=Z}=e^{-r t}(S(Z+\delta ) - S(Z))\le 0, \end{aligned}$$

which leads to a contradiction. Hence, we conclude the result.

From (i) and (iii), we have $V(t,k,Z) \ge V(t+\delta , k , Z + \delta ) \ge V(t+\delta , k,Z)$ for $\delta >0$. Thus, (ii) follows.

The first inequality in part (iv) follows by comparing each sample path of the two value functions. The second inequality uses (iii) in comparing every sample path of the right-hand side to the left-hand side. $\square$

Proof of of Lemma 1

Since $V(0, k, Z)$ is increasing in $k$ and $Z$, we must have $\tau ^k$ decreasing in $k$ from its definition in (22). For any $Z > \tau ^k$, we must have

$$\begin{aligned} C \le V(0, k, Z) \le \int ^Z_0 e^{-rt} R dt = \frac{R}{r} (1 - e^{-rZ}). \end{aligned}$$

The second inequality follows from the fact that the optimal profit is less than the profit earned when the machine is perfectly reliable. The above inequality leads to the relation

$$\begin{aligned} Z \ge \frac{1}{r} \ln \frac{R}{R-rC}. \end{aligned}$$

The relation $\tau ^0 = \tau ^k$ is established once we prove (23).

Next, we show (23) by using induction. It is clear that the result holds for $k = 0$. Suppose that it is true for $k-1$. For $Z < \tau ^0$, we must have $V(0, k-1, Z-T) < C.$ Therefore, further replacement is never optimal for any $T >0$. We deduce that $V(t, k, Z) = V(t, 0, Z)$. $\square$

Proof of Lemma 2

If the optimal stopping age $T$ is strictly less than $Z$, both (18) and (19) hold with equality. Combining the result in Lemma 1, we deduce that $\psi (T;k,Z) \le 0$. $\square$

Proof of Proposition 3

Given the optimal stopping time $T^*_{k,Z}<Z$, we must have strict inequality in (18) and an equality in (19) at the age $T^*_{k,Z}-\delta$ for any small $\delta > 0$. In other words, $\psi (T^*_{k,Z}-\delta ; k, Z) > 0$. Hence, $\partial \psi (T^*_{k,Z}; k, Z)/\partial T \le 0$. We also note that $S^\prime (\infty ) = 0$ and $h(\infty ) = \infty$. If $\min _{0 \le u \le 1} [M(u) + (S(\infty ) - J)(1-u)] > 0$, then

$$\begin{aligned} \psi (\infty ; k, Z) = - r S(\infty ) + R + h(\infty ) \min _{0 \le u \le 1} [M(u) + (S(\infty ) - J)(1-u)] = \infty . \end{aligned}$$

On the other hand, if $\min _{0 \le u \le 1} [M(u) + (S(\infty ) - J)(1-u)]= 0$, then $\psi (\infty ; k, Z) = - r S(\infty ) + R$ is finite. In either case, $\psi (T; k, Z)=0$ has a finite number of roots over $T \in [0, Z]$. Therefore, the set $\mathcal {T}_{k,Z}$ is finite.

Finally, due to the constraint $T^*_{k,Z} \le Z$, it is possible to have a boundary solution $T^*_{k,Z} = Z$. In light of Lemma 2, a necessary condition of stopping at age $Z$ is that it is not optimal to stop at any time right before $Z$. If $\psi (Z;k,Z) < 0$, then $\psi (Z-\delta ; k, Z) < 0$ for some small enough $\delta$. This indicates that stopping at time $Z-\delta$ yields a strictly larger profit than stopping at $Z$. Therefore, we must have $\psi (Z;k,Z) \ge 0$ for $Z$ to be an optimal stopping time. $\square$

Proof of Proposition 4

We prove (ii) first, which leads to the decreasing property of $\bar{T}_k$. We note that (28) is certainly true for $k = 0$. Assume that this relation holds for $(k-1)$. Now consider the system with $k$ possible replacement opportunities. It turns out that $\bar{T}_k$ is the optimal stopping time for the current machine when the state of the system is $(0, k, Z)$ for $Z \ge \bar{Z}_k$. To see that, consider $0 \le T \le \bar{T}_k$. Then,

$$\begin{aligned} \psi (T; k, Z)= & {} S^\prime (T) - V_Z(0, k-1, Z-T) - r [S(T) + V(0, k-1, Z-T)-C] \\&+\, R- h(T)\min _{0\le u \le 1}[ M(u) + (S(T) - J)(1-u)] \\= & {} S^\prime (T) - r [S(T) + V(0, k-1, \bar{Z}_{k-1})-C] \\&+\, R- h(T)\min _{0\le u \le 1}[ M(u) + (S(T) - J)(1-u)] \\\ge & {} 0. \end{aligned}$$

The second equation follows from the induction hypothesis and the fact that $Z- T \ge \bar{Z}_{k-1}$. The last inequality follows from the definition of $\bar{T}_k$. Thus, it is optimal to stop the current machine at age $\bar{T}_k$, if the initial state is $(0, k, Z)$ for $Z \ge \bar{Z}_k$. Let $u^*_{k}(\cdot )$ be the optimal maintenance rate. Note that the optimal maintenance rate is independent of $Z$ on account of the induction hypothesis. Then,

$$\begin{aligned} \begin{array}{rl} V(t, k, Z) &{}= G(t; \bar{T}_k, u^*_k(\cdot )) + \mathbb {E}e^{-r (\bar{T}_{k} \wedge \theta _{1,t} - t)} [ V(0, k-1, Z-\bar{T}_k \wedge \theta _{1,t})-c]^+\\ &{}= G(t; \bar{T}_k, u^*_k(\cdot )) + \mathbb {E}e^{-r (\bar{T}_{k} \wedge \theta _{1,t} - t)} [ V(0, k-1, \sum _{j \le k} \bar{T}_j-\bar{T}_k \wedge \theta _{1,t})-c]^+\\ &{}= V(t, K, \sum _{j \le k} \bar{T}_j). \end{array} \end{aligned}$$

Thus, we have proved part ii).

Based on part ii), we have

$$\begin{aligned} V(0, k, \infty ) = G(0, T^*_k,u^*_k(\cdot )) + \mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})}[S(\bar{T}_k) - C + V(0, k-1,\infty )]. \end{aligned}$$

By the optimality of $T^*_k$, we must have

$$\begin{aligned} V(0, k, \infty )\ge & {} G(0, T^*_{k-1},u^*_k(\cdot )) + \mathbb {E}e^{-r (\bar{T}_{k-1} \wedge \theta _{1,0})}[S(\bar{T}_{k-1}) - C + G(0, T^*_k,u^*_k(\cdot ))\\&+ \mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})} [S(\bar{T}_k) - C +V(0, k-2,\infty )]]. \end{aligned}$$

It is easily seen that

$$\begin{aligned} \tilde{V}(0,k-1,\infty )= & {} G(0, \bar{T}_k,u^*_k(\cdot ))+ \mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})}[S(\bar{T}_k) - C + V(0,k-2,\infty )]\\\le & {} V(0, k-1, \infty ). \end{aligned}$$

Therefore,

$$\begin{aligned} 0\le & {} G(0, \bar{T}_k,u^*_k(\cdot )) - G(0, \bar{T}_{k-1},u^*_k(\cdot )) + \mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})}[S(\bar{T}_k) - C + V(0, k-1,\infty )] \\&-\, \mathbb {E}e^{-r (\bar{T}_{k-1} \wedge \theta _{1,0})}[S(\bar{T}_{k-1}) - C + \tilde{V}(0,k-1,\infty )]\\= & {} \tilde{V}(0,k-1,\infty )- V(0,k-1,\infty ) - (\mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})}-\mathbb {E}e^{-r (\bar{T}_{k-1} \wedge \theta _{1,0})}) V(0, k-2, \infty ) \\&+\, \mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})} V(0, k-1,\infty ) - \mathbb {E}e^{-r (\bar{T}_{k-1} \wedge \theta _{1,0})}\tilde{V}(0,k-1,\infty )\\= & {} (\tilde{V}(0,k-1,\infty )- V(0,k-1,\infty ))(1-\mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})})\\&+\,(\mathbb {E}e^{-r (\bar{T}_{k-1} \wedge \theta _{1,0})}-\mathbb {E}e^{-r (\bar{T}_k \wedge \theta _{1,0})}) (V(0, k-2,\infty ) - V(0, k-1, \infty )). \end{aligned}$$

If $\bar{T}_k > \bar{T}_{k-1}$, then the right-hand side of the above is negative, which leads to a contradiction. Therefore, we must have $\bar{T}_k \le \bar{T}_{k-1}$. $\square$

Proof of Proposition 5

The relation (29) comes directly from (19). The solution $\bar{u}_{k,Z}(t)$ is unique on account of the assumption $M^{\prime \prime }(u) > 0$. Next, we prove $u^*_{k,Z}(T^*_{k,Z}) < u^*_{k-1,Z - T}(0)$ for any $T \in [0, T^*_{k,Z}]$. Since it is optimal to replace the machine at time $T^*$, we must have $V(0, k-1, Z-T) \ge V(0, k-1, Z-T^*_{k,Z} \ge C.$ Thus, it is also optimal to replace the machine if it fails before age $T^*_{k,Z}$. We compare the maintenance rate before and after replacement. Right after the maintenance stops, we must have

$$\begin{aligned} M'(u^*_{k-1, Z-T}(0))= & {} V(0,k-1,Z-T^*_{k,Z})- J -[V(0,k-2,Z-T^*_{k,Z})-C]\\= & {} C - J\\> & {} S(T^*_{k,Z})- J\\= & {} M^\prime (u^*_{k, Z}(T^*_{k,Z})). \end{aligned}$$

Hence, $u^*_{k-1, Z-T}(0)>u^*_{k,Z}(T^*_{k,Z})$. $\square$

Proof of Proposition 6

The result follows from an induction argument on $j$ with a direct application of Proposition 4. $\square$

Proof of Proposition 7

We first prove i). Note that if $V(0, k-1, Z-t) - C \le 0$, no more replacement is ever optimal after the current machine is out of service. Thus, the problem reduces to a single machine problem, and the result follows from Benssousan and Sethi (2007). When $V(0, k-1, Z-t) - C \le 0$, a replacement will take place at some future time $s > t$. In this case, the optimal maintenance rate is determined by the first-order condition

$$\begin{aligned} M^\prime (u^*(t)) + V(t, k, Z) - V(0, k-1, Z-t)-J+C = 0. \end{aligned}$$

(53)

According to Proposition 4, we define $\bar{k}_Z$ to be the maximum number of replacements in a given planning horizon $Z$ such that a deterministic policy is optimal. If $k > \bar{k}_z$, then $V(0, k-1, Z-t) = V(0, k-1, Z-(t+\delta ))$. Moreover, from Proposition 2 iii), $V(t, k, Z) - V(0, k, Z-t)$ is decreasing in $t$. Together with the assumption that $M(\cdot )$ is convex, we conclude that $u^*(t)$ satisfying (53) is decreasing in $t$. If, on the other hand, $k \le \bar{k}_z$, we must $V(0, k-1, Z-t) = V(0, k-1, Z-(t+\delta ))$ for a small enough $\delta >0$ if $k = \bar{k}_Z$. Also $V(t,k,Z)$ is decreasing in $t$ by Proposition 2 ii). Thus, $u^*(t)$ satisfying (53) is decreasing in $t$.

For any $s<T^*_{k,Z}$,

$$\begin{aligned} M'(u^*_k(s))= & {} V(s,k,Z) - J -[V(0,k-1,Z-s)-C]^+\\\ge & {} S(s) +[V(0,k-1,Z-s)-C]^+ - J-[V(0,k-1,Z-s)-C]^+\\= & {} S(s)-J\\= & {} S(T^*_{k,Z}) - J. \end{aligned}$$

Since $M'(u)$ increases with $u$, we have $u^*_k(s) > u^*_k(T^*_k)$.

To see ii), we compare the maintenance rate before and after replacement. As soon as maintenance ceases, we must have $V(0,k-1,Z-T^*_{k,Z}) \ge C.$ Then, the optimal $u^*(0)$ satisfies

$$\begin{aligned} M'(u^*_{k-1}(0))= & {} V(0,k-1,Z-T^*_{k,Z})- J -[V(0,k-2,Z-T^*_{k,Z})-C]^+\\\ge & {} V(0,k-1,Z-T^*_{k,Z})- J -[V(0,k-1,Z-T^*_{k,Z})-C]^+\\= & {} C - J\\> & {} S(T^*_{k,Z})- J. \end{aligned}$$

Hence, $u^*_{k-1}(0)>u^*_k(T^*_{k,Z})$. $\square$

Proof of Proposition 8

Note that when $r = 0$, the function $\psi$ in (24) becomes

$$\begin{aligned} \psi (T; k, Z) = S^\prime (T) + R - h(T)[M(u^*_k(T)+S(T) - J)(1-u^*_k(T))], \end{aligned}$$

where $u^*_k(T)$ is the minimizer of the last term, which is independent of $k$. Therefore, the optimal stopping time $\bar{T}_k$ and the optimal maintenance rate $u^*_k(\bar{T}_k)$ obtained from (31) is independent of $k$.

Furthermore, from Proposition 6, we note that the optimal $u^*_k(t)$ depends on $k$ only via the term $V(k,t,Z)- (V(k-1, 0, k \bar{T}_0) - C)^+$ for $Z \ge (k+1) \bar{T}_0$ in (29). Together with the fact that $V(k,\bar{T}_0,(k+1)\bar{T}_0)- (V(k-1, 0, k \bar{T}_0) - C)^+ = S(\bar{T}_0)$ and $V_t(k, \bar{T}_0, (k+1)\bar{T}_0) = S^\prime (\bar{T}_0)$, we deduce that $V_t(k, t, (k+1)\bar{T}_0) = V_t(0, t, \bar{T}_0)$ and $u_k(t) = u_0(t)$ for $t \in [0, \bar{T}_0]$. $\square$

Proof of Proposition 9

The convergence of $\lim _{k\rightarrow \infty } T^*_k = T^*_\infty$ follows directly from the fact that $\bar{T}_k$ is a decreasing sequence with a lower bound zero. Also,

$$\begin{aligned} V(k, t, \infty ) \le \int ^\infty _t e^{-r(s-t)} R d s = R/r < \infty . \end{aligned}$$

Together with Proposition 2, $V(k, t, \infty )$ is an increasing sequence in $k$ with a finite upper bound. Thus, $V(t) = \lim _{k\rightarrow \infty } V(k, t, \infty )$ exists, which leads to the convergence of $\lim _{k\rightarrow \infty } u^*_k(t) = u^*_\infty (t)$. $\square$

Proof of Proposition 10

For comparison purposes, we use a superscript to parameterize the value function with the replacement lead time. For ${\varDelta }_1 > {\varDelta }_2 \ge 0$, it is clear that $V^{{\varDelta }_1}(t, 0, Z) = V^{{\varDelta }_2}(t, 0, Z)$ by the definition of $G(t; T, u(\cdot ))$. Assume that $V^{{\varDelta }_1}(t, 0, Z) \le V^{{\varDelta }_2}(t, 0, Z)$. Note that for a given ${\varDelta }$, $V^{\varDelta }(0, k-1, Z)$ is nondecreasing in $Z$, and is constant in $Z$ whenever it is higher than $C$. Since ${\varDelta }_1 > {\varDelta }_2$, we have

$$\begin{aligned}&[V^{{\varDelta }_1}(0, k-1, Z- T \wedge (\theta _{1,t} + {\varDelta }_1))-C]^+ \\&\quad = [V^{{\varDelta }_1}(0, k-1, Z- T \wedge (\theta _{1,t} + {\varDelta }_2))-C]^+ \\&\quad \le [V^{{\varDelta }_2}(0, k-1, Z- T \wedge (\theta _{1,t} + {\varDelta }_2))-C]^+ . \end{aligned}$$

Also, $e^{-r(T \wedge (\theta _{1,t} +{\varDelta }_1)-t)} < e^{-r(T \wedge (\theta _{1,t} +{\varDelta }_2)-t)}$, and the constraint $t+{\varDelta }_1 \le T$ is more restrictive than $t+{\varDelta }_2 \le T$. Hence, we conclude the result. $\square$

1.4 Computational method

The policy discussed in §5.1 can be computed efficiently by solving a series of ordinary differential equations.

1 :

Initialize:

1.1:

Set $k = 0$ and $Z_0 = \infty$.

1.2:

Compute $\tau ^0$ and evaluate the set $\mathcal {T}_{0,\infty }$ in Proposition 3.

1.3:

Find $T^*_0$ from (27) and $\bar{Z}_0 = T^*_0$.

1.4:

Compute $V(0,0,T^*_0) = W(0,0,T^*_0,T^*_0)$ by solving the differential Eq. (25) with the boundary condition (25).

2 :

The main loop: While $V(0,k, \bar{Z}_k) - C > 0$, then continue. Otherwise, stop.

2.1:

Set $k = k+1$ and $Z_k = \bar{Z}_{k-1} + \tau ^0$.

2.2:

Evaluate $\mathcal {T}_{0, Z_k}$ in Proposition 3.

2.3:

Find $T^*_k$ from (27) and $\bar{Z}_k = \bar{Z}_{k-1} + T^*_k$.

2.4:

Compute $V(0,k,T^*_0) = W(0,k,T^*_0,T^*_0)$ by solving the differential Eq. (25) with the boundary condition (25).