Analysis of a POMDP Model for an Optimal Maintenance Problem with Multiple Imperfect Repairs

Nobuyuki Tamura

Department of Industrial and Systems Engineering, Hosei University, Tokyo, Japan.

DOI: 10.4236/ajor.2023.136008                

Abstract

I consider a system whose deterioration follows a discrete-time and discrete-state Markov chain with an absorbing state. When the system is put into practice, I may select operation (wait), imperfect repair, or replacement at each discrete-time point. The true state of the system is not known when it is operated. Instead, the system is monitored after operation and some incomplete information concerned with the deterioration is obtained for decision making. Since there are multiple imperfect repairs, I can select one option from them when the imperfect repair is preferable to operation and replacement. To express this situation, I propose a POMDP model and theoretically investigate the structure of an optimal maintenance policy minimizing a total expected discounted cost for an unbounded horizon. Then two stochastic orders are used for the analysis of our problem.

Keywords

Partially Observable Markov Decision Process, Imperfect Repair, Stochastic Order, Monotone Property, Optimal Maintenance Policy

1. Introduction

With recent advances in science and technology, many systems have become more complex and more massive. Accordingly, the breakdown or deterioration of such systems could frequently result in economic and social damage in our communities. To address those problems mathematically, preventive maintenance models for stochastically deteriorating systems have been widely investigated in the literature. Osaki [1] summarized the mathematical approach for reliability and maintenance. And the papers by Cho and Parlar [2] , Dekker [3] , and Wang [4] are excellent reviews of the subject. Since various techniques for detecting the deterioration level of systems have been developed and available without expensive cost, one can adopt condition-based maintenance (CBM) rather than time-based maintenance (TBM) in many cases. The above three reviews include studies on CBM as well as TBM. Jardine et al. [5] summarized and reviewed the recent research and developments in diagnostics and prognostics of mechanical systems implementing CBM with algorithms and technologies for data processing. Also, Olde Keizer et al. [6] and Alaswad and Xiang [7] reviewed stochastic models for addressing issues on CBM policies.

For constructing a stochastic model for CBM, I need first express a deterioration of a system as some kind of stochastic process. If one can assume that the deterioration levels of a system correspond to finite non-negative integers, then the deterioration of the system could be described as a Markov chain with an absorbing state which expresses a failure of the system. This model is called Markovian deteriorating system and Markov decision processes (MDP) are used for addressing maintenance problems. Derman [8] , Douer and Yechiali [9] , Hopp [10] , Kurt and Kharoufeh [11] [12] , and Tamura [13] studied the discrete-time Markovian deteriorating system and derived the sufficient conditions that some monotone properties including the control-limit policy hold. Also, Lam and Yeh [14] [15] [16] , and Yeh [17] [18] studied the continuous-time Markovian deteriorating system. These studies have some barriers from realistic viewpoints because it is too costly or too technically difficult to detect the true state of a system in practical situations. In these cases, a system is monitored and some incomplete information on the true state of the system is obtained to select an optimal action. When I observe alternative characteristics instead of a true deterioration level of a system at each inspection, the result has some kind of relationship with the true deterioration level although it does not express the true deterioration level. Then, partially observable Markov decision process (POMDP) models are available to express the behavior of such systems. POMDP models use a so-called state vector whose element means the probability of a true state. If an element of a state vector is always 1 in a POMDP model, it coincides with an MDP model. Ross [19] incorporated the concept of incomplete information into the Markovian system with two states. However, it was a little different from the POMDP model. Afterwards, Ohnishi et al. [20] , Grosfeld-Nir [21] [22] , and Chen et al. [23] studied the POMDP model for the maintenance problem where only replacement can be selected as a maintenance action. Srinivasan and Parlikad [24] studied the extended POMDP model which is called a POSMDP (Partially Observable Semi-Markov Decision Process) for optimizing maintenance decisions. Oosterom [25] used the new stochastic order to analyze the POMDP model. And Kivanc et al. [26] applied the POMDP model to real problems. On the other hand, Ohnishi et al. [27] proposed the POMDP model with minimal repair as well as replacement and showed that the monotone properties hold under several assumptions. Pham [28] reviewed the studies on imperfect maintenance. Then, Ivy and Pollock [29] introduced the concept of repair, which is different from minimal repair, in addition to replacement for the POMDP model and derived the marginal monotonicity for the two-state model. Tamura et al. [30] and Fan et al. [31] also studied the POMDP model with repair and replacement. Then, these models assumed one option for repair. In practical situations, however, I can choose some options for repair of which the effects are different.

In this paper, I construct a POMDP model where one of H imperfect repairs can be selected as a maintenance action as well as replacement. For the model, I theoretically investigate the structure of an optimal maintenance policy minimizing the total expected discounted cost for unbounded horizon via the theory of stochastic order relations. In particular, I derive sufficient conditions for monotone properties of the optimal maintenance policy.

2. Model Description

Now I consider a system whose deterioration follows a discrete-state and discrete-time Markov chain with an absorbing state. The system can be classified into one of $N+2$ states, and then, state 0 represents the process before any deterioration takes place that is, it is an initial new state, whereas, $N+1$ is a failure state of the system. The intermediates state 1 ∙∙∙ N are ordered to reflect the relative degree of deterioration in ascending order. Thus, I let $p_{ij}$ denote the transition probability of the Markov chain and let $P$ denote the transition probability matrix. $\mathcal{S}=\left\{\mathrm{0,1,}\cdots \mathrm{,}N+1\right\}$ expresses that state space of the Markov chain. And I let $x_i$ denote the probability that the true state of the system is $i\in \mathcal{S}$ . Also, $e_i$ means the $N+2$ dimensional vector that the ith element is 1 and other elements are all zero. The model supposes that an action is selected based on the state vector $x$ instead of the true state i. Thus, I introduce ${\gamma }_{i\theta }$ which means the probability that an outcome $\theta$ is obtained through monitor given that the true state of the system is i, where ${\left(\Gamma \right)}_{i\theta }={\gamma }_{i\theta }$ and $\theta \in \mathcal{M}=\left\{\mathrm{1,}\cdots \mathrm{,}M\right\}$ . To express that the result of repair is uncertain as well as imperfect, I let $q_{ij}\left(h\right)$ denote the repair probability for the system when repair h is selected, where ${\left(Q\left(h\right)\right)}_{ij}=q_{ij}\left(h\right)$ and $h\in \mathcal{H}=\left\{\mathrm{1,}\cdots \mathrm{,}H\right\}$ . That is, $\mathcal{H}$ is a set of options for imperfect repair.

Under these settings, at each time epoch, I can select wait, repair h ( $1\le h\le H$ ), or replacement as follows:

Wait: The system is operated for one period and it isn’t directly inspected after operation. Thus, the system in state i moves to state j with probability $p_{ij}$ after one period with operation. Instead of inspection, I monitor the system and obtain an outcome $\theta$ with probability ${\gamma }_{j\theta }$ .

Imperfect repair: I decided on an option among the H possible imperfect repairs. If repair h is selected as an optimal option, then the true state of the system is identified through inspection before repair and the system in state i is repaired to state j with probability $q_{ij}\left(h\right)$ .

Imperfect repair: The system is replaced by a new and identical one. Thus, after replacement, the system in state i is certainly returned to state 0.

In the next, I assume some costs and probabilities for the model. Hereafter, I consider that increasing means non-decreasing and decreasing means non-increasing, respectively. And $c^{{\rm T}}$ means a transpose of a vector $c$ . Before explanation, two stochastic order relations are defined below.

Definition 1. For a non-negative matrix $B$ on $M\times M$ , $B\in T{P}_2$ means $B$ has a property of totally positive of order 2, that is, $b_{ij}{b}_{kl}\ge b_{kj}{b}_{il}$ holds for $i<k\le M$ and $j<l\le M$ . Similarly, $B\in SI$ means $B$ has a property of usual stochastic order, that is, for any h, ${\displaystyle \underset{j=h}{\overset{M}{\sum }}}{b}_{ij}\le {\displaystyle \underset{j=h}{\overset{M}{\sum }}}{b}_{kj}$ holds when $i\le k$ . Furthermore, for non-negative vectors $a={\left(a_1\mathrm{,}\cdots \mathrm{,}{a}_K\right)}^{{\rm T}}$ and $b={\left(b_1\mathrm{,}\cdots \mathrm{,}{b}_K\right)}^{{\rm T}}$ , if a matrix $\left(\begin{array}{c}{a}^{{\rm T}}\\ b^{{\rm T}}\end{array}\right)\in T{P}_2$ then I write $a\stackrel{T}{\preccurlyeq }b$ . And if ${\displaystyle \underset{j=h}{\overset{K}{\sum }}}{a}_j\le {\displaystyle \underset{j=h}{\overset{K}{\sum }}}{b}_j$ , then I write $a\stackrel{st}{\preccurlyeq }b$ .

For the above stochastic order relations, I provide some important results as a lemma.

Lemma 1.

(i) If $a\stackrel{T}{\preccurlyeq }b$ then $a\stackrel{st}{\preccurlyeq }b$ .

(ii) For any increasing function $g_i$ on i where $g={\left(g_1\mathrm{,}\cdots \mathrm{,}{g}_K\right)}^{{\rm T}}$ , if $a\stackrel{st}{\preccurlyeq }b$ then $a^{{\rm T}}g\le b^{{\rm T}}g$ .

(iii) If $B\in T{P}_2$ then $B\in SI$ .

The details of the stochastic order relations including $T{P}_2$ and SI are explained by Kijima [32] and Shaked and Shanthikumar [33] . Thus, I omit the proof of Lemma 1.

I introduce the following assumptions for the probabilities $P$ , $Q\left(h\right)$ , and $\Gamma$ .

Assumption 1. $P\in T{P}_2$ and $\Gamma \in T{P}_2$ .

Assumption 2. For any $h\in \mathcal{H}$ , $Q\left(h\right)\in T{P}_2$ .

In Assumption 1, the assumption on the transition probability matrix means that as the system deteriorates, it is more likely to move to worse states, and the assumption on $\Gamma$ means that the higher deterioration of the system gives higher outcomes from the monitor. These two assumptions in Assumption 1 have been used in the concerned previous studies to derive the monotone properties. Assumption 2 means that as the system deteriorates, it is less likely to be returned to better states through repair.

When each action is selected, a cost is incurred as follows:

$u_i$ : operating cost for the system in state $i\in \mathcal{S}$ .

$r_i\left(h\right)$ : repair cost for the system in state $i\in \mathcal{S}$ under repair $h\in \mathcal{H}$ .

$c_i$ : replacement cost for the system in state $i\in \mathcal{S}$ .

And I define $u={\left(u_0\mathrm{,}\cdots \mathrm{,}{u}_{N+1}\right)}^{{\rm T}}\mathrm{,}r\left(h\right)={\left(r_0\left(h\right)\mathrm{,}\cdots \mathrm{,}{r}_{N+1}\left(h\right)\right)}^{{\rm T}}\mathrm{,}$ $c={\left(c_0\mathrm{,}\cdots \mathrm{,}{c}_{N+1}\right)}^{{\rm T}}\mathrm{,}{\mathcal{F}}^{N+1}=\left\{f\in {\mathcal{R}}^{N+1}\mathrm{<mo>\; |\; </mo>}{f}_{i-1}\le f_i\left(1\le i\le N+1\right)\right\}\mathrm{,}$ where ${\mathcal{R}}^{N+1}$ means a set of $N+1$ dimensional vectors whose elements are real numbers. For these costs, I introduce the following assumptions.

Assumption 3. For any $h\in \mathcal{H}$ , $u\in {\mathcal{F}}^{N+2}$ , $r\left(h\right)\in {\mathcal{F}}^{N+2}$ , and $c\in {\mathcal{F}}^{N+2}$ .

Assumption 4. For any $h\in \mathcal{H}$ , $u-r\left(h\right)\in {\mathcal{F}}^{N+2}$ , $r\left(h\right)-c\in {\mathcal{F}}^{N+2}$ , and $u-c\in {\mathcal{F}}^{N+2}$ .

Assumption 3 indicates that as the system deteriorates, it is more costly to operate, repair, or replace the system. Also, the first relation of Assumption 4 means that, as the system deteriorates, the merit of repair becomes bigger than that of operation. Similarly, in terms of the latter two relations, the merit of replacement becomes bigger than those of operation and repair with deterioration, respectively. The previous studies have also assumed these relations for the analysis of the POMDP models.

3. Formulation

This section provides the formulation of our problem as a partially observable Markov process model and derives a total expected discounted cost for an unbounded horizon. For the formulation, I define $x={\left(x_0\mathrm{,}{x}_1\mathrm{,}\cdots \mathrm{,}{x}_{N+1}\right)}^{{\rm T}}$ where x is the probability that the true state of the system is i as a state vector. And I let ${\sigma }_j\left(x\mathrm{,}\theta \right)$ denote the probability that the true state is j when the current state vector is $x$ and the outcome is obtained as $\theta$ through monitor after operating the system. And $\beta$ is a discount factor. Then, by using Bayes’ formula, I have

${\sigma }_j\left(x\mathrm{,}\theta \right)=\frac{{\displaystyle {\sum }_i{x}_i{p}_{ij}{\gamma }_{j\theta }}}{{\displaystyle {\sum }_i{\displaystyle {\sum }_j{x}_i{p}_{ij}{\gamma }_{j\theta }}}}\mathrm{,}$ (1)

and I define the jth element of $\sigma \left(x\mathrm{,}\theta \right)$ is ${\sigma }_j\left(x\mathrm{,}\theta \right)$ . Also, I let $\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)$ denote the probability that the outcome is $\theta$ through monitor given that the current state vector is $x$ and I have

$\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)={\displaystyle \underset{i}{\sum }}{x}_i{p}_{ij}{\gamma }_{j\theta }\mathrm{.}$ (2)

Hence I let $W\left(x\right)$ , $R_h\left(x\right)$ , and $Rt\left(x\right)$ denote the optimal expected discounted cost when wait, repair h, and replacement are selected at state vector $x$ , respectively. When $W\left(x\right)$ is expressed as

$W\left(x\right)=u^{{\rm T}}x+\beta {\displaystyle \underset{\theta \in \mathcal{M}}{\sum }}\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)V\left(\sigma \left(x\mathrm{,}\theta \right)\right)$ (3)

Also, I have

$R_h\left(x\right)=r{\left(h\right)}^{{\rm T}}x+\beta {\displaystyle \underset{j}{\sum }}{\left(xQ\left(h\right)\right)}_{j}V\left(e_j\right)\mathrm{,}$ (4)

$Rt\left(x\right)=c^{{\rm T}}x+\beta V\left(e_0\right)\mathrm{,}$ (5)

where ${\left(x^{{\rm T}}Q\left(h\right)\right)}_j={\displaystyle \underset{i}{\sum }}{x}_i{q}_{ij}\left(h\right)\mathrm{.}$

Now I suppose that $V\left(x\right)$ is the optimal expected discounted cost when an optimal action is selected at state vector $x$ and the optimal maintenance policy is adopted afterwards. Then I have

$V\left(x\right)=\min \left[W\left(x\right)\mathrm{,}\underset{1\le h\le H}{\min }{R}_h\left(x\right)\mathrm{,}Rt\left(x\right)\right]\mathrm{.}$ (6)

This problem can be treated as a Markov decision process with a state space $X$ where $X=\left\{x\mathrm{<mo>\; :\; </mo>}{x}_i\ge \mathrm{0,}{\displaystyle \underset{i=0}{\overset{N+1}{\sum }}}{x}_i=1\left(i\in \mathcal{S}\right)\right\}\mathrm{.}$ Thus, by solving Equation (6), I can find the optimal maintenance policy which minimizes the total expected discounted cost for an unbounded horizon. Hereafter, for simplicity, when a function $h\left(x\right)$ satisfies $h\left(x\right)\le h\left(\tilde{x}\right)$ for $x\stackrel{T}{\preccurlyeq }\tilde{x}$ , I describe this relation as $h\left(x\right)$ is increasing $x$ with respect to $T{P}_2$ .

4. Structure of the Optimal Maintenance Policy

In this section, I provide some results on the structure of the optimal maintenance policy. Before proceeding discussion, I summarize several results as the following lemm in preparation.

Lemma 2.

(i) If $x\stackrel{T}{\preccurlyeq }\tilde{x}$ then $x^{{\rm T}}P\stackrel{T}{\preccurlyeq }{\tilde{x}}^{{\rm T}}P$ and $x^{{\rm T}}Q\left(h\right)\stackrel{T}{\preccurlyeq }{\tilde{x}}^{{\rm T}}Q\left(h\right)$ .

(ii) If $x\stackrel{T}{\preccurlyeq }\tilde{x}$ then $x^{{\rm T}}PG\stackrel{T}{\preccurlyeq }{\tilde{x}}^{{\rm T}}PG$ .

(iii) If $x\stackrel{T}{\preccurlyeq }\tilde{x}$ then $\sigma \left(x\mathrm{,}\theta \right)\stackrel{T}{\preccurlyeq }\sigma \left(\tilde{x}\mathrm{,}\theta \right)$ .

(iv) If $\theta <\tilde{\theta }$ then $\sigma \left(x\mathrm{,}\theta \right)\stackrel{T}{\preccurlyeq }\sigma \left(x\mathrm{,}\tilde{\theta }\right)$ .

(v) If a real valued function $f\left(x\mathrm{,}\theta \right)$ is increasing in $\theta$ for any $x\in X$ and is increasing in $x$ with respect to $T{P}_2$ , then ${\displaystyle \underset{\theta }{\sum }}\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)f\left(x\mathrm{,}\theta \right)\le {\displaystyle \underset{\theta }{\sum }}\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)f\left(\tilde{x}\mathrm{,}\theta \right)\mathrm{.}$ The results (i)-(v) are proved by Ohinishi et al. [20] .

4.1. Basic Results

Next, some lemmas which are necessary to derive the main results of this study are developed. In previous studies, similar lemmas were presented and used to derive the monotone properties.

Theorem 1. $V\left(x\right)$ is an increasing function of $x$ in terms of $T{P}_2$ and is concave in $x$ .

Proof. First, I show that the characteristics of $W\left(x\right)$ , $R_h\left(x\right)$ , and $Rt\left(x\right)$ , respectively. $V^n\left(x\right)$ is assumed to be the expected cost when an optimal action is selected for the n-period version of our problem and I use the mathematical induction method, where $V^0\left(x\right)=0$ . Then, I have $V^n\left(x\right)=\min \left[W^n\left(x\right)\mathrm{,}\underset{1\le h\le H}{\min }{R}_h^n\left(x\right)\mathrm{,}R{t}^n\left(x\right)\right]\mathrm{,}$ $W^n\left(x\right)=u^{{\rm T}}x+\beta {\displaystyle \underset{\theta \in \mathcal{M}}{\sum }}\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)V^{n-1}\left(\sigma \left(x\mathrm{,}\theta \right)\right)\mathrm{,}$ $R_h^n\left(x\right)=r{\left(h\right)}^{{\rm T}}x+\beta {\displaystyle \underset{j}{\sum }}{\left(xQ\left(h\right)\right)}_j{V}^{n-1}\left(e_j\right)\mathrm{,}$ $R{t}^n\left(x\right)=c^{{\rm T}}x+\beta V^{n-1}\left(e_0\right)\mathrm{.}$ When $n=1$ , $W^1\left(x\right)$ , $R_h^1\left(x\right)$ , and $R{t}^1\left(x\right)$ are increasing in $x$ from Assumption 3. Thus, $V^1\left(x\right)$ is also increasing in $x$ . Thus, I suppose that $W^n\left(x\right)$ , $R_h^n\left(x\right)$ , $R{t}^n\left(x\right)$ are increasing in $x$ . The first terms of these three functions are increasing in $x$ from Assumption 3. Since the second term of $W\left(x\right)$ is increasing in $x$ from Lemma 2 (v) and the assumption on $V^n\left(x\right)$ , $W^{n+1}\left(x\right)$ is increasing in $x$ . The second term of $R_h^n\left(x\right)$ is a linear function of $x$ and ${\displaystyle \underset{j}{\sum }}{\left(xQ\left(h\right)\right)}_j{V}^{n-1}\left(e_j\right)\le {\displaystyle \underset{j}{\sum }}{\left(\tilde{x}Q\left(h\right)\right)}_j{V}^{n-1}\left(e_j\right)$ for $x\stackrel{T}{\preccurlyeq }\tilde{x}$ from $e_i\stackrel{T}{\preccurlyeq }{e}_j$ for $i\le j$ and Lemma 1 (i)-(ii) and Lemma 2 (i). Thus, $R_h^{n+1}\left(x\right)$ is increasing in $x$ . And $R{t}^{n+1}\left(x\right)$ is increasing in $x$ since the second term is constant, that is, it does not depend upon $x$ .

Second, I consider $V^{n+1}\left(x\right)$ through the results on $W^{n+1}\left(x\right)$ , $R_h^{n+1}\left(x\right)$ , and $R{t}^{n+1}\left(x\right)$ . When I use the argument similar to those of Ohnishi et al. [20] , the second term of $W^{n+1}\left(x\right)$ is increasing and concave in $x$ . Since $R_h^{n+1}\left(x\right)$ and $R{t}^{n+1}\left(x\right)$ are increasing and linear in $x$ , $V^{n+1}\left(x\right)$ is increasing and concave in $x$ . Hence the proof of this theorem completes. □

In addition, I have a result on the difference of the costs as follows.

Lemma 3. For any h, $W\left(x\right)-R_h\left(x\right)$ is concave in $x$ . $W\left(x\right)-Rt\left(x\right)$ and $R_h\left(x\right)-Rt\left(x\right)$ are increasing in $x$ with respect to $T{P}_2$ .

Proof. Since

$\begin{array}{l}W\left(x\right)-R_h\left(x\right)\\ =\left(u-r\left(h\right)\right)x+\beta \left\{{\displaystyle \underset{\theta \in \mathcal{M}}{\sum }}\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)V\left(\sigma \left(x\mathrm{,}\theta \right)\right)-{\displaystyle \underset{j}{\sum }}{\left(xQ\left(h\right)\right)}_{j}V\left(e_j\right)\right\}\mathrm{,}\end{array}$ (7)

the first and the third terms are linear, the second term is concave in $x$ from the proof of Theorem 1. As a result, the difference between the second and the third term is concave in $x$ . Thus. Equation (7) is concave in $x$ for any h. And since

$W\left(x\right)-Rt\left(x\right)=\left(u-c\right)x+\beta \left\{\sigma \left(\theta \mathrm{<mo>\; |\; </mo>}x\right)V\left(\sigma \left(x\mathrm{,}\theta \right)\right)-V\left(e_0\right)\right\}\mathrm{,}$ (8)

the first term is increasing in $x$ from Assumption 4, the second term is also increasing in $x$ from the proof of Theorem 1, and the third term is constant for $x$ . Thus, Equation (8) is increasing in $x$ . And finally, since

$R_h\left(x\right)-Rt\left(x\right)=\left(r\left(h\right)-c\right)x+\beta \left\{{\displaystyle \underset{j}{\sum }}{\left(xQ\left(h\right)\right)}_{j}V\left(e_j\right)-V\left(e_0\right)\right\}\mathrm{,}$ (9)

the first term is increasing in $x$ from Assumption 4, the second term is also increasing in $x$ from the proof of Theorem 1, and the third term is constant for $x$ . Thus, Equation (9) is increasing in $x$ for any h. Hence, the proof of this lemma completes. □

4.2. Monotone Properties

Next, I provide some structural properties of the optimal maintenance policy. For the explanation, I let $D\left(x\right)$ denote an optimal action selected at state vector $x$ . And I define $h^{\ast }\equiv \underset{1\le h\le H}{\arg \min }\left[R_h\left(x\right)\right]\mathrm{,}$ $R_{h^{\ast }}\equiv \underset{1\le h\le H}{\min }\left[R_h\left(x\right)\right]\mathrm{.}$

Then, I have the optimal maintenance policy has the structure expressed by Theorem 2.

Theorem 2. There exist real numbers $\tilde{\alpha }$ , $\hat{\alpha }$ , $\bar{\alpha }$ such that $D\left(x_{\alpha }\right)=(\begin{array}{ll}W\hfill & \left(0\le \alpha <\tilde{\alpha }\right),\hfill \\ R_{h^{\ast }}\hfill & \left(\tilde{\alpha }\le \alpha <\hat{\alpha }\right),\hfill \\ W\hfill & \left(\hat{\alpha }\le \alpha <\bar{\alpha }\right),\hfill \\ R_T\hfill & \left(\bar{\alpha }\le \alpha \le 1\right),\hfill \end{array}$ where $x_{\alpha }=\left(1-\alpha \right)x+\alpha x^{\prime }$ for $x\stackrel{T}{\preccurlyeq }{x}^{\prime }$ and $0\le \tilde{\alpha }\le \hat{\alpha }\le \bar{\alpha }\le 1$ .

Proof. I use Theorem 1 and Lemma 3 for the proof. Since $W\left(x\right)-R_h\left(x\right)$ is concave, $W\left(x\right)$ and $R_h\left(x\right)$ intersect twice at most. Also, since $R_h\left(x\right)-Rt\left(x\right)$ and $W\left(x\right)-Rt\left(x\right)$ are increasing in $x$ , as a result, each pair of $R_h\left(x\right)$ and $Rt\left(x\right)$ and $W\left(x\right)$ and $Rt\left(x\right)$ intersect once at most. Hence the proof of Theorem 2 completes.

Theorem 2 means that the optimal maintenance policy may be classified into 4 regions at most. In particular, since repair includes inspection proposed by Ohnishi et al. [20] if I suppose $q_{ii}\left(h\right)=1$ for any $i\in \mathcal{S}$ and any $h\in \mathcal{H}$ , the structure of the optimal maintenance policy is also similar to that of Ohnishi et al. [20] . Except for Ohnishi et al. [20] , some studies have previously derived monotone properties by introducing several assumptions on costs and probabilities. However, those do not consider that an optimal repair is selected from multiple imperfect repairs whose respective effects are different.

Also, Theorem 2 gives us the following interpretation. In this section, hereafter, I use $x$ instead of $x_{\alpha }$ . When a state vector is less than $\tilde{x}$ or between $\hat{x}$ and $\bar{x}$ with respect to $T{P}_2$ order, I should operate the system, that is, maintenance actions are not necessary. Focused on maintenance actions, if a state vector stays between $\tilde{x}$ and $\hat{x}$ then an optimal imperfect repair is selected and finally, the system should be replaced whenever a state vector exceeds $\bar{x}$ .

Theorem 2 is useful for numerically finding an optimal maintenance policy. However, if the sequence of optimal imperfect repairs has some characteristics when $D\left(x\right)=R_{h^{\ast }}$ , then it would be possible to solve the optimal maintenance problem further efficiently. Thus, by introducing some additional assumptions, I obtain structural properties focused on imperfect repair.

Assumption 5. For any $h,h^{\prime }$ such that $h<h^{\prime }$ , I suppose that,

(i) $r\left(h^{\prime }\right)-r\left(h\right)\in \mathcal{F}$ ,

(ii) $Q\left(h^{\prime }\right)-Q\left(h\right)\in SI$ ,

(iii) $r\left(h\right)-r\left(h^{\prime }\right)\in \mathcal{F}$ ,

(iv) $Q\left(h\right)-Q\left(h^{\prime }\right)\in SI$ .

Assumption 5-(i) and 5-(iii), and Assumptions 5-(ii) and 5-(iv) do not hold together, respectively. Then, Assumptions 5-(i) indicates that it is less costly to select repair h compared with repair h' and Assumption 5-(ii) indicates that the system is more likely to be returned to better states through repair h compared with repair h', as the system deteriorates. Thus, Assumptions 5-(i) and 5-(ii) mean that the merit of repair h becomes bigger than that of repair h’ with deterioration of the system. Also, Assumptions 5-(iii) and 5-(iv) have the contrary interpretation.

Under some of the assumptions given by Assumption 5, I have a property on the relation of the optimal repairs.

Theorem 3. I suppose that $D\left(x_l\right)=R_{h_l}$ and $D\left(x_u\right)=R_{h_u}$ for $x_l\stackrel{T}{\preccurlyeq }{x}_u$ . If Assumptions 5-(i) and 5-(ii) hold then $h_l\ge h_u$ . And if Assumptions 5-(iii) and (iv) hold then $h_l\le h_u$ .

Proof. I define that, for $x_1\stackrel{T}{\preccurlyeq }{x}_2$ and $h_1\le h_2$ , $\begin{array}{c}\Delta R_{h_1\mathrm{,}{h}_2}\left(x\right)\equiv R_{h_1}\left(x\right)-R_{h_2}\left(x\right)\\ =\left(r\left(h_1\right)-r\left(h_2\right)\right)x+\beta {\displaystyle \underset{j}{\sum }}{\left[x\left\{Q\left(h_1\right)-Q\left(h_2\right)\right\}\right]}_{j}V\left(e_j\right)\mathrm{,}\end{array}$ $\begin{array}{c}{\Delta }^2{R}_{h_1\mathrm{,}{h}_2}\left(x_2\mathrm{,}{x}_1\right)\equiv \Delta R_{h_1\mathrm{,}{h}_2}\left(x_2\right)-\Delta R_{h_1\mathrm{,}{h}_2}\left(x_1\right)\\ =\left\{r\left(h_1\right)-r\left(h_2\right)\right\}\left(x_2-x_1\right)\\ +\beta {\displaystyle \underset{j}{\sum }}{\left[\left(x_2-x_1\right)\left\{Q\left(h_1\right)-Q\left(h_2\right)\right\}\right]}_{j}V\left(e_j\right)\mathrm{.}\end{array}$ Also, I suppose that $D\left(x_2\right)=R_{h^{\ast }}\text{and}D\left(x_1\right)=R_{h^{\ast }}\mathrm{.}$ If Assumptions 5-(i) and 5-(ii) hold then ${\Delta }^2{R}_{h_1\mathrm{,}{h}_2}\left(x_2\mathrm{,}{x}_1\right)\le \mathrm{0,}$ and this means that there exists a vector $x_{C_1}$ which satisfies $\Delta R_{h_1\mathrm{,}{h}_2}\left(x\right)>0\text{for}x\stackrel{T}{\prec }{x}_{C_1}\mathrm{,}$ $\Delta R_{h_1\mathrm{,}{h}_2}\left(x\right)\le 0\text{for}x\stackrel{T}{\succcurlyeq }{x}_{C_1}\mathrm{.}$ Hence, if $D\left({\tilde{x}}_1\right)=R_{h_2}$ and $D\left({\tilde{x}}_2\right)=R_{h_1}$ then ${\tilde{x}}_1\stackrel{T}{\preccurlyeq }{\tilde{x}}_2$ since I suppose that $h_1\le h_2$ . And if Assumptions 5-(iii) and 5-(iv) hold then ${\Delta }^2{R}_{h_1\mathrm{,}{h}_2}\left(x_2\mathrm{,}{x}_1\right)\ge 0.$ This indicates that there exists a vector $x_{C_2}$ which satisfies $\Delta R_{h_1\mathrm{,}{h}_2}\left(x\right)\le 0\text{for}x\stackrel{T}{\prec }{x}_{C_2}\mathrm{,}$ $\Delta R_{h_1\mathrm{,}{h}_2}\left(x\right)>0\text{for}x\stackrel{T}{\succcurlyeq }{x}_{C_2}\mathrm{.}$ Thus, if $D\left({\tilde{x}}_1\right)=R_{h_2}$ and $D\left({\tilde{x}}_2\right)=R_{h_1}$ then ${\tilde{x}}_1\stackrel{T}{\succcurlyeq }{\tilde{x}}_2$ Hence, the proof of this theorem completes.

Theorem 3-(i) means that I should select larger numbered repairs in lower state vectors in terms of $T{P}_2$ and Theorem 3-(ii) has the contrary interpretation. This theorem is also useful for finding an optimal maintenance policy more efficiently. For example, I suppose that there are H options on imperfect repair and $D\left(x\right)=R_{h^{\ast }}$ for $x\in \left[\tilde{x}\mathrm{,}\hat{x}\right)$ in terms of $T{P}_2$ In this case, Theorem 3 tells us that, under Assumption 5, the number of options on imperfect repair gradually reduces from H as a state vector in $\left[\tilde{x}\mathrm{,}\hat{x}\right)$ increases, that is, the system deteriorates.

5. Discussion

In this section, I explain the significance of Theorems 2 and 3 to find an optimal maintenance policy. Generally, I know that monotone properties are available to find an optimal maintenance policy numerically.

Now this section supposes that the system has two states as good (0) and bad (1) and there are three options for imperfect repair ( $\mathcal{H}=\left\{\mathrm{1,2,3}\right\}$ ). And the state vector $x$ becomes a scalar x which means a probability that the system stays in a bad state. In this case, since I have to decide on an optimal action $D\left(x\right)$ for $x\in \left[\mathrm{0,1}\right]$ , our problem has an infinite state space. However, if Theorem 2 holds, that is, I can know the problem satisfies Assumptions 1, 2, 3 and 4 in advance, then I may find 3 real numbers $\tilde{\alpha }$ , $\hat{\alpha }$ , $\bar{\alpha }$ in Theorem 2. Then, I first compare $W\left(x\right)$ and $R_{h^{\ast }}\left(x\right)$ for $x\in \left[\mathrm{0,1}\right]$ and find real numbers $\tilde{\alpha }$ and $\hat{\alpha }$ such that $W\left(x\right)\le R_{h^{\ast }}\left(x\right)\text{for}x\in \left[0,\tilde{\alpha }\right),$ $W\left(x\right)\le R_{h^{\ast }}\left(x\right)\text{for}x\in \left[\hat{\alpha },1\right),$ $W\left(x\right)>R_{h^{\ast }}\left(x\right)\text{for}x\in \left[\tilde{\alpha },\hat{\alpha }\right).$ Second, similarly, I compare $W\left(x\right)$ and $Rt\left(x\right)$ for $x\in \left[\hat{\alpha }\mathrm{,1}\right]$ and find $\bar{\alpha }$ such that $W\left(x\right)>Rt\left(x\right)\text{for}x\in \left[\bar{\alpha }\mathrm{,1}\right]\mathrm{,}$ $W\left(x\right)\le Rt\left(x\right)\text{for}x\in \left[\hat{\alpha }\mathrm{,}\bar{\alpha }\right)$ , since $W\left(x\right)\le R_{h^{\ast }}\left(x\right)$ for $x\in \left[\hat{\alpha }\mathrm{,1}\right)$ . Thus, Theorem 2 can reduce the computational effort for finding an optimal maintenance policy numerically. This usefulness is conserved for more than two states.

To find the optimal maintenance policy in the above, I need obtain $R_{h^{\ast }}\left(x\right)$ , that is, the comparison of $R_h\left(x\right)$ for $h\in \mathcal{H}$ arises in this problem. Then Theorem 3 is useful to address the problem. Since I have 3 options for imperfect repair, if the costs and the probabilities satisfy Assumptions 5-(iii) and 5-(iv) then Theorem 3-(ii) holds. In this case, comparing $R_1\left(x\right)$ with $W\left(x\right)$ , I find ${\tilde{\alpha }}_1$ such that $R_1\left(x\right)\le W\left(x\right)$ for $x\in \left[\mathrm{0,1}\right]$ as a first step. In the next, I find ${\tilde{\alpha }}_2$ that $D\left(x\right)=R_2$ , that is, $R_2\left(x\right)<R_1\left(x\right)$ for $x\in \left[{\tilde{\alpha }}_1\mathrm{,}\hat{\alpha }\right]$ through comparison of $R_1\left(x\right)$ and $R_2\left(x\right)$ . And finaly, I find ${\tilde{\alpha }}_3$ that $R_3\left(x\right)<R_2\left(x\right)$ for $x\in \left[{\tilde{\alpha }}_2\mathrm{,1}\right]$ through comparison of $R_2\left(x\right)$ and $R_3\left(x\right)$ . As a result of this procedure, I can find the real numbers ${\tilde{\alpha }}_1$ , ${\tilde{\alpha }}_2$ , ${\tilde{\alpha }}_3$ , $\hat{\alpha }$ and $\bar{\alpha }$ , and determine the optimal maintenance policy that satisfy ${\tilde{\alpha }}_1\le {\tilde{\alpha }}_2\le {\tilde{\alpha }}_3\le \hat{\alpha }\le \bar{\alpha }$ . On the other hand, if the costs and the probabilities satisfy Assumptions 5-(i) and 5-(ii) then I may use Theorem 3-(i) to find an optimal maintenance policy where ${\tilde{\alpha }}_3\le {\tilde{\alpha }}_2\le {\tilde{\alpha }}_1\le \hat{\alpha }\le \bar{\alpha }$ .

Even if the number of states is more than 2, I can similarly use Theorems 2 and 3. However, the computational effort becomes much harder with larger states.

6. Conclusions

In this paper, I considered a system whose deterioration follows a discrete-time and discrete-state Markov chain under incomplete information on the true state and constructed a POMDP model for an optimal maintenance problem. I have several options for repair which has different recovery effects on the system in addition to replacement as maintenance actions. Then, I derived sufficient conditions that the monotone property holds as per Theorem 2. As described in Section 4.2, since this theorem is a generalization of some previous results and is useful for efficiently solving the optimal maintenance problem since the optimal maintenance policy may be classified into 4 regions at most.

Furthermore, I established the sequence of optimal repairs under several assumptions in Theorem 3. Since the previous studies on POMDP models for optimal maintenance problems do not focus on the concept of multiple imperfect repairs that the repair probabilities are different, Theorem 3 is a significant property in this area even if the assumptions are so strict. In particular, the feature that the number of options on imperfect repair gradually reduces with the increase of a state vector in terms of $T{P}_2$ is so interesting.

I can check whether the costs for the respective actions and the transition and repair probabilities satisfy the assumptions for Theorems 2 and 3 before solving an optimal maintenance problem. Thus, as discussed in Section 5, the theorems obtained in this study are available to reduce the computational time since the number of regions of the optimal maintenance policy can be limited.

However, I do not provide quantitative analysis through numerical experiments. While there exist algorithms for POMDP models (see e.g. Monahan [34] , Guo and Lian [35] ), as stated by the previous studies, POMDP models with many states have an aspect of time-consuming computation. Thus, future works are to construct an efficient algorithm for solving our problem under the assumptions for the monotone properties and to obtain some characteristics of the optimal maintenance policy through numerical analysis. Also, I need to consider how to relax the sufficient conditions for the theorems. In particular, four conditions in Assumption 5, which are used for deriving Theorem 3 and are originally proposed in this study, are so strict that it would be difficult for them to be satisfied in real situations. Hence, it is important to construct a numerical method for addressing the optimal maintenance problems without Assumption 5.

Acknowledgements

This work was supported by JSPS KAKENHI Grant Number JP20K04989.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Osaki, S. (2001) Stochastic Models in Reliability and Maintenance. Springer, Berlin. https://doi.org/10.1007/978-3-540-24808-8
[2]	Cho, D.I. and Parlar, M. (1991) A Survey of Maintenance Models for Multi-Unit Systems. European Journal of Operational Research, 51, 1-23. https://doi.org/10.1016/0377-2217(91)90141-H
[3]	Dekker, R. (1996) Applications of Maintenance Optimization Models: A Review and Analysis. Reliability Engineering and System Safety, 51, 229-240. https://doi.org/10.1016/0951-8320(95)00076-3
[4]	Wang, H. (2002) A Survey of Maintenance Policies of Deteriorating Systems European. Journal of Operational Research, 139, 469-489. https://doi.org/10.1016/S0377-2217(01)00197-7
[5]	Jardine, A., Lin, D. and Banjevic, D. (2006) A Review on Machinery Diagnostics and Prognostics Implementing Condition-Based Maintenance. Mechanical Systems and Signal Processing, 20, 1483-1510. https://doi.org/10.1016/j.ymssp.2005.09.012
[6]	Olde Keizer, M.C.A., Flapper, S.D.P. and Teunter, R.H. (2017) Condition-Based Maintenance Policies for Systems with Multiple Dependent Components: A Review. European Journal of Operational Research, 261, 405-420. https://doi.org/10.1016/j.ejor.2017.02.044
[7]	Alaswad, S. and Xiang, Y. (2017) A Review on Condition-Based Maintenance Optimization Models for Stochastically Deteriorating System. Reliability Engineering and System Safety, 157, 54-63. https://doi.org/10.1016/j.ress.2016.08.009
[8]	Derman, C. (1963) On Optimal Replacement Rules When Changes of States Are Markovian. In: Bellman, R., Ed., Mathematical Optimization Techniques, University of California Press, Berkley, 201-210. https://doi.org/10.1525/9780520319875-011
[9]	Douer, N. and Yechiali, U. (1994) Optimal Repair and Replacement in Markovian Systems. Communications in Statistics. Stochastic Models, 10, 253-270. https://doi.org/10.1080/15326349408807295
[10]	Hopp, W. and Wu, A. (1990) Machine Maintenance with Multiple Maintenance Actions. IIE Transactions, 22, 226-233. https://doi.org/10.1080/07408179008964177
[11]	Kurt, M. and Kharoufeh, J.P. (2010) Monotone Optimal Replacement Policies for a Markovian Deteriorating System in Controllable Environment. Operations Research Letters, 38, 273-279. https://doi.org/10.1016/j.orl.2010.03.001
[12]	Kurt, M. and Kharoufeh, J.P. (2010) Optimally Maintaining a Markovian Deteriorating System with Limited Imperfect Repairs. European Journal of Operational Research, 205, 368-380. https://doi.org/10.1016/j.ejor.2010.01.009
[13]	Tamura, N. (2011) An Optimal Inspection Policy for a Markovian Deteriorating System with Stochastically Decreasing Lifetime. International Journal of Reliability Quality and Operations Management, 2, 13-28.
[14]	Lam, C.T. and Yeh, R.H. (1994) Optimal Maintenance-Policies for Deteriorating Systems under Various Maintenance Strategies. IEEE Transactions on Reliability, 43, 423-430. https://doi.org/10.1109/24.326439
[15]	Lam, C.T. and Yeh, R.H. (1994) Optimal Replacement Policies for Multistate Deteriorating Systems. Naval Research Logistics, 41, 303-315. https://doi.org/10.1002/1520-6750(199404)41:3<303::AID-NAV3220410302>3.0.CO;2-2
[16]	Lam, C.T. and Yeh, R.H. (1994) Comparison of Sequential and Continuous Inspection Strategies for Deteriorating Systems. Advances in Applied Probability, 26, 423-435. https://doi.org/10.2307/1427444
[17]	Yeh, R.H. (1996) Optimal Inspection and Replacement Policies for Multi-State Deteriorating Systems. European Journal of Operational Research, 96, 248-259. https://doi.org/10.1016/S0377-2217(96)00077-X
[18]	Yeh, R.H. (1997) State-Age-Dependent Maintenance Policies for Deteriorating Systems with Erlang Sojourn Time Distributions. Reliability Engineering and System Safety, 58, 55-60. https://doi.org/10.1016/S0951-8320(97)00049-5
[19]	Ross, S.M. (1971) Quality Control under Markovian Deterioration. Management Science, 17, 587-596. https://doi.org/10.1287/mnsc.17.9.587
[20]	Ohnishi, M., Kawai, H. and Mine, H. (1986) An Optimal Inspection and Replacement Policy under Incomplete State Information. European Journal of Operational Research, 27, 117-128. https://doi.org/10.1016/S0377-2217(86)80014-5
[21]	Grosfeld-Nir, A. (1996) A Two-State Partially Observable Markov Decision Process with Uniformly Distributed Observation. Operations Research, 44, 458-463. https://doi.org/10.1287/opre.44.3.458
[22]	Grosfeld-Nir, A. (2007) Control Limits for Two-State Partially Observable Markov Decision Processes. European Journal of Operational Research, 182, 300-304. https://doi.org/10.1016/j.ejor.2006.08.033
[23]	Chen, M., Fan, H., Hu, C. and Zhou, D. (2014) Maintaining Partially Observed Systems with Imperfect Observation and Resource Constraint. IEEE Transactions on Reliability, 63, 881-890. https://doi.org/10.1109/TR.2014.2337792
[24]	Srinivasan, R. and Parlikad, A.K. (2014) Semi-Markov Decision Process with Partial Information for Maintenance Decisions. IEEE Transactions on Reliability, 63, 891-898. https://doi.org/10.1109/TR.2014.2338811
[25]	Oosterom, C., Peng, H. and Houtm, G. (2017) Maintenance Optimization for a Markovian Deteriorating System with Population Heterogeneity. IISE Transactions, 49, 96-109. https://doi.org/10.1080/0740817X.2016.1205239
[26]	Kivanc, I., Ozgur-Unluakin, D. and Bilgic, T. (2022) Maintenance Policy Analysis of the Regenerative Air Heater System Using Factored POMDPs. Reliability Engineering and System Safety, 219, Article ID: 108195. https://doi.org/10.1016/j.ress.2021.108195
[27]	Ohnishi, M., Morioka, T. and Ibaraki, T. (1994) Optimal Minimal-Repair and Replacement Problem of Discrete-Time Markovian Deterioration System under Incomplete State Information. Computers and Industrial Engineering, 27, 409-412. https://doi.org/10.1016/0360-8352(94)90321-2
[28]	Pham, H. and Wang, H. (1996) Imperfect Maintenance. European Journal of Operational Research, 94, 425-438. https://doi.org/10.1016/S0377-2217(96)00099-9
[29]	Ivy, J.S. and Pollock, S.M. (2005) Marginally Monotonic Maintenance Policies for a Multi-State Deteriorating Machine with Probabilistic Monitoring, and Silent Failures. IEEE Transactions on Reliability, 54, 489-497. https://doi.org/10.1109/TR.2005.853443
[30]	Tamura, N., Yuge, T. and Yanagi, S. (2011) Monotone Properties of Optimal Maintenance Policy for Two-State Partially Observable Markov Decision Process Model with Multiple Observations. International Journal of Operations Research, 7, 23-34.
[31]	Fan, H., Xu, Z. and Chen, S.W. (2015) Optimally Maintaining a Multi-State System with Limited Imperfect Preventive Repairs. International Journal of Systems Science, 46, 1729-1740. https://doi.org/10.1080/00207721.2013.828799
[32]	Kijima, M. (1997) Markov Processes for Stochastic Modeling. Chapman & Hall, New York. https://doi.org/10.1007/978-1-4899-3132-0
[33]	Shaked, M. and Shanthikumar, J.G. (2007) Stochastic Orders. Springer, New York. https://doi.org/10.1007/978-0-387-34675-5
[34]	Monahan, G. (1982) A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms. Management Science, 28, 1-111. https://doi.org/10.1287/mnsc.28.1.1
[35]	Guo, C. and Liang, Z. (2022) A Predictive Markov Decision Process for Optimizing Inspection and Maintenance Strategies of Partially Observable Multi-State Systems. Reliability Engineering and System Safety, 226, Article ID: 108683. https://doi.org/10.1016/j.ress.2022.108683