An approximation approach for the deviation matrix of continuous-time Markov processes with application to Markov decision theory

B.F. Heidergott, A. Hordijk, N. Leder

Research output: Contribution to JournalArticleAcademicpeer-review

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 toMarkov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm. © 2010 INFORMS.
Original languageEnglish
Pages (from-to)918-932
Number of pages13
JournalOperations Research
Volume58
DOIs
Publication statusPublished - 2010

Fingerprint

Decision theory
Markov processes
Approximation algorithms
Access control
Continuous time
Markov process
Approximation
Deviation
Queue
Generator

Cite this

@article{45a2e43bda1e46bcbc21dcfdd8791beb,
title = "An approximation approach for the deviation matrix of continuous-time Markov processes with application to Markov decision theory",
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 toMarkov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm. {\circledC} 2010 INFORMS.",
author = "B.F. Heidergott and A. Hordijk and N. Leder",
year = "2010",
doi = "10.1287/opre.1090.0786",
language = "English",
volume = "58",
pages = "918--932",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

An approximation approach for the deviation matrix of continuous-time Markov processes with application to Markov decision theory. / Heidergott, B.F.; Hordijk, A.; Leder, N.

In: Operations Research, Vol. 58, 2010, p. 918-932.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - An approximation approach for the deviation matrix of continuous-time Markov processes with application to Markov decision theory

AU - Heidergott, B.F.

AU - Hordijk, A.

AU - Leder, N.

PY - 2010

Y1 - 2010

N2 - 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 toMarkov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm. © 2010 INFORMS.

AB - 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 toMarkov decision theory for computing the optimal control policy. Numerical examples are presented to highlight the efficiency of the proposed algorithm. © 2010 INFORMS.

U2 - 10.1287/opre.1090.0786

DO - 10.1287/opre.1090.0786

M3 - Article

VL - 58

SP - 918

EP - 932

JO - Operations Research

JF - Operations Research

SN - 0030-364X

ER -