A numerical study of Markov decision process algorithms for multi-component replacement problems

Research output: Contribution to journalJournal articleResearchpeer-review

34 Downloads (Pure)


We present a unified modeling framework for Time-Based Maintenance (TBM) and ConditionBased Maintenance (CBM) for optimization of replacements in multi-component systems. The considered system has a K-out-of-N reliability structure, and components deteriorate according to a multivariate gamma process with L´evy copula dependence. The TBM and CBM models are formulated as Markov Decision Processes (MDPs), and optimal policies are found using dynamic programming. Solving the CBM model requires that the continuous deterioration process is discretized. We therefore investigate the discretization level required for obtaining a near-optimal policy. Our results indicate that a coarser discretization level than previously suggested in the literature is adequate, indicating that dynamic programming is a feasible approach for optimization in multi-component systems. We further demonstrate this through empirical results for the size limit of the MDP models when solved with an optimized implementation of modified policy iteration. The TBM model can generally be solved with more components than the CBM model, since the former has a sparser state transition structure. In the special case of independent component deterioration, transition probabilities can be calculated efficiently at runtime. This reduces the memory requirements substantially. For this case, we also achieved a tenfold speedup when using ten processors in a parallel implementation of algorithm. Altogether, our results show that the computational requirements for systems with independent component deterioration increase at a slower rate than for systems with stochastic dependence.
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number3
Pages (from-to)94–102
Number of pages12
Publication statusPublished - 2022


  • Maintenance
  • Dynamic Programming
  • Multi-component system
  • Markov decision process
  • Numerical study


Dive into the research topics of 'A numerical study of Markov decision process algorithms for multi-component replacement problems'. Together they form a unique fingerprint.

Cite this