IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v58y2010i4-part-1p918-932.html
   My bibliography  Save this article

An Approximation Approach for the Deviation Matrix of Continuous-Time Markov Processes with Application to Markov Decision Theory

Author

Listed:
  • Nicole Leder

    (Department of Mathematics, University of Hamburg, Hamburg 20146, Germany)

  • Bernd Heidergott

    (Department of Econometrics and Operations Research, and Tinbergen Institute, Vrije Universiteit Amsterdam, Amsterdam 1081 HV, The Netherlands)

  • Arie Hordijk

    (Mathematical Institute, Leiden University, Leiden 2300 RA, The Netherlands)

Abstract

We present an update formula that allows the expression of the deviation matrix of a continuous-time Markov process with denumerable state space having generator matrix Q * through a continuous-time Markov process with generator matrix Q . We show that under suitable stability conditions the algorithm converges at a geometric rate. By applying the concept to three different examples, namely, the M/M/1 queue with vacations, the M/G/1 queue, and a tandem network, we illustrate the broad applicability of our approach. For a problem in admission control, we apply our approximation algorithm to Markov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm.

Suggested Citation

  • Nicole Leder & Bernd Heidergott & Arie Hordijk, 2010. "An Approximation Approach for the Deviation Matrix of Continuous-Time Markov Processes with Application to Markov Decision Theory," Operations Research, INFORMS, vol. 58(4-part-1), pages 918-932, August.
    • Handle: RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:918-932
    DOI: 10.1287/opre.1090.0786
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1090.0786
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1090.0786?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. E. Altman & A. Hordijk & F. M. Spieksma, 1997. "Contraction Conditions for Average and (alpha)-Discount Optimality in Countable State Markov Games with Unbounded Rewards," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 588-618, August.
    2. Richard F. Serfozo, 1979. "Technical Note—An Equivalence Between Continuous and Discrete Time Markov Decision Processes," Operations Research, INFORMS, vol. 27(3), pages 616-620, June.
    3. Arie Hordijk & Alexander A. Yushkevich, 1999. "Blackwell optimality in the class of all policies in Markov decision chains with a Borel state space and unbounded rewards," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 50(3), pages 421-448, December.
    4. Rommert Dekker & Arie Hordijk, 1992. "Recurrence Conditions for Average and Blackwell Optimality in Denumerable State Markov Decision Chains," Mathematics of Operations Research, INFORMS, vol. 17(2), pages 271-289, May.
    5. Xianping Guo, 2007. "Continuous-Time Markov Decision Processes with Discounted Rewards: The Case of Polish Spaces," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 73-87, February.
    6. Arie Hordijk & Alexander A. Yushkevich, 1999. "Blackwell optimality in the class of stationary policies in Markov decision chains with a Borel state space and unbounded rewards," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 49(1), pages 1-39, March.
    7. R. Dekker & A. Hordijk & F. M. Spieksma, 1994. "On the Relation Between Recurrence and Ergodicity Properties in Denumerable Markov Decision Chains," Mathematics of Operations Research, INFORMS, vol. 19(3), pages 539-559, August.
    8. Chao, Xiuli & Zhao, Yiqiang Q., 1998. "Analysis of multi-server queues with station and server vacations," European Journal of Operational Research, Elsevier, vol. 110(2), pages 392-406, October.
    9. Rommert Dekker & Arie Hordijk, 1988. "Average, Sensitive and Blackwell Optimal Policies in Denumerable Markov Decision Chains with Unbounded Rewards," Mathematics of Operations Research, INFORMS, vol. 13(3), pages 395-420, August.
    10. Lawrence Brown & Noah Gans & Avishai Mandelbaum & Anat Sakov & Haipeng Shen & Sergey Zeltyn & Linda Zhao, 2005. "Statistical Analysis of a Telephone Call Center: A Queueing-Science Perspective," Journal of the American Statistical Association, American Statistical Association, vol. 100, pages 36-50, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Abbas, K. & Heidergott, B.F. & Aissani, D., 2011. "A Taylor series expansion approach to the functional approximation of finite queues," Serie Research Memoranda 0049, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dwi Ertiningsih & Sandjai Bhulai & Flora Spieksma, 2018. "A novel use of value iteration for deriving bounds for threshold and switching curve optimal policies," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(8), pages 638-659, December.
    2. Bernd Heidergott & Arie Hordijk & Heinz Weisshaupt, 2006. "Measure-Valued Differentiation for Stationary Markov Chains," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 154-172, February.
    3. Bernd Heidergott & Arie Hordijk & Haralambie Leahu, 2009. "Strong bounds on perturbations," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 70(1), pages 99-127, August.
    4. Bernd Heidergott & Haralambie Leahu, 2010. "Weak Differentiability of Product Measures," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 27-51, February.
    5. Heidergott, B. & Leahu, H., 2008. "Differentiability of Product Measures," Serie Research Memoranda 0005, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    6. F. M. Spieksma, 2016. "Kolmogorov forward equation and explosiveness in countable state Markov processes," Annals of Operations Research, Springer, vol. 241(1), pages 3-22, June.
    7. Yu Zhang & Vidyadhar G. Kulkarni, 2017. "Two-day appointment scheduling with patient preferences and geometric arrivals," Queueing Systems: Theory and Applications, Springer, vol. 85(1), pages 173-209, February.
    8. Q. Zhu, 2007. "Sample-path optimality and variance-maximization for Markov decision processes," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 65(3), pages 519-538, June.
    9. Alexey Piunovskiy & Yi Zhang, 2012. "The Transformation Method for Continuous-Time Markov Decision Processes," Journal of Optimization Theory and Applications, Springer, vol. 154(2), pages 691-712, August.
    10. Arnab Basu & Mrinal K. Ghosh, 2018. "Nonzero-Sum Risk-Sensitive Stochastic Games on a Countable State Space," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 516-532, May.
    11. Eugene A. Feinberg & Jefferson Huang, 2019. "On the reduction of total‐cost and average‐cost MDPs to discounted MDPs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(1), pages 38-56, February.
    12. De Munck, Thomas & Chevalier, Philippe & Tancrez, Jean-Sébastien, 2023. "Managing priorities on on-demand service platforms with waiting time differentiation," International Journal of Production Economics, Elsevier, vol. 266(C).
    13. Avishai Mandelbaum & Petar Momčilović, 2017. "Personalized queues: the customer view, via a fluid model of serving least-patient first," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 23-53, October.
    14. Barrow, Devon & Kourentzes, Nikolaos, 2018. "The impact of special days in call arrivals forecasting: A neural network approach to modelling special days," European Journal of Operational Research, Elsevier, vol. 264(3), pages 967-977.
    15. Rouba Ibrahim & Pierre L'Ecuyer, 2013. "Forecasting Call Center Arrivals: Fixed-Effects, Mixed-Effects, and Bivariate Models," Manufacturing & Service Operations Management, INFORMS, vol. 15(1), pages 72-85, May.
    16. Nabil Channouf & Pierre L’Ecuyer & Armann Ingolfsson & Athanassios Avramidis, 2007. "The application of forecasting techniques to modeling emergency medical system calls in Calgary, Alberta," Health Care Management Science, Springer, vol. 10(1), pages 25-45, February.
    17. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.
    18. Ward Whitt, 2007. "What you should know about queueing models to set staffing requirements in service systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(5), pages 476-484, August.
    19. Rouba Ibrahim & Mor Armony & Achal Bassamboo, 2017. "Does the Past Predict the Future? The Case of Delay Announcements in Service Systems," Management Science, INFORMS, vol. 63(6), pages 1762-1780, June.
    20. Rouba Ibrahim & Ward Whitt, 2011. "Wait-Time Predictors for Customer Service Systems with Time-Varying Demand and Capacity," Operations Research, INFORMS, vol. 59(5), pages 1106-1118, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:918-932. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.