# Optimal policy structure for system upgrades during an asset’s lifetime

Fiona Sloothaak  Alp Akçay  Matthieu van der Heijden  Geert-Jan van Houtum

###### Abstract

We consider a continuous-time stochastic model that aims to find an optimal
upgrade policy for a single system in an asset with a fixed overhaul planning.
In a novel model, we include the key critical factors that may drive an asset
owner to upgrade a system: increasing functionality requirements due to
evolving technology, age-dependent maintenance costs, a predetermined overhaul
plan, and a finite lifetime of the asset. We characterize the structure of the
optimal upgrade policy through analytical results, and use these to establish
an efficient solution approach based on dynamic programming. We also consider
the effects of the input parameters on the optimal total costs, both
analytically as well as numerically.

##  1 Introduction

Maintaining a satisfactory operational level for assets, i.e. capital goods,
during their entire lifetime is a very challenging problem (Pierskalla and
Voelker,, 1976; Arts et al.,, 2019). Assets typically have complex designs
with many different systems installed. Each system itself has to be maintained
through several upgrades in order to keep up with the desired level of
functionality, which continually increases with the age of the asset due to
e.g. technological advancements. These maintenance activities come with costs
and may also affect the availability and operations of the asset. To minimize
downtime, it is decided upfront to have several so-called overhaul moments
during the asset’s lifetime where the major maintenance activities of
different systems can be executed in parallel. Among those maintenance
activities are system upgrades, which improves the functionality and/or
quality of an asset to meet the user’s requirements. In this paper, we study
the planning of upgrades for all critical systems for a time horizon that
equals the lifetime of the asset, where a fixed overhaul planning is set
upfront for the asset.

Tangible examples can be found in many settings, such as the maritime and
transport industries, or production processes that operate round-the-clock.
For example, a frigate is an asset that contains many different systems, e.g.
electrical, automation, radar, or weapon systems. Frigates are typically in
use for over 30 years, while the incorporated systems themselves do not
necessarily last several decades. Upfront, a schedule is created with
designated moments (”overhauls”) where the frigate is docked and large-scale
maintenance can be executed. Docking a ship is costly, and it is therefore
efficient to do as much maintenance work as possible during these periods.
Naturally, maintenance activities can be done between the overhaul moments as
well. The costs for maintaining systems may increase over time, as
difficulties can arise in finding spare parts, system expertise, and so forth.

There are many factors that play a role in the decision whether and when to
execute a system upgrade. Based on extensive discussions with multiple
companies from the maritime sector, we came to the following dominant factors:
functionality requirements, failure frequency, age-dependent failure costs and
the asset’s lifetime. We elaborate on these factors in more detail next.
First, advancement of technologies leads to the availability of systems that
perform much better than the older ones, which may cause higher expectations
of a system’s functionality. Also, advancement of technology may be prompted
by other reasons, e.g. the desire for a more energy-sustainable system, the
wish to rival or even surpass the functionality that competitors have, and
more. This aspect is studied in some papers, e.g. (Nair and Hopp,, 1992; Hopp
and Nair,, 1994), but is surprisingly often neglected in existing literature
on maintenance strategies (de Jonge and Scarf,, 2020).

Secondly, a well-studied aspect is the notion that system failures may occur
over time. Existing literature often focuses on scenarios where failures
become more likely as the system ages, corresponding to increasing failure
rates, or on constant failure rates which are common for electronics. Under an
age-replacement policy, a system is replaced at some planned age or upon
failure. In our setting, an asset owner may wish to upgrade its system to an
improved version sooner when failures become increasingly likely. There is a
vast literature on age-replacement policies, and it continues to be an active
field of research (Wang,, 2002; Zhao et al.,, 2017).

Thirdly, all maintenance activities come with associated costs, which are
stationary in classical variants of age-based maintenance models (Barlow and
Hunter,, 1960). Naturally, age-dependent costs are often necessary to model
reality more closely. Several factors contribute to the need for age-dependent
costs, such as the salvage values and the failure costs. Regarding the salvage
values, we can observe that the residual value of the system in use typically
decreases as newer and improved versions come to market. The failure costs can
also be age-dependent, especially when assets have relatively long lifetimes.
This is often due to obsolescence issues, i.e. spare parts become costlier or
even unavailable over time since newer versions are developed and the
production of older components or systems are discontinued. Moreover, trained
technicians with the knowledge and skills to execute the upgrades may no
longer be available. A well-chosen strategy can reduce the risk of
(unexpected) obsolescence issues and their corresponding costs (IEC,, 2019),
such as monitoring for obsolescence, last-time-buys (Behfard et al.,, 2015) or
partner agreements, e.g. incorporation of availability guarantees from
suppliers for critical components (Tomczykowski,, 2003). Nevertheless, the
level of uncertainty and associated costs makes this a very challenging aspect
of the problem, and can persuade the asset owner to upgrade the system to an
improved version sooner.

Finally, the timing of an upgrade may be affected by the remaining lifetime of
the asset. Existing literature often focuses on long-run expected average
costs for systems with an infinite time horizon. However, an infinite horizon
rarely applies to real-life settings: as the end of the asset’s lifetime is
near, it makes little sense to execute large-scale upgrades or improvements
anymore. Moreover, the total costs during the lifetime can be reduced by
bringing forward (or postponing) certain maintenance activities.

In this paper, we consider a continuous-time stochastic model that aims to
find an optimal upgrade policy for a single system in an asset with a fixed
overhaul planning. To do so, we account for all four of the above-mentioned
factors that may play a role in this decision. Our model is novel by bringing
these crucial aspects together, while they are relatively under-examined in
existing literature: 1) the introduction of a penalty for the functionality
gap between the old system and the required level, 2) the penalization of an
upgrade when it is not executed during an overhaul, 3) age-dependent cost
functions and 4) accounting for a finite lifetime of the asset. For this
model, we analytically characterize the structure of the optimal upgrade
policy. In particular, if we do not penalize the event where upgrades are not
executed during overhauls, we establish that there exists an optimal policy
with equidistant upgrade times for a large class of input parameters
functions. This allows for a relatively simple characterization of the optimal
upgrade policies, and can be used to design an efficient solution approach
based on dynamic programming for the case where the penalization is also
included. Finally, we establish sensitivity results with respect to the input
parameters. For example, it is intuitively clear that the optimal number of
upgrades do not increase as the price for the upgrades are higher. However,
surprisingly, this is not necessarily true with respect to many other input
parameters such as the penalty for upgrading outside overhauls, the number of
overhauls, or a more rapid increase of failure costs.

The remainder of this paper is organized as follows. In Section 2, we review
related literature, and in Section 3 we introduce our model formally. In
Section 4, we derive high-level insights for the structure of the optimal
policy if upgrade executions outside overhauls are not penalized. For the
general case, we use the results in Section 4 to introduce a solution approach
on how to calculate the optimal policy efficiently in Section 5. Finally, we
derive several managerial insights in Section 6 by testing the dependency of
the optimal policy with respect to the input parameters. We summarize our key
findings and insights in Section 7.

##  2 Literature review

Our work mainly relates to two streams of literature: (i) age-based
maintenance models with age-dependent costs, and (ii) upgrade/replacement
decision-making by considering the effects of evolving technology. In this
section, we review the related literature for both streams, and describe the
contributions of our paper.

The first streams concerns age-based maintenance models. In the classical
variants of these models, we consider a single system with a stochastic
lifetime distribution. The policy maker can choose to execute preventive
maintenance against fixed costs that are lower than the costs that are
incurred if the maintenance activity would be executed upon failure (Barlow
and Hunter,, 1960). However, it is often the case that not all times are
convenient to do maintenance on a system. Examples include systems in
production lines, the aerospace or maritime industry, or other systems in
industries where unplanned downs severely interrupt operations (Arts et al.,,
2019). In that case, the policy maker may choose to apply minimal repair until
the planned maintenance moment is reached, i.e. restore the system to a state
right before the failure took place any time a failure occurs.

There is a vast literature on these types of maintenance models (Wang,, 2002).
We point out that in these papers executing maintenance is often considered to
be a replacement of the system. Initially, stationary costs are considered
(Barlow and Hunter,, 1960; Barlow and Proschan,, 1965), but quickly also age-
dependent costs were accounted for in the models. A recent paper (Sanoubar et
al.,, 2020) shows the existence of an optimal replacement policy for an
infinite time horizon that allows for a wide class of age-dependent
replacement cost functions without minimal repair. In (Boland,, 1982; Boland
and Proschan,, 1982) a setting is described where the minimal repair costs
increase with the number of occurrences for both a finite and an infinite time
horizon. A more general minimal repair cost function is considered in (Tilquin
and Cléroux,, 1975), but replacement costs are assumed to be stationary. Non-
decreasing minimal repair and replacement costs are considered in (Segawa et
al.,, 1992) for an infinite time horizon. Literature that considers a finite
time horizon is scarcer; (Chun,, 1992; Dagpunar and Jack,, 1994) determine the
optimal number of imperfect preventive maintenance for a finite horizon given
that the minimal repair is made at any failure (with stationary costs).

This paper considers a continuous-time setting with non-decreasing upgrade
costs, failure rate and minimal repair costs, while accounting for the finite
lifetime of the asset. A major novel aspect is that not only maintenance on
system level is considered, but there already exists an overhaul plan upfront
for the entire asset. This means that the execution of upgrades during the
overhauls is typically preferred in order to prevent disruption of asset
availability. Upgrades can still be planned at moments when there is no
overhaul, but this comes with a penalty that portrays the severity of the
disruption. The effects of such overhaul plans are unexplored in existing
literature on age-based maintenance models.

The second stream of literature relates to the effect of executing upgrades to
meet (increasing) functional requirements. This aspect is studied already in a
series of papers (Nair and Hopp,, 1992; Hopp and Nair,, 1994; Nair,, 1995),
where a discrete-time model is proposed in which one needs to decide whether
to keep current technology or move to another version at every time step.
Through a Markov Decision Problem formulation, an optimal solution can be
determined through dynamic programming, and also the infinite horizon case can
be solved through an efficient algorithm. Technology advancement is also
considered in (Rajagopalan et al.,, 1998), but for an entirely different
environment where technologies provide a certain capacity that is needed for
operations. A continuous-time multi-component maintenance model is considered
in (Mercier,, 2008), where the goal is to identify when to upgrade all
components after a single technology improvement among the class of reactive
upgrade policies. Analytical results are derived for a similar problem in
(Öner et al.,, 2015), but among the class of only two possible policies
(preventive vs corrective upgrading). The paper (Nguyen et al.,, 2013) bridges
technology change with spare part inventory management in a discrete-time
model, and use dynamic programming to determine the optimal maintenance policy
for a fixed horizon. Although this paper is rich in the different aspect that
comes with upgrades (i.e. potential loss of spare parts, different maintenance
options, and so forth), no structural insights on the optimal policy are
provided.

In this paper, we consider a continuous-time stochastic model similar as in
(Mercier,, 2008). We restrict to an upgrade policy for a single system, but we
allow for continuously evolving technology and preventive upgrade policies
(with a minimal repair strategy to deal with failures). Our underlying costs
and penalty functions are age-based, and we derive structural insights for the
optimal upgrade policy. In addition, we incorporate overhaul moments where
large-scale maintenance is executed, and hence it can be cost-effective to
execute a system upgrade at such a moment.

##  3 Model description

In this section, we provide a formal description of the model. This
description requires some mathematical notation, for which we provide an
overview in Appendix A. We consider an asset that is in operation for a finite
(known) lifetime $H$. Typically, an asset has many different systems,
subsystems and components in place on different indenture levels. We take a
simplified view as illustrated in Figure 1. That is, an asset is composed of
different systems, and in turn, every system has many different (critical)
components that are needed for an operational system. The goal is to determine
a cost-optimal upgrade planning on system level.

assetsystemsystemsystemcomponentcomponentcomponent Figure 1: Asset
decomposition.

We consider a setting where the upgrade of a system may interfere with the
operations of the entire asset. It is therefore efficient to plan upgrades of
multiple systems together, where also other maintenance activities can be
performed. We assume that there exists an overhaul plan with planned moments
for the entire asset. Our goal is to provide an upgrade policy for a single
system in the asset with consideration of the overhauls, i.e. the time periods
at which the system is upgraded, either jointly with overhauls or separately.
This yields a continuous-time model with special overhaul periods where large-
scale maintenance is executed. More specifically, we assume that the asset has
an overhaul plan with fixed overhaul periods. Overhaul periods are relatively
short with respect to the total lifetime of the asset. Therefore, we allow for
a simplification of the model by assuming that the overhaul takes no time in
the planning, and hence the state of the system also has not changed after an
overhaul unless an upgrade had been planned.

We denote the time between consecutive overhauls by
$M_{1},\ldots,M_{m},M_{m+1}$, where $m$ is the number of overhauls during the
asset’s lifetime. In particular, $M_{1}$ denotes the time of the first
overhaul, and $M_{m+1}$ denotes the duration between the last overhaul and the
end of the asset’s lifetime. We also allow for system upgrades to be executed
at times when there is no overhaul, but we penalize these events with fixed
costs $c_{d}$. Note that if a system upgrade can be executed easily and has no
effect on asset-level, the setting simplifies to $c_{d}=0$. We refer to this
special setting as the base case.

As mentioned in the introduction, we model several factors that drive an asset
owner to upgrade a system through general costs and penalty functions. We
explain this in more detail next. First, we say that a system upgrade comes
with a certain upgrade costs, for which we assume the following.

###### Assumption 3.1

The upgrade costs can be written as $c_{0}-v(t)$, where $c_{0}>0$ can be seen
as the price for purchasing and installing the upgraded version of the system,
$v(t)$ corresponds to the salvage value of the current system, and $t\geq 0$
is the time since the current system is in use. Moreover, we assume that
$c_{0}>v(0)$, and that the salvage value $v(t)$ is non-increasing and
differentiable in $t$.

We point out that the price for a system upgrade $c_{0}$ is constant, i.e. has
no dependency on time. This reflects the idea that asset owners are willing to
pay a certain fixed price for the newest generation of a system, which is not
uncommon for consumer goods or certain capital goods. The salvage value
$v(\cdot)$ corresponds to the possible costs or return that comes with the
disposing of the current system in use, and depends only on time it has been
in use. In particular, we make no assumptions on whether the salvage value is
positive or negative. We do exclude the unrealistic scenarios where $c_{0}\leq
v(0)$, otherwise it would be profitable to continuously do upgrades. The
property that the salvage value is non-increasing describes the natural
phenomenon that the disposal of an older system becomes less profitable (or
costlier) over time. Also in cases where equipment is refurbished or reused,
the salvage value can decrease in age since the refurbishment process may
involve adjustments and additions of extra components (Sanoubar et al.,,
2020).

As soon as a certain system is set in place in the asset, improved versions
and upgrades may come to the market. Increasing functional requirements of the
current system may lead to the necessity for upgrading to the newer versions
to meet the desired requirements. We model this effect through a penalty
function $c_{f}(t)$, where $t$ denotes the time that the system is in use
since its last upgrade. It represents the gap in functionality between the
system in use and the upgraded version, see e.g. (Sols et al.,, 2012) for an
example of such a gap function. Note that by definition there is no gap when
the system in use is brand-new, i.e. $c_{f}(0)=0$.

###### Assumption 3.2

The functionality gap function $c_{f}(t)$ is non-decreasing function in $t$
with $c_{f}(0)=0$, where $t$ denotes the time since the last upgrade.

The system itself consists of many different (critical) components that are
subject to failures. We aggregate the failures to a single failure rate for
the system, where every failure comes with a certain expected cost. We
consider the setting where failures do not occur less likely as time
progresses, as well as that the associated costs do not lessen over time.
Moreover, we assume that the repair or replacement of a component restores the
total failure rate back to the value right before the failure event, also
known as a minimal repair strategy (Barlow and Proschan,, 1965).

###### Assumption 3.3

Let $h(t)$ denote the failure rate of the system, and $k(t)$ the expected
repair costs to bring the system back to the state just prior to the failure,
where $t\geq 0$ denotes the time since the last upgrade. The functions $h(t)$
and $k(t)$ are both non-decreasing in $t$. Repairs are immediate.

We point out that minimal repair is assumed due to the notion that the system
is composed of many components, and the failure of one critical component will
not (likely) affect the total failure rate of the system. The associated
expected costs that comes with a failure have a general form, as long as it is
non-decreasing in time. These costs are an aggregation of the actual repair
and replacement costs and downtime costs, and particularly obsolescence issues
for critical components. That is, the non-decreasing property of $k(t)$ mostly
stems from obsolescence issues that can arise when critical components are no
longer on stock nor produced, and the repair becomes costlier as a more
expensive fix needs to be applied.

###### Remark 3.4

For a system with many critical different components, it may hold that the
failure of the system relates to the failure of one particular components by a
certain probability. In this example, the expected repair costs $k(t)$ may be
written as

$\displaystyle k(t)=\sum_{i=1}^{I}k_{i}(t)p_{i},$ (3.1)

where $I$ is the number of (critical) components in the system, $p_{i}$ is the
probability that the failure is due to the breakdown of component $i$, and
$k_{i}(t)$ is the expected repair costs of a failed component $i$.

The goal is to find the policy that minimizes the total costs, which is the
aggregation of all costs and penalties over the entire asset’s lifetime. To
formalize this, we introduce the following notation. Under a given policy
$\Pi$, let $N$ denote the number of upgrades, $T_{1}$ the first upgrade moment
(if $N>0$), and $T_{2},\ldots,T_{N}$ the time between upgrade moments (if
$N\geq 2$). Write $T_{N+1}=H-\sum_{i=1}^{N}T_{i}$ as the time between the last
system upgrade (if any) and the end of the asset’s lifetime, which we also
refer to as the remaining lifetime. Let a cycle be the time a single system
version is in use, i.e. the time between the moment the system is installed
till it is disposed off, which is either at the next upgrade moment or at the
end of the asset’s lifetime. We define the cycle costs $C(T)$ as the
aggregation of the salvage value, missing functionality penalty, and the
expected costs that come with system failures in a cycle of length $T$, i.e.

$\displaystyle C(T)=-v(T)+\int_{0}^{T}c_{f}(t)\,dt+\int_{0}^{T}k(t)h(t)\,dt.$
(3.2)

We point out that the price $c_{0}$ is not included in the cycle costs as the
last cycle covers a disposal but not an upgrade. Under policy $\Pi$, let
$S^{\Pi}$ denote the number of times a system upgrade is executed but not
jointly with an overhaul, i.e.

$\displaystyle S^{\Pi}=\left|\left\\{n\leq
N:\sum_{i=1}^{n}T_{i}\neq\sum_{i=1}^{j}M_{i}\text{ for all }1\leq j\leq
m\right\\}\right|.$

Under a given policy $\Pi$, the total costs $\mathcal{K}^{\Pi}(H)$ over a
lifetime $H$ are given by

$\displaystyle\mathcal{K}^{\Pi}(H)=S^{\Pi}c_{d}+Nc_{0}+\sum_{i=1}^{N+1}C(T_{i}).$
(3.3)

The objective is to minimize the total costs, which we denote as

$\displaystyle\mathcal{K}^{*}(H)=\min_{\Pi}\mathcal{K}^{\Pi}(H)$ (3.4)

with corresponding optimal policy $\Pi^{*}$ specified by the inter-upgrade
times $T_{i}^{*},i=1,\ldots,N^{*}$.

If $c_{d}=0$, we change the total costs variable from $\mathcal{K}$ to
$\mathcal{C}$ to stress the fact we consider the base case. Under a given
policy $\Pi$, the total costs reduces to

$\displaystyle\mathcal{C}^{\Pi}(H)=Nc_{0}+\sum_{i=1}^{N+1}C(T_{i}).$ (3.5)

We denote $\mathcal{C}^{*}(H)$ as the minimal total costs in the base case.

A central question is whether we can derive results on what the optimal policy
looks like structurally. A straightforward observation is that it can never be
optimal to upgrade more than a finite number of times.

###### Lemma 3.5

Let $\bar{N}=(C(H)+v(0))/(c_{0}-v(0))\in[0,\infty)$. Any policy $\Pi$ with
$N>\bar{N}$ upgrades satisfies $\mathcal{K}^{\Pi}(H)>\mathcal{K}^{*}(H)$.

A short proof of Lemma 3.5 can be found in Appendix C. As a consequence, Lemma
3.5 indicates certain scenarios where it optimal to never upgrade a system
during the asset’s lifetime. This typically applies to expensive systems and
with little technological advancements and which are robust to failures.

###### Corollary 3.6

If the upgrade costs are very high, it is never optimal to execute upgrades.
More specifically, this is the case if $c_{0}-2v(0)\geq C(H)$.

Next to the upgrade costs, we can identify two extreme cases with respect to
the penalty $c_{d}$. The first extreme case is when an upgrade disrupts the
asset’s operation completely, and an extremely high penalty $c_{d}$ is
incurred. In that case, it would only be rewarding to upgrade during
overhauls, which reduces the number of possible upgrade plans significantly.
One needs to only decide at the $m$ overhaul moments whether to upgrade or
not, where $m$ is finite and relatively small. This can be solved through
dynamic programming, which we discuss in more detail in Section 5.2.

The other extreme case concerns the base case where $c_{d}=0$, i.e. no penalty
is given to doing upgrades if it does not coincide with an overhaul. This
corresponds to systems that can be easily maintained and upgraded without
affecting the total operation mode of the asset. It turns out that the optimal
policy has a simple structure for a large class of cycle cost functions. We
consider this in more detail next.

##  4 Analysis of the base case

In this section, we assume that $c_{d}=0$ and determine the optimal upgrade
policy for different shapes of the cycle cost function. We use these results
as building blocks to design an efficient algorithm to find the optimal policy
for the general case where also positive values of the penalty $c_{d}\geq 0$
are allowed. Therefore, we spend significant effort to determine the structure
of the optimal upgrade policy in the base case, knowing that this is directly
related to determining the optimal upgrade policy for the general case as
well. Unless stated otherwise, the proofs of the results in this section can
be found in Appendix C.1.

Recall that the total costs expression simplifies to (3.5) in the base case
for a given policy $\Pi$. In view of Lemma 3.5, we can try to derive for every
$N\in\mathbb{N}_{\geq 0}$ with $N<\bar{N}$ what the corresponding optimal
inter-upgrade times are. If we can answer this question, we can simply compare
the total costs for a finite number of upgrades to derive the optimal upgrade
policy.

Mathematically, this means that our problem can be rewritten as

$\displaystyle\mathcal{C}^{*}(H)=\min_{0\leq
N\leq\lfloor\bar{N}\rfloor}\left\\{Nc_{0}+\min_{T_{1}+\ldots+T_{N+1}=H}\left\\{\sum_{i=1}^{N+1}C(T_{i})\right\\}\right\\}.$
(4.1)

For a fixed $N$, we can therefore determine the corresponding optimal upgrade
policy by deriving the inter-upgrade times that minimizes
$\sum_{i=1}^{N}C(T_{i})+C(H-\sum_{i=1}^{N}T_{i})$, where $T_{i}\in[0,H]$ for
all $i=1,\ldots,N$. Over a finite interval, a minimum can only be attained at
points where each partial derivative (in $T_{i}$) is either zero or at the
boundaries. Note that for the optimal upgrade policy, it cannot hold that
$T_{i}^{*}=0$ for some $i=1,\ldots,N$ or $\sum_{i=1}^{N^{*}}T_{i}^{*}=H$ since
$c_{0}>v(0)$. In other words, an optimal upgrade system must satisfy the
property that every partial derivative (in $T_{i}$) is zero. That is, a
necessary condition for optimality is given by

$\displaystyle
C^{\prime}(T_{i}^{*})=C^{\prime}\left(H-\sum_{j=1}^{N}T_{j}^{*}\right),\hskip
28.45274pt\forall i=1,\ldots,N^{*},$ (4.2)

where $C^{\prime}(t)$ denotes the first derivative of the cycle cost function
$C(t),t\geq 0$. To find the optimal upgrade policy, we are therefore
interested in the sets

$\displaystyle\mathcal{T}^{N}=\left\\{(t_{1},t_{2},\ldots,t_{N})\in\mathbb{R}_{>0}^{N}:\sum_{j=1}^{N}t_{j}<H,C^{\prime}(t_{i})=C^{\prime}\left(H-\sum_{j=1}^{N}t_{j}\right),\;\;\;i=1,\ldots,N\right\\},\;\;\;N\geq
1.$ (4.3)

These sets represent the candidates for the optimal inter-upgrade times if
$N\geq 1$ upgrades would be executed during the lifetime. The optimal policy
is therefore contained in the set

$\displaystyle\mathcal{T}=\bigcup_{N=0}^{\lfloor\bar{N}\rfloor}\mathcal{T}^{N},$
(4.4)

where $\mathcal{T}^{0}=\emptyset$ represents the case where no upgrades are
executed.

The size of the sets $\mathcal{T}^{N}$ depends on the behavior of the cycle
cost function. When we take a closer look to our assumptions, we observe that
more information can be derived on the behavior of the cycle costs. Recall
that the cycle costs are given by (3.2), and the first derivative is thus
given by

$\displaystyle C^{\prime}(T)=-v^{\prime}(T)+c_{f}(T)+k(T)h(T)\geq 0.$

Our assumptions state that $c_{f}(T)+k(T)h(T)$ is non-negative and non-
decreasing in $T$, and hence this gives rise to a convex term in the cycle
cost function. The cycle costs are thus an aggregation of a convex non-
decreasing function, and a general non-decreasing function $-v(T),T\geq 0$.
Naturally, there are many settings where the salvage value also displays
typical behavior, and in turn, yields a certain behavior for the cycle cost
function. Therefore, we consider the special cases where the cycle costs are
convex (Section 4.1), concave (Section 4.2) or S-shaped (Section 4.3). We also
consider general structures for the cycle cost function for the base case in
Section 4.4.

###  4.1 Convex cycle costs

In this section, we consider the case where the salvage values are such that
the cycle costs are convex and non-decreasing. Special cases include:

  * •

Salvage values that are constant over time;

  * •

Salvage values that are linearly decreasing over time;

  * •

Salvage value functions $v(\cdot)$ that are concave (and non-increasing) up to
lifetime $H$.

An example where constant salvage values occur is when a system cannot be
resold after use, or the disposal of an older version comes with some
associated costs that is not affected by time. For this setting, the salvage
value is constant and leads to convex cycle costs. Convex cycle costs also
occur when the salvage value is linearly decreasing or non-increasing concave
over time.

For many scenarios where reselling is an option, the salvage value has the
following pattern. Initially, the resell value is close to the initial price.
But as newer versions come to the market, this resell values decreases rapidly
with increasing speed. Yet, at some point in time, the resell value start to
stabilize again. Mathematically, this corresponds to the setting where the
salvage value has a reversed S-shape, where $v(t)$ is concave non-increasing
up to some point of inflection $x_{v}$. After that, the salvage value starts
to stabilize, i.e. the salvage value becomes convex non-increasing, after
which it is (almost) constant. This implies that the cycle costs are always
convex non-decreasing on $[0,x_{v}]$. In particular, if the system’s lifetime
$H$ is relatively short and causes the point of inflection to satisfy
$x_{v}\geq H$, then the cycle costs are convex non-decreasing during the
entire lifetime of the system.

If the cycle costs are convex and non-decreasing, it turns out that an optimal
upgrade policy for the base model has a very simple structure. More
specifically, an optimal strategy to follow is to either never upgrade, or to
upgrade a finite number of times $N^{*}$ with equidistant inter-upgrade times
$T_{i}^{*}=H/(N^{*}+1)$, $i=1,\ldots,N^{*}$. Intuitively, it is clear that it
is never optimal to upgrade more than a finite number of times since every
upgrade always comes with a certain strictly positive cost. Equidistant inter-
upgrade times is a property that comes from the convexity of the cycle costs.
For example, suppose you would upgrade once at time $T$ during the asset’s
lifetime, then the total costs are given by $c_{0}+C(T)+C(H-T)$. The cycle
costs are convex, and by definition, this implies that for every
$\Delta\in[0,H/2]$,

$\displaystyle
c_{0}+C\left(\frac{H/2-\Delta}{2}\right)+C\left(\frac{H/2+\Delta}{2}\right)\leq
c_{0}+2C\left(\frac{H/2-\Delta}{2}+\frac{H/2+\Delta}{2}\right)=c_{0}+2C\left(\frac{H}{2}\right),$

where an equality holds if $\Delta=0$. Therefore, the total costs are
minimized if $T=H/2$. Similarly, this also holds in general when executing
multiple upgrades.

###### Proposition 4.1

Suppose that the cycle costs are convex. Then, it is either optimal to never
upgrade, or to do so for $N^{*}\in\mathbb{N}$ times with $N^{*}\leq\bar{N}$.
In the latter case, $T_{i}^{*}=H/(N^{*}+1)$, $i=1,\ldots,N^{*}$ and the
minimal total costs are given by

$\displaystyle\mathcal{C}^{*}(H)=\min_{0\leq
N\leq\bar{N}}\left\\{Nc_{0}+(N+1)C\left(\frac{H}{N+1}\right)\right\\}.$ (4.5)

We point out that this result already follows directly from (4.3) if the cycle
costs are strictly convex. Define

$\displaystyle\mathcal{C}^{N}(H)=Nc_{0}+(N+1)C\left(\frac{H}{N+1}\right).$
(4.6)

Proposition 4.1 states that for convex cycle costs, the minimal total costs
are obtained for some $N\leq\bar{N}$ that minimizes $\mathcal{C}^{N}(H)$. In
case that $c_{0}-v(0)$ is small, one may need to check a large number of
values. To possibly speed up the process, we show a convexity result for
$C^{N}(H)$.

###### Lemma 4.2

If the cycle cost function is convex, then the function $\mathcal{C}^{N}(H)$
is convex in $N$.

$0$$5$$10$$15$$20$$25$$30$$0$$20$$40$$60$$80$$t$$C_{A}(t)$$C_{B}(t)$ Figure 2:
Cycle costs for $t\in[0,H]$.

Proposition 4.1 and Lemma 4.2 imply that in order to find an optimal number of
upgrades $N^{*}$, we need to determine the final integer $N$ before
$\mathcal{C}^{N}(H)$ increases.

###### Example 4.3

Consider two settings, where in both settings $H=30$ years and $c_{0}=4$. In
setting A, let the cycle costs be given by

$\displaystyle
C_{A}(t)=\frac{t}{3}+\frac{3}{16}\left(\frac{t}{3}\right)^{2}+\frac{1}{10}t^{1.1},$
(4.7)

and in setting B, let

$\displaystyle
C_{B}(t)=\frac{t}{3}+\frac{3}{16}\left(\frac{t}{3}\right)^{3}+\frac{1}{10}t^{1.1}.$
(4.8)

In Figure 2, we plot the cycle costs as a function of time.

Note that the cycle costs are strictly convex on $[0,H]$ for both settings. In
view of Proposition 4.1 and Lemma 4.2, we can conclude that the (unique)
optimal policy is to upgrade $N^{*}$ times after every $H/(N^{*}+1)$ years,
where $N^{*}$ is the final integer before $C^{N}(H)$ increases. Using Table 1,
we observe that it is optimal to execute an upgrade once ($N_{A}^{*}=1$) after
15 years in setting A. In setting B, it is optimal to upgrade $N_{B}^{*}=4$
times after every 6 years.

$N$ | $\mathcal{C}^{N}_{A}(H)$ | $\mathcal{C}^{N}_{B}(H)$
---|---|---
0 | 32.9653 | 201.7153
1 | 27.3081 | 64.8081
2 | 28.0268 | 42.6101
3 | 30.3572 | 37.3884
4 | 33.3387 | 37.0887
5 | 36.6489 | 38.7322
Table 1: Total costs values for setting A and B.

###  4.2 Concave cycle costs

In this section, we consider the case that the cycle cost function is concave.
Due to our assumptions, a necessary condition for this case to occur is that
the salvage value is convex (non-increasing) over time. Implicitly, this also
means that the functionality gap and the costs due to failures should not
increase too rapidly relative to the salvage values. Special instances that
lead to concave cycle cost functions are

  * •

Constant cycle cost function;

  * •

Convex salvage value functions and $c_{f}(t)+k(t)h(t)$ is constant for all
$t\in[0,H]$;

For concave cycle cost functions, it is optimal to never upgrade. Intuitively,
this statement can be explained as follows. If it would be optimal to execute
at least one upgrade during the lifetime, then due to the concavity of the
cycle cost function, an optimal strategy would be to immediately execute all
upgrades at the start of the asset’s lifetime. But since an upgrade always
comes with a positive cost, this implies it is best to never upgrade at all.

###### Lemma 4.4

Suppose that $C(t)$ is concave for all $t\in[0,H]$. Then, it is optimal to
never do any upgrades.

###  4.3 S-shaped cycle costs

In this section, we consider the case that the cycle cost function is
S-shaped, i.e. there exists a point of inflection $x\in[0,H]$ such that the
cycle costs are convex on the interval $[0,x]$ and concave on $[x,H]$. An
example of a scenario where this could occur is when the salvage value
function has a reversed S-shape with inflection point $x_{v}$, and the missing
functionality penalty and expected failure costs stabilizes to a worst-case
scenario at some point in time. Think of an electronic device for which
upgraded versions with technological improvements appear rapidly on the
market, and make older versions obsolete. If that worst-case moment occurs
before the point of inflection $x_{v}$, we observe that the cycle costs have
an S-shape.

###### Remark 4.5

The point of inflection $x\in[0,H]$ does not necessarily have to be uniquely
defined. For example, if the cycle costs are linearly increasing on
$[a,b]\subset[0,H]$ with $a<b$, strictly convex on $[0,a]$ and strictly
concave on $[b,H]$, then any $x\in[a,b]$ can be chosen as the point of
inflection. Yet, in the results that are provided in this section, we require
the point of inflection $x$ to be chosen in a (unique) specific manner. That
is, we say that $x$ is chosen such that

$\displaystyle C(x+\Delta)-C(x)<C^{\prime}(x)\Delta,\hskip
56.9055pt\forall\Delta>0.$ (4.9)

For the mentioned example, this implies that the point of inflection is chosen
to be equal to $b$. In the remainder of this paper, points of inflection that
satisfy this property (4.9) will be referred to as satisfying the technical
requirement.

It turns out that in the case of S-shaped cycle costs, there is an optimal
policy that has a relatively simple structure. It has one of the following
structures:

  1. 1.

It is optimal to never upgrade;

  2. 2.

It is optimal to upgrade $N\geq 1$ times after every $H/(N+1)$ time units;

  3. 3.

It is optimal to upgrade $N\geq 1$ times after every $T<H/(N+1)$ time units,
where $T$ differs from the time between the final upgrade and the end of the
lifetime.

The reason that this holds already follows implicitly from the results in the
two previous sections. Suppose there is an optimal policy where we upgrade
$N=N_{1}+N_{2}-1$ times, where $N_{1}$ and $N_{2}$ are the number of times we
have inter-upgrade times in the interval $[0,x]$ and $(x,H]$, respectively
(where we slightly abuse definitions by including the time between the last
upgrade and the end of the lifetime as an inter-upgrade time). Since the cycle
costs are concave on $(x,H]$, whenever $N_{2}\geq 2$, we observe that there
exists an optimal policy where at least one of the $N_{2}$ inter-upgrade times
lies at the boundary of the interval $(x,H]$. This is not possible, and
therefore it must hold that $N_{2}\leq 1$. In particular, if $N_{2}=1$,
without loss of generality we can set the corresponding inter-upgrade time as
the time between the final upgrade and the end of the lifetime, i.e. as
$T_{N+1}$. Moreover, there exists an optimal upgrade policy where the $N_{1}$
inter-upgrade times in interval $[0,x]$ equal one another (if any) since the
cycle costs are convex on this interval.

In order to prove this formally, we require some additional results on the
optimal policy structure. The following result shows that there exists an
optimal policy where no inter-upgrade time lies strictly between
$\min\\{x,H/(N+1)\\}$ and $\max\\{x,H/(N+1)\\}$.

###### Lemma 4.6

Let the cycle costs have an S-shape with point of inflection $x\in(0,H)$ that
satisfies the technical requirement. If $N^{*}\geq 1$, then there exists an
optimal upgrade policy where for all $i=1,\ldots,N^{*}+1$ it holds that
$T_{i}^{*}\not\in\left(\min\\{x,H/(N^{*}+1)\\},\max\\{x,H/(N^{*}+1)\\}\right)$.

Secondly, it turns out that if $N^{*}\geq 1$, then there exists an optimal
policy that always contains at least one inter-upgrade time that is at most
equal to the point of inflection $x$.

###### Lemma 4.7

Let the cycle costs have an S-shape with point of inflection $x\in(0,H)$,
where $x$ satisfies the technical requirement. If $N^{*}\geq 1$, then there
exists an optimal policy for which $T_{i}^{*}\leq x$ for some
$i=1,\ldots,N^{*}+1$.

The previous two lemmas can be used to prove the main result of this section,
which gives insight in the structure of the optimal solution in case of
S-shaped cycle costs.

###### Proposition 4.8

Let the cycle costs have an S-shape with point of inflection $x\in(0,H)$
satisfying the technical requirement. It is either optimal to execute no
upgrades, or there exists an optimal policy with $N^{*}\geq 1$ upgrades that
has one of two structures: either
$T_{1}^{*}=\ldots=T_{N}^{*}=H/(N+1)=T_{N+1}^{*}$, or
$T_{1}^{*}=\ldots=T_{N}^{*}\leq x<T_{N+1}^{*}$.

Proof of Proposition 4.8. If $N^{*}=0$, then the proposition holds and there
is nothing to prove. Therefore, let $N^{*}\geq 1$ for the remainder of the
proof. That is, suppose there is an optimal policy where we upgrade
$N^{*}=N_{1}+N_{2}-1\geq 1$ times, where $N_{1}$ and $N_{2}$ are the number of
times we have inter-upgrade times in the interval $[0,x]$ and $(x,H]$,
respectively. In view of (4.2), we observe that there exists such an optimal
policy that satisfies $T_{1}=\ldots=T_{N_{1}}\leq x$ and
$T_{N_{1}+1}=\ldots=T_{N_{1}+N_{2}}>x$ (if $N_{2}>0$). We point out that
$N_{1}\geq 1$ due to Lemma 4.7. To conclude the result, what remains to show
is that $N_{2}\in\\{0,1\\}$. To that purpose, suppose that $N_{2}\geq 2$.
Consider the policy $\tilde{\Pi}$ with

$\displaystyle\tilde{T}_{i}=T_{1},\;\;\;i=1,\ldots,N_{1},$
$\displaystyle\hskip
28.45274pt\tilde{T}_{j}=T_{N^{*}+1},\;\;\;j=N_{1}+1,\ldots,N^{*}-1,$
$\displaystyle\tilde{T}_{N^{*}}=x,$ $\displaystyle\hskip
28.45274pt\tilde{T}_{N^{*}+1}=2T_{N^{*}+1}-x.$

Note that this solution is feasible, since

$\displaystyle\sum_{i=1}^{N_{1}+N_{2}}\tilde{T}_{i}=N_{1}T_{1}+(N_{2}-2)T_{N^{*}+1}+x+(2T_{N^{*}+1}-x)=N_{1}T_{1}+N_{2}T_{N^{*}+1}=H.$

Due to the technical requirement, we observe that

$\displaystyle\mathcal{C}^{\tilde{\Pi}}(H)$
$\displaystyle=N^{*}c_{0}+N_{1}C(T_{1})+(N_{2}-2)C(T_{N^{*}+1})+C(x)+C(2T_{N^{*}+1}-x)$
$\displaystyle<N^{*}c_{0}+N_{1}C(T_{1})+N_{2}C(T_{N^{*}+1})=\mathcal{C}^{\Pi}(H).$

This contradicts the hypothesis, proving our proposition.

We point out that the proof of Proposition 4.8 implies that in case of an
S-shaped cycle cost function with point of inflection $x\in(0,H)$, the
candidate solutions for optimality can be simplified to the union of the set
$\mathcal{T}^{0}$ (no upgrading) and the sets

$\displaystyle\mathcal{T}^{N_{1},N_{2}}=\left\\{(t_{1},t_{2})\in\mathbb{R}^{2}:0<t_{1}\leq
x<t_{2}<H,N_{1}\in\mathbb{N},N_{2}\in\\{0,1\\},N_{1}t_{1}+N_{2}t_{2}=H,C^{\prime}(t_{1})=C^{\prime}(t_{2})\right\\},$
(4.10)

where $N_{1}$ is bounded due to Lemma 3.5. To illustrate how this observation
can be used to determine an optimal upgrade policy, we consider the following
example.

###### Example 4.9

Suppose that $H=30$, $c_{0}\geq 1$, $c_{f}(t)+k(t)h(t)=0$ and

$\displaystyle C(t)=-v(t)=-1+\left(1+\exp^{-(x+10)}\right)^{-1}.$

This is an S-shaped function with $C(t)=-v(t)\in(-1,0)$ for all $t\in[0,H]$
and (unique) point of inflection $x=10$. Note that

$\displaystyle
C^{\prime}(t)=-v^{\prime}(t)=\frac{\exp^{-(x-10)}}{\left(1+\exp^{-(x-10)}\right)^{2}},$

This derivative satisfies $C^{\prime}(t)=C^{\prime}(20-t)$ for all
$t\in[0,10]$ and is strictly decreasing for $t\geq 10$. In particular, this
implies that there exists no optimal upgrade policy where $T_{i}\in(20,30)$
for some $i=1,\ldots,N+1$. In view of (4.10), we observe that for any
$t_{2}=20-t_{1}$ with $t_{1}\in[0,10)$ and $N_{2}=1$,

$\displaystyle N_{1}t_{1}+N_{2}t_{2}=H\hskip 28.45274pt\Rightarrow\hskip
28.45274ptt_{1}=\frac{10}{N_{1}-1}=\frac{10}{N-1}.$

Therefore, the possible candidates for the optimal upgrade policy are
$\mathcal{T}^{0}$ and

$\displaystyle\mathcal{T}^{N_{1},0}=\left\\{\left(\frac{30}{N+1},0\right)\right\\},\;\;\;N\in\mathbb{N}_{\geq
2}\hskip
42.67912pt\mathcal{T}^{N_{1},1}=\left\\{\left(\frac{10}{N-1},20-\frac{10}{N-1}\right)\right\\},\;\;\;N\in\mathbb{N}_{\geq
2}.$

We point out that any policy $\Pi\in\mathcal{T}^{N_{1},1}$ leads to total
costs that satisfy $\mathcal{C}^{\Pi}(H)\geq 0>C(H)$ for every $c_{0}\geq 1$,
i.e. every policy $\Pi\in\mathcal{T}^{N_{1},1}$ leads to a higher total costs
than when upgrades would never be executed and hence the optimal upgrade
policy will never be contained in the set $\mathcal{T}^{N_{1},1}$. Therefore,
depending on the value of $c_{0}$, the optimal policy is to either never
upgrade, or to upgrade $N\geq 2$ times with equidistant upgrade times that
equals the remaining lifetime (i.e. the time between the final upgrade and the
end of the lifetime).

To illustrate that it is possible to have a (unique) upgrade policy where the
remaining time between the last upgrade and the end of the lifetime differs
from the (other) inter-upgrade times, we provide the following example.

###### Example 4.10

Consider a setting where $H=10$ years, and the system is not subjective to
failure, i.e. $h(t)=0$ for all $t\geq 0$. Initially, the salvage value is
given by $v(0)=0.15$. After $s=4.9$, an upgrade comes to the market against
upgrade costs $c_{0}=0.75$. This event causes the missing functionality
penalty to jump to $c_{f}(t)=0.15$ for all $t\geq 4.9$ (while $c_{f}(t)=0$ for
all $t<4.9$). Moreover, this event leads to the salvage value to decrease
rapidly till time $t=5$, after which reselling the old system yields no
return. More specifically, the salvage value is given by

$\displaystyle v(t)=\left\\{\begin{array}[]{ll}0.15&\textrm{if }t\leq 4.9,\\\
0.15-30(t-4.9)^{2}&\textrm{if }4.9\leq t\leq 4.95,\\\ 30(5-t)^{2}&\textrm{if
}4.95\leq t\leq 5,\\\ 0&\textrm{if }t\geq 5.\end{array}\right.$ (4.15)

This leads to an S-shaped continuous cycle cost function, given by

$\displaystyle C(t)=\left\\{\begin{array}[]{ll}-0.15&\textrm{if }t\leq 4.9,\\\
-0.15+30(t-4.9)^{2}+0.15(t-4.9)&\textrm{if }4.9\leq t\leq 4.95,\\\
-30(5-t)^{2}+0.15(t-4.9)&\textrm{if }4.95\leq t\leq 5,\\\
0.15(t-4.9)&\textrm{if }t\geq 5.\end{array}\right.$ (4.20)

The point of inflection is thus given by $x=4.95$.

To determine the optimal upgrade policy, note that
$\bar{N}=(C(H)+v(0))/(c_{0}-v(0))=1.525$ and hence it is never optimal to
upgrade more than once. Since $C^{\prime}(t)=0.15$ for all $t\geq 5$ and
$C^{\prime}(t)>0.15$ for all $t\in(4.9,5)$, it is never optimal to upgrade at
a time in the interval $(4.9,5)$ by (4.2). Moreover, since the failure rate
equals zero, there is no advantage to upgrading before $t=4.9$. In view of
Proposition 4.8, the optimal policy is therefore either to never upgrade, or
to upgrade once at time $T_{1}=4.9$ or at time $T_{1}=5$, with corresponding
total costs $C(10)=0.765$, $c_{0}+C(4.9)+C(5.1)=0.63$ and $c_{0}+2C(5)=0.78$,
respectively. In other words, it is optimal to upgrade at time $T_{1}=4.9$
years, and the remaining time between this upgrade and the end of the lifetime
is $5.1$ years.

###  4.4 General cycle costs

In general, a necessary condition for optimality is given by (4.2). We point
out that this observation can be used to generalize the results of the
previous sections. More specifically, one can divide the lifetime of the
system $[0,H]$ into intervals for which the cycle costs are convex and
concave. That is, suppose
$[0,H]=\mathcal{H}_{1}{\cup}\ldots{\cup}\mathcal{H}_{k}$ for some (finite)
$k\in\mathbb{N}$, where the cycle costs are convex on (closed) intervals
$\mathcal{H}_{l}$ if $l$ is odd, and concave on (open) intervals
$\mathcal{H}_{l}$ if $l$ is even, and
$\mathcal{H}_{i}\cap\mathcal{H}_{j}=\emptyset$ if $i\neq j$. Note that these
intervals can be constructed even in the extreme case when the cycle costs are
concave by choosing $k=3$ and $\mathcal{H}_{1}=\\{0\\}$,
$\mathcal{H}_{2}=(0,H)$ and $\mathcal{H}_{3}=\\{H\\}$. We point out that $k$
is typically finite for instances we observe in practice, i.e. the cycle costs
do not behave erratically by changing from convex to concave infinitely often
on the finite interval $[0,H]$. Using the same argument as in the proof of
Proposition 4.8, there is always an optimal policy that satisfies the
following properties:

  * (i)

For every $l\leq k$ that is even, there is at most one $i\leq N^{*}$ for which
$T_{i}^{*}\in\mathcal{H}_{l}$;

  * (ii)

if $T_{i}^{*},T_{j}^{*}\in\mathcal{H}_{l}$ for some $l$ odd, then
$T_{i}^{*}=T_{j}^{*}$.

Note that this is a generalization of the results in the previous sections. In
case that the cycle costs are convex on $[0,H]$, then Property (ii) implies
equidistant upgrade times. In case that the cycle costs are concave on
$[0,H]$, Property (i) implies that there can only be a single
$T_{1}^{*}\in[0,H]$, and hence it is optimal to not upgrade at all. Finally,
if the cycle costs have an S-shape, then Properties (i) and (ii) imply
Proposition 4.8.

However, it may be clear that the calculation of the optimal upgrade policy
can become cumbersome when the cycle costs behaves erratically, changing from
convex to concave very often. As long as $k$ is extremely large, the optimal
inter-upgrade times can be derived efficiently for any given $N$, and hence
the overall optimal upgrade policy for the base case as well.

##  5 Solution approach

The results of the previous section can be used to derive a solution approach
to determine the optimal policy. Note that we identified two extreme cases
with respect to the penalty $c_{d}$, namely the base case where an upgrade
does not affect the asset’s operation, or the case where $c_{d}=\infty$ and
upgrades occur only during overhauls. We discuss the solution approach for
both extreme cases first, after which we explain how one can combine the
approaches to determine a solution approach for any value of $c_{d}$.

###  5.1 Solution approach for the base case

As argued in Section 4.4, the optimal inter-upgrade times can be derived
efficiently for any finite values of $N$ as long as the cycle cost functions
are relatively well-behaved, i.e. do not change between convex and concave too
often up to lifetime $H$. In particular, we considered three special cases in
Section 4. If the cycle costs are concave, then the optimal policy is to never
upgrade. If the cycle costs are convex, the optimal number of upgrades is the
first integer at which $\Delta C^{N}(H)=C^{N+1}(H)-C^{N}(H)$ is non-negative,
denoted by $N^{*}$. The optimal policy is then to upgrade $N^{*}$ times after
every $H/(N^{*}+1)$ time units. This yields Algorithm 1 as given in Appendix
B. Implicitly, this solution approach is used for Example 4.3 in Section 4.1.

If the cycle costs are S-shaped with point of inflection $x\in(0,H)$, we would
need to check more possibilities as there may be an optimal policy where the
time between the last upgrade and the asset’s lifetime differs from the other
inter-upgrade times. That is, we need to check the total costs under the
policy of never upgrading, under the class of policies with equidistant
upgrade times, and finally under the class of policies where the remaining
lifetime differs from the other inter-upgrade times. No upgrading leads to
total costs $C(H)$. Next, Proposition 4.8 shows that if it is optimal to
upgrade at least once, then there exists a policy with optimal inter-upgrade
times $T_{1}=\ldots=T_{N}\leq x$. In the class of equidistant upgrade times,
it therefore suffices to look at $N\geq H/x-1$. In that case, $C(t)$ is convex
in $t=H/(N+1)$, and hence Lemma 4.2 follows through, i.e. $\mathcal{C}^{N}(H)$
is convex in $N\geq H/x-1$. This implies that we can adopt a similar approach
as for convex cycle cost function. That is, we determine the first integer
$N\geq H/x-1$ for which $\Delta C^{N}(H)=C^{N+1}(H)-C^{N}(H)$ is non-negative.
Finally, for the class of policies with a different remaining lifetime, note
that due to the S-shape of the cycle costs and Proposition 4.8, it holds that
an optimal policy satisfies $T_{N+1}\in(x,H)$ and $T_{i}=(H-T_{N+1})/N$ for
all $i=1,\ldots,N$ if $N\geq 1$. Define

$\displaystyle\tilde{\mathcal{C}}^{N}(H,t):=Nc_{0}+NC\left(\frac{H-t}{N}\right)+C(t),\hskip
28.45274ptN\geq 1,$ (5.1)

the total costs where $N$ upgrades are executed at equidistant time intervals
of length $(H-t)/N$, and the remaining lifetime after the last upgrade is
given by $t$. By deriving $t\geq\max\\{H/(N+1),x\\}$ that minimizes
$\tilde{\mathcal{C}}^{N}(H,t)$, we inherently determine the optimal policy
that minimizes the total costs for this class of policies with $N$ upgrades.
Checking for a finite number of possible upgrades (see Lemma 3.5), leads to
all potential optimal upgrade policies with a different remaining lifetime. We
formalize this solution approach in Algorithm 2, which is given in Appendix B.

###### Example 5.1

Recall Example 4.10. The derived solution could also be found by executing
Algorithm 2 in Appendix B.

  1. 1.

The first step is to check to class of equidistant inter-upgrade times. Note
that $\lceil H/x-1\rceil=2$ and
$\mathcal{C}^{3}(H)=1.65>1.05=\mathcal{C}^{2}(H)$, this part terminates after
a single step and returns $N^{*}=2$, $T^{*}=5$ and $C=1.05$.

  2. 2.

The next step shows that $C(10)=0.765<1.05$, and hence we update our values to
$N^{*}=0$, $T^{*}=0$ and $C=0.765$.

  3. 3.

Note that $\lfloor\bar{N}\rfloor=\lfloor(C(H)+v(0))/(c_{0}-v(0))\rfloor=1$,
and hence the for loop consists only of a single step. To determine the
$t^{*}\in[5,5.1]$ that minimizes $\tilde{\mathcal{C}}^{1}(H,t)$, we observe

$\displaystyle\frac{\partial\tilde{\mathcal{C}}^{1}(H,t)}{\partial
t}=C^{\prime}(H-t)+C^{\prime}(t)=\left\\{\begin{array}[]{ll}60t-299.7&\textrm{if
}5\leq t\leq 5.05,\\\ -60t+306.3&\textrm{if }5.05\leq t<5.1,\\\
0.15&\textrm{if }t=5.1,\end{array}\right.$

This function is minimized at $t^{*}=5.1$, for which
$\tilde{\mathcal{C}}^{1}(H,t^{*})=0.63<0.765=C$. Therefore, we update our
values to $C=0.63$, $N^{*}=1$, and $T^{*}=4.9$.

  4. 4.

Finally, the algorithm returns the optimal policy $N^{*}=1$, $T_{1}^{*}=4.9$,
$T_{2}^{*}=5.1$ and corresponding minimum costs $\mathcal{C}^{*}(H)=0.63$.

When the cycle costs are not convex, concave or S-shaped, a more involved
analysis needs to be performed. As indicated in Section 4.4, this can still be
done as long as the number of times $k$ that the cycle costs changes from
convex to concave or vice versa is not too large, which is the case for most
practical instances. That is, we need to find an optimal policy under the
class of policies that satisfy the two properties indicated in Section 4.4. By
exploiting these two properties, we can design a solution approach in a
similar way as we did for the S-shaped function. However, we point that these
minimization problems become more involved for larger $k$, and it is beyond
the scope of this paper to move into more detail on this topic.

###  5.2 Solution approach when only upgrading during overhauls

The extreme case $c_{d}=\infty$ where upgrades are only executed during
overhauls reduces the number of possible upgrade plans significantly. During
the assets’ lifetime, one needs to decide only at the $m$ overhauls whether to
upgrade or not, where $m$ is finite and relatively small in practice. This can
be solved via dynamic programming. In essence, we condition on the first
occurrence of executing an upgrade at an overhaul, if any. Suppose that this
occurs at some time $T\in(0,H)$, then we split the horizon $H$ in two parts
$[0,T]$ and $(T,H]$. The total costs during the first part is given by
$c_{0}+C(T)$, while the total costs poses an identical problem except that the
time horizon has changed to a smaller value $H-T$. Since $m$ is relatively
small, we can efficiently work backwards in time to determine the optimal
policy. Details of this approach are given in Algorithm 3 of Appendix B.

###### Example 5.2

Reconsider the example as described in Example 4.3. For the additional
parameters, suppose that $c_{d}=\infty$ and $M_{i}=5$ for $i=1,\ldots,6$ in
both settings, i.e. there is an overhaul every 5 years. In setting A, recall
that the optimal policy in the base case was to upgrade after 15 years. Since
this coincides with an overhaul, this policy remains the optimal choice and
consequently, the corresponding minimal total costs of $27.308$ are not
affected. For setting B, the optimal policy does change with respect to the
base model: instead of upgrading every six years, we upgrade every five years
together with a planned overhaul. This leads to total costs of $38.732$.

###  5.3 On the optimal solution for the general case

To find the optimal policy for the general case, a similar dynamic programming
approach can be taken. To determine the optimal policy, we condition on the
first occurrence we execute an upgrade at an overhaul (if any). This cuts the
lifetime in two pieces that can be optimized separately. The expected total
costs in the first piece can be determined using a strategy similar to the
base model, since we conditioned that no upgrade is executed during an
overhaul in this interval. The second piece of the interval is an identical
problem for the general model, but with a shorter horizon length. Using
dynamic programming, we can then efficiently determine the optimal policy.

More specifically, suppose that the first time an upgrade is executed at an
overhaul is at time $T=\sum_{i=1}^{j}M_{i}$ for some $j\leq m$. In the first
interval $[0,T)$, no upgrade is executed at an overhaul moment. This
corresponds to the base case, with a slight modification that the price of
executing an upgrade comes with an additional penalty $c_{d}>0$. That is, for
a given policy $\Pi$, let $\hat{\mathcal{C}}^{\Pi}(T)$ denote the total costs
in the base case with price $c_{0}+c_{d}$ for an upgrade, horizon length $T$,
number of upgrades $\hat{N}$ with corresponding inter-upgrade times
$T_{1},\ldots,T_{\hat{N}}$ and $T_{\hat{N}+1}=T-\sum_{i=1}^{\hat{N}}T_{i}$.
Equivalently to (3.5), the total costs are given by

$\displaystyle\hat{\mathcal{C}}^{\Pi}(T)=\hat{N}\cdot(c_{0}+c_{d})+\sum_{i=1}^{\hat{N}+1}C(T_{i}).$
(5.2)

In particular, if the shape of the cycle cost function is convex, concave or
S-shaped, we derived in Section 4 that the upgrade strategy has a relatively
simple form structurally. For other shapes of the cycle cost function, a more
involved analysis needs to be executed, as indicated in Section 4.4.

The price of the upgrade at time $T$ itself is given by $c_{0}$. Finally, we
need to consider the total costs for the second interval. However, this poses
an identical problem with a shorter horizon. Since $m$ is relatively small, we
can therefore use dynamic program efficiently to determine the optimal policy,
see Algorithm 4 in Appendix B.

###### Example 5.3

Reconsider the example as described in Example 4.3, together with $c_{d}=1.5$
and $M_{i}=10$ for $i=1,2,3$ in both settings. By executing Algorithm 4 in
Appendix B, we determine the optimal policy which is given as follows. In case
A, it is optimal to execute an upgrade twice after every 10 years, i.e.
together with the planned overhauls. The associated costs are $28.027$. In
setting B, it turns out that it is optimal to upgrade once after 10 years
during an overhaul. In the remaining 20 years, it is optimal to upgrade two
more times at times that do not coincide with overhauls. That is, the optimal
policy prescribes to upgrade at times $\\{10,16\frac{2}{3},23\frac{1}{3}\\}$
years with associated total costs of $41.794$.

##  6 Effects of the input parameter on the optimal total costs

We observed that in the base case, the behavior of the cycle cost function
determines the structure of the optimal upgrade policy. When a penalty is
incurred for upgrading while there is no overhaul, the optimal upgrade policy
can be determined using dynamic programming (that uses the structural results
from the base case). The final outcome depends heavily on the values and
functions of the different input parameters. In this section, we take a closer
look at this notion both analytically as numerically. The proofs of the
analytical results can be found in Appendix C.2.

###  6.1 The effect of the penalty $c_{d}$ for upgrades outside overhaul
moments

In previous sections, we already observed that there is a strong dependence on
the penalty $c_{d}$. Whenever this penalty is very small, the optimal policy
is the same as in the base case. If the base case prescribes to upgrade only
at moments that happen to not coincide with the overhaul moments, then this
holds for all sufficiently small penalty values of $c_{d}$. If there is a
relatively high penalty $c_{d}>0$, it would be very costly to execute upgrades
outside overhaul moments, and hence it would not be optimal to do so. In fact,
whenever it is optimal to only execute upgrades during overhauls for a given
penalty $\bar{c}_{d}$, then the same strategy is optimal for every case with
$c_{d}\geq\bar{c}_{d}$. This is rather intuitive: higher penalties strictly
increase the total costs for any policy that executes upgrades outside the
overhauls, while policies that only upgrade during overhauls yield the same
total costs.

This latter notion can be generalized: as the penalty $c_{d}$ increases, the
optimal policy can only change to one where the total number of upgrades that
are not jointly executed with overhauls is less.

###### Proposition 6.1

As the penalty $c_{d}$ increases, the optimal policy can only change to one
where the number of upgrades outside overhauls is less.

In particular, if a policy $\Pi^{*}$ prescribes to only upgrade during
overhauls, then $S^{\Pi^{*}}=0$. If this is the optimal policy for some
penalty value $\bar{c}_{d}$, then Proposition 6.1 implies that the optimal
policy also only upgrades during overhauls for all $c_{d}\geq\bar{c}_{d}$.
Since for any policy that only upgrade during overhauls, the total costs do
not change in $c_{d}$, the minimum remains attained by upgrade strategy
$\Pi^{*}$.

###### Corollary 6.2

Suppose that for a penalty $\bar{c}_{d}$, an optimal policy $\Pi^{*}$
prescribes to upgrade only at planned overhauls. For any setting with
$c_{d}\geq\bar{c}_{d}$ and where the other parameter settings are the same,
$\Pi^{*}$ is also an optimal policy.

We would like to point out that Corollary 6.2 implies scenarios where the
optimal upgrade solution is insensitive to the value of $c_{d}$. Whenever the
base case leads to an upgrade plan where the timing of the upgrades coincide
with the overhauls, Lemma 6.2 implies that this is also the optimal strategy
for all $c_{d}>0$. In particular, if it is optimal to never upgrade in the
base case, then this is also the optimal strategy for positive values of
penalty $c_{d}$.

###### Example 6.3

To illustrate Proposition 6.1, we reconsider setting B of Example 4.3. That
is, suppose that the horizon length is given by $H=30$, the price is
$c_{0}=4$, and we have cycle costs

$\displaystyle
C(t)=\frac{t}{3}+\frac{3}{16}\left(\frac{t}{3}\right)^{3}+\frac{1}{10}t^{1.1}.$

$0$$0.5$$1$$1.5$$2$$2.5$$36$$38$$40$$42$$44$$c_{d}$$\mathcal{K}^{\Pi_{1}}(H)$$\mathcal{K}^{\Pi_{2}}(H)$$\mathcal{K}^{\Pi_{3}}(H)$$\mathcal{K}^{\Pi_{4}}(H)$
Figure 3: Total costs $\mathcal{K}^{\Pi}(H)$ under the four policies
$\Pi_{1}=\\{6,12,18,24\\}$, $\Pi_{2}=\\{7.5,15,22.5\\}$,
$\Pi_{3}=\\{10,16\frac{2}{3},23\frac{1}{3}\\}$ and $\Pi_{4}=\\{10,20\\}$.

Moreover, two overhauls are planned every 10 years, i.e. $M_{i}=10$,
$i=1,2,3$. We consider the relation with respect to $c_{d}\geq 0$. In view of
Figure 3, the optimal strategy is:

  * •

If $c_{d}\in[0,0.29973)$, upgrade every 6 years at times $\\{6,12,18,24\\}$
with $\mathcal{K}^{*}(H)=16+5C(6)+4c_{d}$;

  * •

If $c_{d}\in[0.29973,1.40559)$, upgrade at times $\\{7.5,15,22.5\\}$ with
$\mathcal{K}^{*}(H)=12+4C(7.5)+3c_{d}$;

  * •

If $c_{d}\in[1.40559,1.90805)$, upgrade during one overhaul moment and two
times after $6\frac{2}{3}$ years, i.e. at times
$\\{10,16\frac{2}{3},23\frac{1}{3}\\}$ or
$\\{6\frac{2}{3},13\frac{1}{3},20\\}$ with
$\mathcal{K}^{*}(H)=12+C(10)+3C(6\frac{2}{3})+2c_{d}$;

  * •

If $c_{d}\geq 1.90805$, upgrade twice during the overhauls at times
$\\{10,20\\}$ with $\mathcal{K}^{*}(H)=8+3C(10)$.

###  6.2 The effect of the number of overhaul moments

As the number of overhauls increases, it generates more possibilities to
execute upgrades without having to pay an additional penalty $c_{d}$. This
does not necessary imply that the number of upgrades (during overhauls)
increases together with the number of overhauls. The lack of this monotonicity
property can be easily explained as follows. There is an optimal upgrade
policy in the base case, which is the best you can do to minimize costs if no
penalty $c_{d}$ is incurred. This is attained in the general setting if the
overhauls coincide exactly with the upgrade moments in this policy. Therefore,
one cannot expect to do better than this, even if more overhauls are planned.
To illustrate this notion, we consider the following example.

###### Example 6.4

Reconsider setting B of Example 4.3 with $H=30$, $c_{0}=4$ and $c_{d}=5$. In
the base case when no penalty is incurred, the optimal policy is to upgrade
$N=4$ times (every 6 years) with minimal costs of 37.0887. This a lower bound
on the total costs for the general setting. If the overhauls are planned
equidistantly, this implicitly also implies that this optimal solution is
obtained whenever the number of overhaul moments is given by $m=5k-1$ for some
$k\in\mathbb{N}$. Indeed, in Table 2 we observe that the total costs are
higher when e.g. $m=5$ than $m=4$.

$m$ |  Optimal upgrade policy $\Pi^{*}$ | $K^{*}(H)$
---|---|---
0 |  {7.5,15,22.5} | 52.3884
1 |  {7.5,15,22.5} | 47.3884
2 |  {10,20} | 42.6101
3 |  {7.5,15,22.5} | 37.3884
4 |  {6,12,18,24} | 37.0887
5 |  {5,10,15,20,25} | 38.7322
Table 2: Optimal upgrade policy and minimal costs in case of overhaul moments
$M_{i}=H/(m+1)$, $i=1,\ldots,m$. The number in bold correspond to moments that
coincide with overhauls.

###  6.3 The effect of price $c_{0}$

Naturally, as the price $c_{0}$ increases, we can expect fewer upgrades and
indeed, this intuitive notion turns out to be correct. Note that Assumption
3.1 states that we only consider values of $c_{0}$ such that $c_{0}>v(0)$.

###### Lemma 6.5

The optimal number of upgrades $N^{*}$ is non-increasing in $c_{0}$.

Next, we provide an example to illustrate this result.

###### Example 6.6

Reconsider setting B of Example 4.3 with $H=30$, $c_{d}=5$ and two overhaul
moments after every 10 years. In Table 3 we display the total costs under the
optimal upgrade policy under the condition that the number of upgrades $N$ is
fixed. We point out that if $c_{0}=0$, then the optimal policy is to upgrade
after every 5 years with $N^{*}=5$, and hence we do not consider larger values
of $N$ in Table 3. We conclude that

$\displaystyle N^{*}=\left\\{\begin{array}[]{ll}5&\textrm{if
}c_{0}\in[0,0.2926]\\\ 4&\textrm{if }c_{0}\in[0.2926,0.29265]\\\ 2&\textrm{if
}c_{0}\in[0.29265,10.5944]\\\ 1&\textrm{if }c_{0}\in[10.5944,135.907]\\\
0&\textrm{if }c_{0}>135.907,\end{array}\right.$

where the corresponding optimal policies can be found in Table 3.

$N$ | $\Pi$ | $\mathcal{K}^{\Pi}(H)$
---|---|---
0 | {$\emptyset$} | 201.715
1 |  {15} |  65.8081$+c_{0}$
2 |  {10,20} |  34.6101$+2c_{0}$
3 |  {5,10,20} |  34.3175$+3c_{0}$
4 |  {5,10,15,20} |  34.0248$+4c_{0}$
5 |  {5,10,15,20,25} |  33.7322$+5c_{0}$
Table 3: Value of $\mathcal{K}^{\Pi}(H)$ under optimal upgrade policy $\Pi$
conditioned on having $N$ upgrades.

Although the optimal number of upgrades changes as $c_{0}$ increases, we
observe that there is a rapid change from $N^{*}=5$ upgrades to $N^{*}=2$ in a
relatively short interval ($c_{0}\in[0.29,0.30]$). Plotting the total costs In
Figure 4, we observe that the total costs are extremely close for
$c_{0}\in[0.29,0.30]$. For these parameter settings, it matters relatively
little which policy is chosen, as all lead to similar total costs.

$0$$0.1$$0.2$$0.3$$0.4$$0.5$$33$$34$$35$$36$$c_{0}$$N=2$$N=3$$N=4$$N=5$ Figure
4: Total costs $\mathcal{K}^{\Pi}(H)$ under optimal upgrade policy conditioned
on having $N$ upgrades.

###  6.4 The effect of the cycle costs

A final aspect concerns the effect of the cycle costs, which can be seen as
the combined contribution of the salvage value, the missing functionality
penalty function and the failure aspect. Already in the base case, we observed
the strong relation of the cycle costs with respect to what the structural
properties of the optimal upgrade policy. In this section, we focus on whether
we can say more about the upgrade policy whenever the cycle costs starts to
increase rapidly.

Intuitively, we would always upgrade before a point at which the cycle costs
increase very strongly. To a certain extent, this can be made rigorous through
the following result. Suppose that the cycle costs increase extremely after
some time $z\in(0,H)$. If it is already optimal to upgrade multiple times with
all inter-upgrade times occurring before time $z$ in an alternate setting
where we linearize the cycle costs after time $z$, i.e. a setting where a less
rapid increase in cycle costs is assumed after time $z$, then this must also
be optimal for the original setting.

###### Lemma 6.7

Consider an alternate setting with the same parameter settings, except
$\tilde{C}(t)=C(z)+(t-z)C^{\prime}(z)$ for all $t\geq z$ for some $z\in(0,H)$.
If the optimal policy $\tilde{\Pi}^{*}$ for the alternate setting is to
upgrade $\tilde{N}^{*}$ times with $\tilde{T}_{i}^{*}\leq z$ for all
$i=1,\ldots,\tilde{N}^{*}+1$, then $\tilde{\Pi}^{*}$ is also the optimal
upgrade policy for the original setting.

We point out that Lemma 6.7 may imply more information about the structure of
the optimal upgrade policy. For example, suppose that there exists an
alternate setting with the properties as in Lemma 6.7 for some $z\in(0,H)$,
and the cycle costs $C(t)$ are convex on $[0,z]$. By construction, note that
$\tilde{C}(t)$ is convex on the entire interval $[0,H]$, and hence the optimal
upgrade policy $\tilde{\Pi}^{*}$ is one with equidistant upgrade times. In
other words, there is an optimal policy where we upgrade after equidistant
time intervals that are at most equal to $z$.

To conclude this section, we would like to point out that Lemma 6.7 does not
imply that the number of upgrades always increases as the total cycle cost
curve steepens. In fact, this is actually not true as we illustrate in the
following example.

###### Example 6.8

Suppose that $c_{d}=0$ (base case) and $c_{0}=0.02$, and $H=0.5$. For the
cycle costs, consider the following. In setting A, let the cycle costs be
given by $C_{A}(t)=t+t^{2}/10=\int_{0}^{t}(1+x/5)\,dx$, and for setting B,
$C_{B}(t)=\frac{2}{3}t^{3/2}=\int_{0}^{t}\sqrt{x}\,dx$.

$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0$$0.2$$0.4$$0.6$$t$$C_{A}(t)$$C_{B}(t)$ Figure
5: Upgrade costs over $[0,t]$ if $t<H$.

We point out that $(1+x/5)\geq\sqrt{x}$ for all $x\in[0,H]$, and hence it also
holds that $C_{A}(t)\geq C_{B}(t)$ for all $t\in[0,H]$. In particular, we see
that the increase in cycle costs is steeper for setting A than for setting B,
see Figure 5. Yet, as we see in Table 4, the total costs are minimized if
$N^{*}_{A}=0$ for setting A, and if $N^{*}_{B}=2$ in setting B. In other
words, although the total costs increase is steeper in setting A, the optimal
number of upgrades is larger in setting B.

$N$ | $\mathcal{C}^{N}_{A}(H)$ | $\mathcal{C}^{N}_{B}(H)$
---|---|---
0 | 0.525 | 0.2357
1 | 0.5325 | 0.1867
2 | 0.5483 | 0.1761
3 | 0.5663 | 0.1779
Table 4: Total costs values for setting A and B.

##  7 Conclusion

This paper considers a continuous-time stochastic model in order to determine
an optimal upgrade policy for systems in an asset. This model is novel for
combining several aspects that are relatively under-examined in existing
literature: functionality gap, an predetermined overhaul plan, age-dependent
cost functions and finite lifetime of the asset. For this model, we
analytically characterize the structure of the optimal upgrade policy. For the
base case, we establish that it is optimal to never upgrade if the cycle costs
are concave, and to upgrade after every $T\in(0,H]$ time units if the cycle
costs are convex or S-shaped, where $H$ is the asset’s lifetime. We also
provide properties that an optimal upgrade policy satisfies for other shapes
of the cycle cost function, see Section 4.4. We use these results as building
blocks to design an efficient solution approach based on dynamic programming
when the penalty for executing upgrades outside overhauls is non-negative.

Naturally, the optimal upgrade policy depends heavily on the input parameters.
Many intuitive sensitivity results can be made rigorous. For example, the
optimal number of upgrades can only decrease as the price $c_{0}$ becomes
larger. A more subtle approach needs to be taken for other input parameters:
as penalty $c_{d}$ increases, the optimal upgrade policy can only change to
one where the number of upgrades that are not executed jointly with overhauls
is less. However, that does not imply that the optimal number of upgrades is
non-increasing in $c_{d}$. Similar for the number of overhauls: the optimal
number of upgrades does not need to be non-decreasing together with the number
of overhauls. Yet, adding more overhauls with respect to a former overhaul
plan will ensure that the optimal number of upgrades does not increase.
Finally, the number of upgrades also does not necessarily have to be non-
decreasing with the steepening of the total cycle cost curve.

## References

  * IEC, (2019) (2019).  Obsolescence management - application guide.  IEC 62402.
  * Arts et al., (2019) Arts, J., Basten, R., and van Houtum, G.-J. (2019).  Maintenance Service Logistics, pages 493–517.
  * Barlow and Hunter, (1960) Barlow, R. and Hunter, L. (1960).  Optimum preventive maintenance policies.  Operations Research, 8(1):90–100.
  * Barlow and Proschan, (1965) Barlow, R. and Proschan, F. (1965).  Mathematical Theory of Reliability.
  * Behfard et al., (2015) Behfard, S., van der Heijden, M. C., Al Hanbali, A., and Zijm, W. H. (2015).  Last time buy and repair decisions for spare parts.  European journal of operational research, 244(2):498–510.
  * Boland, (1982) Boland, P. J. (1982).  Periodic replacement when minimal repair costs vary with time.  Naval Research Logistics Quarterly, 29(4):541–546.
  * Boland and Proschan, (1982) Boland, P. J. and Proschan, F. (1982).  Periodic replacement with increasing minimal repair costs at failure.  Operations Research, 30(6):1183–1189.
  * Chun, (1992) Chun, Y. (1992).  Optimal number of periodic preventive maintenance operations under warranty.  Reliability Engineering & System Safety, 37(3):223–225.
  * Dagpunar and Jack, (1994) Dagpunar, J. and Jack, N. (1994).  Preventative maintenance strategy for equipment under warranty.  Microelectronics Reliability, 34(6):1089–1093.
  * de Jonge and Scarf, (2020) de Jonge, B. and Scarf, P. A. (2020).  A review on maintenance optimization.  European Journal of Operational Research, 285(3):805–824.
  * Hopp and Nair, (1994) Hopp, W. J. and Nair, S. K. (1994).  Markovian deterioration and technological change.  IIE transactions, 26(6):74–82.
  * Mercier, (2008) Mercier, S. (2008).  Optimal replacement policy for obsolete components with general failure rates.  Applied Stochastic Models in Business and Industry, 24(3):221–235.
  * Nair, (1995) Nair, S. K. (1995).  Modeling strategic investment decisions under sequential technological change.  Management Science, 41(2):282–297.
  * Nair and Hopp, (1992) Nair, S. K. and Hopp, W. J. (1992).  A model for equipment replacement due to technological obsolescence.  European Journal of Operational Research, 63(2):207–221.
  * Nguyen et al., (2013) Nguyen, T. K., Yeung, T. G., and Castanier, B. (2013).  Optimal maintenance and replacement decisions under technological change with consideration of spare parts inventories.  International Journal of Production Economics, 143(2):472–477.
  * Öner et al., (2015) Öner, K. B., Kiesmüller, G. P., and van Houtum, G.-J. (2015).  On the upgrading policy after the redesign of a component for reliability improvement.  European Journal of Operational Research, 244(3):867–880.
  * Pierskalla and Voelker, (1976) Pierskalla, W. P. and Voelker, J. (1976).  A survey of maintenance models: The control and surveillance of deteriorating systems.  Naval Research Logistics Quarterly, 23:353–388.
  * Rajagopalan et al., (1998) Rajagopalan, S., Singh, M. R., and Morton, T. E. (1998).  Capacity expansion and replacement in growing markets with uncertain technological breakthroughs.  Management Science, 44(1):12–30.
  * Sanoubar et al., (2020) Sanoubar, S., Maillart, L. M., and Prokopyev, O. A. (2020).  Age-replacement policies under age-dependent replacement costs.  IISE Transactions, 0(0):1–12.
  * Segawa et al., (1992) Segawa, Y., Masamitsu Ohnishi, and Toshihide Ibaraki (1992).  Optimal minimal-repair and replacement problem with age dependent cost structure.  Computers & Mathematics with Applications, 24(1):91–101.
  * Sols et al., (2012) Sols, A., Romero, J. J., and Cloutier, R. J. (2012).  Performance-based logistics and technology refreshment programs: Bridging the operational-life performance capability gap in the spanish f-100 frigates.  Systems Engineering, 15:422–432.
  * Tilquin and Cléroux, (1975) Tilquin, C. and Cléroux, R. (1975).  Periodic replacement with minimal repair at failure and general cost function.  Journal of Statistical Computation and Simulation, 4(1):63–77.
  * Tomczykowski, (2003) Tomczykowski, W. (2003).  A study on component obsolescence mitigation strategies and their impact on R&M.  In Annual Reliability and Maintainability Symposium, pages 332–338.
  * Wang, (2002) Wang, H. (2002).  A survey of maintenance policies of deteriorating systems.  European Journal of Operational Research, 139(3):469 – 489.
  * Zhao et al., (2017) Zhao, X., Al-Khalifa, K. N., Magid Hamouda, A., and Nakagawa, T. (2017).  Age replacement models: A summary with new perspectives and methods.  Reliability Engineering & System Safety, 161:95–105.

##  Appendix A Notation

Variable |  Meaning
---|---
$H$ |  Lifetime of the asset
$c_{0}$ |  Price of a system upgrade
$v(t)$ |  Salvage value of the current system that has been in use for time $t$
$c_{f}(t)$ |  Penalty for missing functionality of the current system that has been in use for time $t$
$h(t)$ |  Failure rate of a system that has been in use for time $t$
$k(t)$ |  Expected repair costs for a failed system that has been in use for time $t$
$c_{d}$ |  Penalty for executing an upgrade but not during an overhaul
$m$ |  The number of overhauls
$M_{i}$ |  Time between overhaul $i-1$ and $i$, with $M_{0}=0$ and $\sum_{i=1}^{m+1}M_{i}=H$
$\Pi$ |  The upgrade policy (specified by the upgrade times)
$N$ |  The number of upgrades
$T_{i}$ |  Time between upgrade $i-1$ and $i$, with $T_{0}=0$ and $\sum_{i=1}^{N+1}T_{i}=H$
$C(t)$ |  Cycle costs as specified in (3.2)
$S^{\Pi}$ |  The number of upgrades not jointly executed with an overhaul under policy $\Pi$
$\mathcal{K}^{\Pi}(H)$ |  The total costs over a lifetime $H$ under policy $\Pi$, as given in (3.3)
$\mathcal{C}^{\Pi}(H)$ |  The total costs over a lifetime $H$ under policy $\Pi$ in the base case ($c_{d}=0$), as given in (3.5)
$\bar{N}$ |  Upper bound for the number of upgrades under the optimal policy, given by $(C(H)+v(0))/(c_{0}-v(0))$
$\mathcal{C}^{N}(H)$ |  The total costs if $N$ upgrades are executed after every $H/(N+1)$ time, as given in (4.6)
$\mathcal{T}^{N}$ |  Set of candidate solutions for the optimal inter-upgrade times with $N$ upgrades, see (4.3)
$\tilde{\mathcal{C}}^{N}(H,t)$ |  Total costs if we execute $N$ upgrades every $(H-t)/N$ time, see (5.1)
$\mathcal{K}^{\Pi}(t)$ |  The total costs in $(H-t,H]$ under policy $\Pi$
Table 5: Overview of notation.

##  Appendix B Pseudo-code for solution approaches

0: Values $H$, $c_{0}$, and functions $v(t)$, $c_{f}(t)$, $k(t)$ and $h(t)$
for $t\in[0,H]$.  1: Set $N=0$;  while  _$\mathcal{C}^{N+1}(H)
<\mathcal{C}^{N}(H)$_ do Set $N=N+1$;  end while  2: return $N^{*}=N$ and
$T_{i}^{*}=H/(N+1)$, $i=1,\ldots,N^{*}+1$.

Algorithm 1 Algorithm to find optimal upgrade policy in base case with convex
cycle cost function

0: Values $H$, $c_{0}$, and functions $v(t)$, $c_{f}(t)$, $k(t)$ and $h(t)$
for $t\in[0,H]$ (with point of inflection $x$).  1: Set $N=\lceil
H/x-1\rceil$;  while  _$\mathcal{C}^{N+1}(H) <\mathcal{C}^{N}(H)$_ do Set
$N=N+1$;  end while  2: Set $N^{*}=N$, $T^{*}=H/(N+1)$ and
$C=\mathcal{C}^{N}(H)$.  3: if $C(H)<C$ then 4: Set $C=C(H)$, $N^{*}=0$ and
$T^{*}=0$;  5: end if 6: for $1\leq
N\leq\bar{N}=\lfloor(C(H)+v(0))/(c_{0}-v(0))\rfloor$ do 7: Determine
$t^{*}\in[\max\\{H/(N+1),x\\},H]$ that minimizes
$\tilde{\mathcal{C}}^{N}(H,t^{*})$ as in (5.1);  8: if $t^{*}\in(x,H)$ and
$\tilde{\mathcal{C}}^{N}(H,t^{*})<C$ then 9: Set
$C=\tilde{\mathcal{C}}^{N}(H,t^{*})$, $N^{*}=N$ and $T^{*}=(H-t^{*})/N^{*}$;
10: end if 11: end for 12: return $N^{*}$ and $T_{i}^{*}=T^{*}$,
$i=1,\ldots,N^{*}$, $T_{N^{*}+1}=H-N^{*}T^{*}$ and $\mathcal{C}^{*}(H)=C$.

Algorithm 2 Algorithm to find optimal upgrade policy and corresponding minimum
costs in base case with S-shaped cycle costs

For Algorithm 3 and Algorithm 4, we extend the notation for the total costs
$\mathcal{K}^{\Pi}(t)$ as the total costs in $(H-t,H]$ under policy $\Pi$. Let
$\mathcal{K}^{*}(t)$ denote the minimal costs over all upgrade policies on
this interval. Moreover, we denote $\hat{K}^{*}(t)$ as the minimal total costs
in $(H-t,H]$ among the policies where upgrades are only executed during
overhaul moments.

0: Values $H$, $c_{0}$, and functions $v(t)$, $c_{f}(t)$, $k(t)$ and $h(t)$
for $t\in[0,H]$.

1: Initiate $\hat{K}^{*}(M_{m+1})=C(M_{m+1})$ and save
$\hat{\mathcal{T}}(m+1)=\\{M_{m+1}\\}$;

2: for $l=m,\ldots,1$ do

3: Set
$\hat{K}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)=C\left(\sum_{i=l}^{m+1}M_{i}\right)$
and $\hat{\mathcal{T}}(l)=\\{\sum_{i=l}^{m+1}M_{i}\\}$;

4: for $j=l,\ldots,m$ do

5: Set
$x=C\left(\sum_{i=l}^{j}M_{i}\right)+c_{0}+\hat{K}^{*}\left(\sum_{i=j+1}^{m+1}M_{i}\right)$;

6: if $x<\hat{K}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)$ then

7: Set $\hat{K}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)=x$ and
$\hat{\mathcal{T}}(l)=\\{\sum_{i=l}^{j}M_{i}\\}\cup\hat{\mathcal{T}}(j+1)$;

8: end if

9: end for

10: end for

11: return Total costs
$\hat{K}^{*}(H)=\hat{K}^{*}\left(\sum_{i=1}^{m+1}M_{i}\right)$ and upgrade
policy $\hat{\mathcal{T}}(1)$.

Algorithm 3 Algorithm to find optimal upgrade policy among the class where
upgrades are only executed during overhaul moments.

0: Values $H$, $c_{0}$, $c_{d}$ and functions $v(t)$, $c_{f}(t)$, $k(t)$ and
$h(t)$ for $t\in[0,H]$.  1: Initiate
${K}^{*}(M_{m+1})=\hat{\mathcal{C}}^{*}(M_{m+1})$ and save corresponding
upgrade times ${\mathcal{T}}(m+1)$;  2: for $l=m,\ldots,1$ do 3: Set
${K}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)=\hat{\mathcal{C}}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)$
and save corresponding upgrade times ${\mathcal{T}}(l)$;  4: for
$j=l,\ldots,m$ do 5: Set
$x=\hat{\mathcal{C}}^{*}\left(\sum_{i=l}^{j}M_{i}\right)+c_{0}+{K}^{*}\left(\sum_{i=j+1}^{m+1}M_{i}\right)$
and save upgrade times $\mathcal{T}$ on
$\left[\sum_{i=1}^{l-1}M_{i},\sum_{i=1}^{j}M_{i}\right]$;  6: if
$x<{K}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)$ then 7: Set
${K}^{*}\left(\sum_{i=l}^{m+1}M_{i}\right)=x$ and
${\mathcal{T}}(l)=\mathcal{T}\cup{\mathcal{T}}(j+1)$;  8: end if 9: end for
10: end for 11: return Total costs
${K}^{*}(H)={K}^{*}\left(\sum_{i=1}^{m+1}M_{i}\right)$ and upgrade policy
${\mathcal{T}}(1)$.

Algorithm 4 Algorithm to find optimal upgrade policy.

##  Appendix C Proofs

Proof of Lemma 3.5. Write $\Pi_{0}$ as the policy to never upgrade, and note
that $\mathcal{K}^{\Pi_{0}}(H)=C(H)$. For any policy $\Pi$ with $N>\bar{N}$,
$\mathcal{K}^{\Pi}(H)\geq
Nc_{0}+(N+1)(-v(0))>\bar{N}(c_{0}-v(0))-v(0)=C(H)=\mathcal{K}^{\Pi_{0}}(H)\geq\mathcal{K}^{*}(H).$

###  C.1 Proofs for the base case

Proof of Proposition 4.1. We need to minimize the total costs by finding the
optimal policy that describes the number of upgrades $N^{*}$ and corresponding
$T_{1}^{*},\ldots,T^{*}_{N}$ such that

$\displaystyle\mathcal{C}^{*}(H)=\min_{\Pi}\mathcal{C}^{\Pi}(H).$ (C.1)

Due to Lemma 3.5, we know that it is never optimal to upgrade more than
$\bar{N}$ times. First, we answer the question what the optimal inter-upgrade
times are if the optimal number of upgrades is given by $N^{*}$.

If $N^{*}=0$, then there are no upgrades during the lifetime and
$\mathcal{C}^{*}(H)=C(H)$. Otherwise, $1\leq N^{*}\leq\bar{N}$ and the policy
also needs to describe the inter-upgrade times. Then,

$\displaystyle\mathcal{C}^{*}(H)=N^{*}c_{0}+\min_{\begin{subarray}{c}T_{1},\ldots,T_{N^{*}+1}\geq
0,\\\
T_{1}+\ldots+T_{N^{*}+1}=H\end{subarray}}\left\\{\sum_{i=1}^{N^{*}+1}C(T_{i})\right\\}.$

The term in the minimization operation is the summation of $N^{*}+1$ identical
convex non-decreasing functions in $T_{i}$, under the condition that the sum
of the inter-upgrade times $T_{i}$ is equal to $H$. By the convexity property,
this is minimized if $T_{1}=\ldots=T_{N^{*}+1}=H/(N^{*}+1)$. Using this
observation together with Lemma 3.5 concludes the proof.

Proof of Lemma 4.2. To show that $\mathcal{C}^{N}(H)$ is convex in $N$, we
require that $\Delta^{2}\mathcal{C}^{N}(H)\geq 0$. Note that

$\displaystyle\Delta\mathcal{C}^{N}(H)=\mathcal{C}^{N+1}(H)-\mathcal{C}^{N}(H)=c_{0}+C\left(\frac{H}{N+2}\right)-(N+1)\left(C\left(\frac{H}{N+1}\right)-C\left(\frac{H}{N+2}\right)\right),$

and hence

$\displaystyle\Delta^{2}\mathcal{C}^{N}(H)$
$\displaystyle=\Delta\mathcal{C}^{N+1}(H)-\Delta\mathcal{C}^{N}(H)$
$\displaystyle=(N+1)\left(C\left(\frac{H}{N+1}\right)-C\left(\frac{H}{N+2}\right)\right)-(N+3)\left(C\left(\frac{H}{N+2}\right)-C\left(\frac{H}{N+3}\right)\right).$

Write

$\displaystyle y_{i}=\frac{H}{N+2}+i\frac{H}{(N+1)(N+2)(N+3)},\hskip
56.9055ptz_{i}=\frac{H}{N+3}+i\frac{H}{(N+1)(N+2)(N+3)},$

and note that $y_{N+3}=H/(N+1)$ and $z_{N+1}=y_{0}=H/(N+2)$. Therefore,

$\displaystyle\Delta^{2}\mathcal{C}^{N}(H)$
$\displaystyle=(N+1)\sum_{i=1}^{N+3}\left(C(y_{i})-C(y_{i-1})\right)-(N+3)\sum_{j=1}^{N+1}\left(C(z_{j})-C(z_{j-1})\right)$
$\displaystyle=\sum_{i=1}^{N+3}\sum_{j=1}^{N+1}\left(\left(C(y_{i})-C(y_{i-1})\right)-\left(C(z_{j})-C(z_{j-1})\right)\right)\geq
0,$

where the final inequality follows since every single term within the
summations is non-negative due to the convexity and the non-decreasing
property of the cycle cost function.

Proof of Lemma 4.4. Suppose that there is an optimal policy $\Pi$ for which it
is optimal to upgrade exactly $N\geq 1$ times. Since $C(t)$ is concave and
non-decreasing in $t\geq 0$, the term $\sum_{i=1}^{N+1}C(T_{i})$ is minimized
if $T_{1}=\ldots=T_{N}=0$ and $T_{N+1}=H$. However, in that case it follows
that

$\displaystyle\mathcal{C}^{\Pi}(H)=N(c_{0}-v(0))+C(H)>C(H),$ (C.2)

where the latter corresponds to the total costs under the policy to never
execute an upgrade. This contradicts the hypothesis.

Proof of Lemma 4.6. This lemma only applies to cases where $x\neq H/(N+1)$,
because otherwise it holds that
$\left(\min\\{x,H/(N^{*}+1)\\},\max\\{x,H/(N^{*}+1)\\}\right)=\emptyset$.
Therefore, we assume $x\neq H/(N+1)$ for the remainder of the proof. Suppose
that there would be an optimal strategy $\Pi$ with an inter-upgrade time
strictly between point of inflection $\min\\{x,H/(N+1)\\}$ and
$\max\\{x,H/(N+1)\\}$ with $N\geq 1$. Due to symmetry, we can assume without
loss of generality that

$\displaystyle
T_{N+1}\in\left(\min\left\\{x,\frac{H}{N+1}\right\\},\max\left\\{x,\frac{H}{N+1}\right\\}\right).$

Moreover, note that a necessary condition for an policy to be optimal is

$\displaystyle C^{\prime}(T_{i})=C^{\prime}(T_{N+1})\hskip 85.35826pt\forall
i=1,\ldots,N.$ (C.3)

Moreover, let

$\displaystyle a=\inf\\{t\in[0,x]:C^{\prime}(t)=C^{\prime}(T_{N+1})\\},\hskip
14.22636pt$ $\displaystyle
c=\inf\\{t\in[x,H]:C^{\prime}(t)=C^{\prime}(T_{N+1})\\},$ (C.4) $\displaystyle
b=\sup\\{t\in[0,x]:C^{\prime}(t)=C^{\prime}(T_{N+1})\\},\hskip 14.22636pt$
$\displaystyle d=\sup\\{t\in[x,H]:C^{\prime}(t)=C^{\prime}(T_{N+1})\\}.$ (C.5)

We point out that at least $a$ and $b$ or $c$ and $d$ are well-defined (or
all). Moreover, if it is well-defined, note that $a=b$ in case of strict
convexity on $[0,x]$ and $c=d$ in case of strict concavity on $[x,H]$. Since
$C(\cdot)$ has an S-shape with point of inflection $x$ that satisfies the
technical requirement, we observe that $[a,b]$ and $[c,d]$ contain all
solutions of (C.3), and $C(\cdot)$ is linear on both intervals (if they
exist). Therefore, without loss of generality, we can say that $T_{i}\in[a,b]$
for all $i=1,\ldots,N_{1}$ and $T_{i}\in[c,d]$ for all
$i=N_{1}+1,\ldots,N_{1}+N_{2}$ where $N_{1}+N_{2}=N+1$. Note that $N_{1}=0$ if
$a,b$ do not exist, and similarly, $N_{2}=0$ if $c,d$ do not exist.

Case $x<H/(N+1)$: or in other words, $x<T_{N+1}<H/(N+1)$. In that case $c,d$
are well-defined values and $T_{N+1}\in[c,d]$ and $N_{2}\geq 1$. If $N_{2}=1$,
then $N=N_{1}\geq 1$ and $a,b$ must also be well-defined. Therefore,
$T_{i}\leq b\leq x<H/(N+1)$ for all $i=1,\ldots,N$. Recalling that
$T_{N+1}<H/(N+1)$ yields

$\displaystyle\sum_{i=1}^{N+1}T_{i}<\sum_{i=1}^{N+1}H/(N+1)=H,$

which is a contradiction. Therefore, we require that $N_{2}\geq 2$. In that
case, we can construct the policy $\tilde{\Pi}$ where

$\displaystyle\tilde{T}_{i}=T_{i},\;\;\;i=1,\ldots,N-1,\hskip
28.45274pt\tilde{T}_{N}=T_{N}+T_{N+1}-x,\hskip 28.45274pt\tilde{T}_{N+1}=x.$

Note that $\tilde{T}_{N}\in(x,H)$. Since the cycle costs are concave and due
to the technical requirement,
$C(T_{N})+C(T_{N+1})>C(\tilde{T}_{N})+C(\tilde{T}_{N+1})$, and hence

$\displaystyle\mathcal{C}^{\tilde{\Pi}}(H)=\mathcal{C}^{\Pi}(H)+C(\tilde{T}_{N})+C(\tilde{T}_{N+1})-C(T_{N})-C(T_{N+1})<\mathcal{C}^{\Pi}(H).$
(C.6)

In other words, our original policy $\Pi$ is not optimal, contradicting our
hypothesis.

Case $x>H/(N+1)$: or in other words $H/(N+1)<T_{N+1}<x$. In that case, $a$ and
$b$ are well-defined and $T_{N+1}\in[a,b]$ and $N_{1}\geq 1$. We will show
that if this policy $\Pi$ exists, then there is another policy $\tilde{\Pi}$
that yields the same minimal total costs but has no inter-upgrade time in
$(H/(N+1),x)$. First, if $T_{i}\in[a,b]$ for all $i=1,\ldots,N$, then let
policy $\tilde{\Pi}$ be given by $\tilde{T}_{i}=H/(N+1)$ for all
$i=1,\ldots,N+1$. By construction, it holds that
$\mathcal{C}^{\tilde{\Pi}}(H)=\mathcal{C}^{\Pi}(H)$ since the cycle costs are
linear on $[a,b]$, and hence $\tilde{\Pi}$ is also an optimal upgrade policy.

Next, suppose that $T_{i}\not\in[a,b]$ for all $i=1,\ldots,N$, implying
directly that $c$ and $d$ are well-defined. Without loss of generality, we can
order the inter-upgrade times such that $T_{i}\in[c,d]$ for $i=1,\ldots,l$ for
some $l\geq 1$ and $T_{i}\in[a,b]$ for $i=l+1,\ldots,N$ (if any). Consider the
policy

$\displaystyle\tilde{T}_{i}=T_{i},\;\;\;i=1,\ldots,l,\hskip
28.45274pt\tilde{T}_{N+1}=\tilde{T}_{j}=\frac{\sum_{i=l+1}^{N+1}T_{i}}{N-l+1},\;\;\;j=l+1,\ldots,N.$

Note that $\tilde{T}_{N+1}\geq a$ and

$\displaystyle\tilde{T}_{N+1}=\frac{\sum_{i=l+1}^{N+1}T_{i}}{N-l+1}=\frac{H-\sum_{i=1}^{l}T_{i}}{N-l+1}<\frac{H-lH/(N+1)}{N-l+1}=\frac{H}{N+1}<x.$

That is, policy $\tilde{\Pi}$ has no inter-upgrade time in $(H/(N+1),x)$, and
$\mathcal{C}^{\tilde{\Pi}}(H)=\mathcal{C}^{\Pi}(H)$ since the cycle costs are
linear on $[a,b]$.

Proof of Lemma 4.7. Suppose that the statement is not true, and
$T_{1},\ldots,T_{N+1}>x$. In view of Lemma 4.6, we observe that

$\displaystyle\sum_{i=1}^{N+1}T_{i}\geq\sum_{i=1}^{N+1}\frac{H}{N+1}=H,$

where $\sum_{i=1}^{N+1}T_{i}=H$ holds if and only if
$T_{1}=\ldots=T_{N+1}=H/(N+1)>x$. In other words, if $T_{1},\ldots,T_{N+1}>x$,
then $T_{1}=\ldots=T_{N+1}=H/(N+1)>x$, and the total costs under this policy
are given by $Nc_{0}+(N+1)C(H/(N+1))$.

Consider the policy $\tilde{\Pi}$ where $\tilde{T}_{1}=\ldots=\tilde{T}_{N}=x$
and $\tilde{T}_{N+1}=H-Nx$. Then, due to the technical requirement and the
notion that we have a setting where $x<H/(N+1)$,

$\displaystyle\mathcal{C}^{\Pi}(H)=Nc_{0}+NC(x)+C(H-nx)<Nc_{0}+(N+1)C(H/(N+1)),$

contradicting the hypothesis.

###  C.2 Proofs for the sensitivity analysis

Proof of Proposition 6.1. This is a direct consequence of the total cost
function (3.3). Note that for any fixed policy $\Pi$, the total cost function
is linear in $c_{d}$ with slope $S^{\Pi}$. Therefore, as penalty $c_{d}$
increases, the optimal policy can only change to one with a smaller value of
$S^{\Pi}$.

Proof of Lemma 6.5. For every policy $\Pi$, the total costs are given by
(3.3). Write $\mathcal{P}_{N}$ as the set of all possible upgrade policies
with $N$ upgrades. We observe that for every $N\in\mathbb{N}$, we can
determine the upgrade times that minimize the total costs by solving

$\displaystyle
K^{N}(H):=\min_{\Pi\in\mathcal{P}_{N}}S^{\Pi}c_{d}+\sum_{i=1}^{N+1}C(T_{i}),$
(C.7)

regardless of the value of $c_{0}$. In particular,

$\displaystyle\mathcal{K}^{*}(H)=\min_{N\in\mathbb{N}}\left\\{Nc_{0}+K^{N}(H)\right\\}.$

We point out that

$\displaystyle\frac{\partial}{\partial c_{0}}\left(Nc_{0}+K^{N}(H)\right)=N.$

That is, it is linear in $c_{0}$ with slope $N$, and $N^{*}$ is the argument
that minimizes the total costs. In conclusion, the optimal number of upgrades
will never decrease.

Proof of Lemma 6.7. For any general variable $X$, let $\tilde{X}$ denote the
corresponding one in the alternate setting. For any policy $\Pi$, it holds
that $\mathcal{K}^{\Pi}(H)\geq\mathcal{\tilde{K}}^{\Pi}(H)$ since
$\tilde{C}(t)\leq C(t)$ for all $t\in[0,H]$. Moreover, since
$\tilde{T}_{i}^{*}\leq z$ for all $i=1,\ldots,\tilde{N}^{*}+1$, it holds that
$\mathcal{K}^{\tilde{\Pi}^{*}}(H)=\mathcal{\tilde{K}}^{*}(H)$. In conclusion,
we obtain

$\displaystyle\mathcal{K}^{\tilde{\Pi}^{*}}(H)=\mathcal{\tilde{K}}^{*}(H)\leq\mathcal{\tilde{K}}^{\Pi}(H)\leq\mathcal{K}^{\Pi}(H),$

for any policy $\Pi$. We can conclude that $\tilde{\Pi}^{*}$ is also optimal
for the original setting.