M/G/k queue: Difference between revisions

Revision as of 22:22, 29 January 2014

Revision as of 07:21, 30 January 2014

Line 1:

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], an '''M/G/k queue''' is a queue model where arrivals are '''M'''arkovian (modulated by a [[Poisson process]]), service times have a '''G'''eneral [[probability distribution|distribution]] and there are ''k'' servers. The model name is written in [[Kendall's notation]], and is an extension of the [[M/M/c queue]], where service times must be [[exponential distribution|exponentially distributed]] and of the [[M/G/1 queue]] with a single server. Most performance metrics for this queueing system are not known and remain an [[open problem]].<ref>{{cite doi|10.1007/s11134-009-9147-4}}</ref>

==Model definition==

Line 9:

Tijms ''et al.'' believe it is "not likely that computationally tractable methods can be developed to compute the exact numerical values of the steady-state probability in the M/G/''k'' queue."<ref name="tijms">{{cite jstor|1426474}}</ref>

Various approximations for the average queue size,<ref>{{cite doi|10.1287/opre.43.1.158}}</ref> stationary distribution<ref>{{cite doi|10.1007/s11134-008-9073-x}}</ref><ref name="cite jstor|169760">{{cite jstor|169760}}</ref> and approximation by a [[reflected Brownian motion]]<ref>{{cite doi|10.1287/opre.31.2.304}}</ref><ref name="yao">{{cite doi|10.1287/opre.33.6.1266}}</ref> have been offered by different authors. Recently a new approximate approach based on [[Laplace transform]] for steady state probabilities has been proposed by Hamzeh Khazaei ''et al.'' .<ref>{{cite doi|10.1109/TPDS.2011.199}}</ref><ref>{{cite doi|10.1109/ICDCSW.2011.13}}</ref>. This new approach is yet accurate enough in cases of large number of servers and when the distribution of service time has a [[Coefficient of variation]] more than one.

==Average delay/waiting time==

There are numerous approximations for the average delay a job experiences.<ref>{{ name="cite jstor|169760}}"/><ref name="yao" /ref><ref>{{cite jstor|1426432}}</ref><ref>{{cite jstor|3212698}}</ref><ref>{{cite jstor|3213437}}</ref><ref>{{cite jstor|172087}}</ref><ref name="yao" /> The first such was given in 1959 using a factor to adjust the mean waiting time in an [[M/M/c queue]]<ref name="gbdz" /><ref>{{cite doi|10.1057/jors.1959.5}}</ref> This result is sometimes known as Kingman's law of congestion.<ref>{{cite doi|10.1287/msom.5.2.79.16071}}</ref>

:<math>E[W^{\text{M/G/}k}] = \frac{C^2+1}{2} \mathbb E [ W^{\text{M/M/}c}]</math>