Skip to main content
SpringerLink
Log in

Performance Analysis for Controlled Semi-Markov Systems with Application to Maintenance

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper concerns with the performance analysis for controlled semi-Markov systems in Borel state and action spaces. The performability of the system is defined as the probability that the system reaches a prescribed reward level during a first passage time to some target set. Under mild conditions, we develop a value iteration algorithm for computing the optimal value, and establish the existence of optimal policies with the maximal performability. Our main results are applied to a maintenance problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Beaudry, M.D.: Performance related reliability measures for computing systems. IEEE Trans. Comput. C-27, 540–547 (1978)

    Article  Google Scholar 

  2. Ciardo, G., Marie, R.A., Sericola, B., Trivedi, K.S.: Performability analysis using semi-Markov reward processes. IEEE Trans. Comput. C-39, 1251–1264 (1990)

    Article  Google Scholar 

  3. Goyal, A., Tantawi, A.N.: Evaluation of performability for degradable computer systems. IEEE Trans. Comput. C-36, 738–744 (1987)

    Article  Google Scholar 

  4. Iyer, B.R., Donatiello, L., Heidelberger, P.: Analysis of performability for stochastic models of fault-tolerant systems. IEEE Trans. Comput. C-35, 902–907 (1986)

    Article  Google Scholar 

  5. Meyer, J.F.: On evaluating the performability of degradable computing systems. IEEE Trans. Comput. C-29, 720–731 (1980)

    Article  Google Scholar 

  6. Smith, R.M., Trivedi, K.S., Ramesh, A.V.: Performability analysis: measures, an algorithm, and a case study. IEEE Trans. Comput. C-37, 406–417 (1988)

    Article  Google Scholar 

  7. Limnios, N., Oprisan, J.: A unified approach for reliability and performability evaluation of semi-Markov systems. Appl. Stoch. Models Bus. Ind. 15, 353–368 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  8. Limnios, N., Oprisan, J.: Semi-Markov Processes and Reliability. Birkhäuser, Boston (2001)

    MATH  Google Scholar 

  9. Cekyay, B., Ozekici, S.: Mean time to failure and availability of semi-Markov missions with maximal repair. Eur. J. Oper. Res. 207, 1442–1454 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  10. Love, C.E., Zhang, Z.G., Zitron, M.A., Guo, R.: A discrete semi-Markov decision model to determine the optimal repair/replacement policy under general repairs. Eur. J. Oper. Res. 125, 398–409 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  11. Mamer, J.W.: Successive approximations for finite horizon semi-Markov decision processes with application to asset liquidation. Oper. Res. 34, 638–644 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  12. Silvestrov, D., Stenberg, F.: A pricing process with stochastic volatility controlled by a semi-Markov process. Commun. Stat., Theory Methods 33, 591–608 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  13. Singh, S.S., Tadic, V.B., Doucet, A.: A policy gradient method for semi-Markov decision processes with application to call admission control. Eur. J. Oper. Res. 178, 808–818 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  14. Walczak, D., Brumelle, S.: Semi-Markov information model for revenue management and dynamic pricing. OR Spektrum 29, 61–83 (2007)

    MATH  MathSciNet  Google Scholar 

  15. Yadavalli, V.S.S., Natarajan, R.: A semi-Markov model of a manpower system. Stoch. Anal. Appl. 19, 1077–1086 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  16. Bhattacharya, R.N., Majumdar, M.: Controlled semi-Markov models—the discounted case. J. Stat. Plan. Inference 21, 365–381 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  17. Cao, X.R.: Semi-Markov decision problems and performance sensitivity analysis. IEEE Trans. Autom. Control 48, 758–769 (2003)

    Article  Google Scholar 

  18. Glazebrook, K.D., Bailey, M.P., Whitaker, L.R.: Cost rate heuristics for semi-Markov decision processes. J. Appl. Probab. 29, 633–644 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  19. Hernandez-Lerma, O.: Nonstationary value-iteration and adaptive control of discounted semi-Markov processes. J. Math. Anal. Appl. 112, 435–445 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  20. Hudak, D., Nollau, V.: Approximation solution and suboptimality for discounted semi-Markov decision problems with countable state space. Optimization 53, 339–353 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  21. Wakuta, K.: Arbitrary state semi-Markov decision processes with unbounded rewards. Optimization 18, 447–454 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  22. Beutler, F.J., Ross, K.W.: Time-average optimal constrained semi-Markov decision processes. Adv. Appl. Probab. 18, 341–359 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  23. Bhattacharya, R.N., Majumdar, M.: Controlled semi-Markov models under long-run average rewards. J. Stat. Plan. Inference 22, 223–242 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  24. Dekker, R., Hordijk, A.: Denumerable semi-Markov decision chains with small interest rates. Ann. Oper. Res. 28, 185–211 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  25. Rosberg, Z.: Semi-Markov decision processes with polynomial reward. J. Appl. Probab. 19, 301–309 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  26. Schal, M.: On the second optimality equation for semi-Markov decision models. Math. Oper. Res. 17, 470–486 (1992)

    Article  MathSciNet  Google Scholar 

  27. Ghosh, M.K., Goswami, A.: Partially observable semi-Markov games with discounted payoff. Stoch. Anal. Appl. 24, 1035–1059 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  28. Herzberg, M., Yechiali, U.: Criteria for selecting the relaxation factor of the value iteration algorithm for undiscounted Markov and semi-Markov decision processes. Oper. Res. Lett. 10, 193–202 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  29. Jaskiewicz, A.: Zero-sum ergodic semi-Markov games with weakly continuous transition probabilities. J. Optim. Theory Appl. 141, 321–347 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  30. Klabjan, D., Adelman, D.: An infinite-dimensional linear programming algorithm for deterministic semi-Markov decision processes on Borel spaces. Math. Oper. Res. 32, 528–550 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  31. Liu, K.: Weighted semi-Markov decision processes and their perturbations. Information 8, 785–800 (2005)

    MathSciNet  Google Scholar 

  32. Novak, J.: Linear programming in vector criterion Markov and semi-Markov decision processes. Optimization 20, 651–670 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  33. Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)

    MATH  Google Scholar 

  34. Bertsekas, D.P., Shreve, S.E.: Stochastic Optimal Control: The Discrete-Time Case. Athena Scientific, Belmont (1996)

    Google Scholar 

  35. Hernández-Lerma, O., Lasserre, J.B.: Discrete-Time Markov Control Processes. Springer, New York (1996)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Computational Science, Sun Yat-Sen University, Guangzhou, 510275, China

    Yonghui Huang & Xianping Guo

  2. Guangdong Province Key Laboratory of Computational Science, Guangzhou, 510275, China

    Yonghui Huang & Xianping Guo

  3. Department of Statistics, Chinese University of Hong Kong, Hong Kong, China

    Xinyuan Song

Authors
  1. Yonghui Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xianping Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xinyuan Song
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xianping Guo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huang, Y., Guo, X. & Song, X. Performance Analysis for Controlled Semi-Markov Systems with Application to Maintenance. J Optim Theory Appl 150, 395–415 (2011). https://doi.org/10.1007/s10957-011-9813-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-011-9813-7

Keywords

Search

Navigation