The M/G/1-type markov chain with restricted transitions and its application to queues with batch arrivals

Juan F. Perez, Benny Van Houdt

Resultado de la investigación: Contribución a RevistaArtículo

3 Citas (Scopus)

Resumen

We consider M/G/ 1-type Markov chains where a transition that decreases the value of the level triggers the phase to a small subset of the phase space. We show how this structure—referred to as restricted downward transitions—can be exploited to speed up the computation of the stationary probability vector of the chain. To this end we define a new M/G/ 1-type Markov chain with a smaller block size, the G matrix of which is used to find the original chain’s G matrix. This approach is then used to analyze the BMAP/PH/1 queue and the BMAP[2]/PH[2]/l preemptive priority queue, yielding significant reductions in computation time.

Idioma originalEnglish (US)
Páginas (desde-hasta)487-517
Número de páginas31
PublicaciónProbability in the Engineering and Informational Sciences
Volumen25
N.º4
DOI
EstadoPublished - ene 1 2011
Publicado de forma externa

Huella dactilar

Batch Arrivals
Markov processes
Queue
Markov chain
Preemptive Priority
Priority Queue
Trigger
Phase Space
Speedup
Decrease
Subset
Batch

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Citar esto

@article{873b7f5ee6e64953bff6344bf55cf997,
title = "The M/G/1-type markov chain with restricted transitions and its application to queues with batch arrivals",
abstract = "We consider M/G/ 1-type Markov chains where a transition that decreases the value of the level triggers the phase to a small subset of the phase space. We show how this structure—referred to as restricted downward transitions—can be exploited to speed up the computation of the stationary probability vector of the chain. To this end we define a new M/G/ 1-type Markov chain with a smaller block size, the G matrix of which is used to find the original chain’s G matrix. This approach is then used to analyze the BMAP/PH/1 queue and the BMAP[2]/PH[2]/l preemptive priority queue, yielding significant reductions in computation time.",
author = "Perez, {Juan F.} and Houdt, {Benny Van}",
year = "2011",
month = "1",
day = "1",
doi = "10.1017/S0269964811000155",
language = "English (US)",
volume = "25",
pages = "487--517",
journal = "Probability in the Engineering and Informational Sciences",
issn = "0269-9648",
publisher = "Cambridge University Press",
number = "4",

}

The M/G/1-type markov chain with restricted transitions and its application to queues with batch arrivals. / Perez, Juan F.; Houdt, Benny Van.

En: Probability in the Engineering and Informational Sciences, Vol. 25, N.º 4, 01.01.2011, p. 487-517.

Resultado de la investigación: Contribución a RevistaArtículo

TY - JOUR

T1 - The M/G/1-type markov chain with restricted transitions and its application to queues with batch arrivals

AU - Perez, Juan F.

AU - Houdt, Benny Van

PY - 2011/1/1

Y1 - 2011/1/1

N2 - We consider M/G/ 1-type Markov chains where a transition that decreases the value of the level triggers the phase to a small subset of the phase space. We show how this structure—referred to as restricted downward transitions—can be exploited to speed up the computation of the stationary probability vector of the chain. To this end we define a new M/G/ 1-type Markov chain with a smaller block size, the G matrix of which is used to find the original chain’s G matrix. This approach is then used to analyze the BMAP/PH/1 queue and the BMAP[2]/PH[2]/l preemptive priority queue, yielding significant reductions in computation time.

AB - We consider M/G/ 1-type Markov chains where a transition that decreases the value of the level triggers the phase to a small subset of the phase space. We show how this structure—referred to as restricted downward transitions—can be exploited to speed up the computation of the stationary probability vector of the chain. To this end we define a new M/G/ 1-type Markov chain with a smaller block size, the G matrix of which is used to find the original chain’s G matrix. This approach is then used to analyze the BMAP/PH/1 queue and the BMAP[2]/PH[2]/l preemptive priority queue, yielding significant reductions in computation time.

UR - http://www.scopus.com/inward/record.url?scp=84870669375&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84870669375&partnerID=8YFLogxK

U2 - 10.1017/S0269964811000155

DO - 10.1017/S0269964811000155

M3 - Article

AN - SCOPUS:84870669375

VL - 25

SP - 487

EP - 517

JO - Probability in the Engineering and Informational Sciences

JF - Probability in the Engineering and Informational Sciences

SN - 0269-9648

IS - 4

ER -