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

Juan F. Perez, Benny Van Houdt

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)487-517
Number of pages31
JournalProbability in the Engineering and Informational Sciences
Volume25
Issue number4
DOIs
StatePublished - Jan 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'The M/G/1-type markov chain with restricted transitions and its application to queues with batch arrivals'. Together they form a unique fingerprint.

Cite this