M/G/k queue: Difference between revisions

Revision as of 18:35, 12 June 2013

Latest revision as of 10:41, 17 July 2025

(44 intermediate revisions by 21 users not shown)

Line 1:

{{Use American English|date = January 2019}}

In [[queueing theory]], 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]].

{{Short description|Queue model}}

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[[Markov property|Markovian]] (modulated by a [[Poisson process]]), service times have a '''G'''eneral [[probability distribution|general 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 journal | last1 = Kingman | first1 = J. F. C. | author-link1 = John Kingman | title = The first Erlang century—and the next | journal = [[Queueing Systems]] | volume = 63 | pages = 3–4 | year = 2009 | issue = 1–4 | doi = 10.1007/s11134-009-9147-4| s2cid = 38588726 }}</ref>

==Model definition==

A queue represented by a M/G/''k'' queue is a stochastic process whose [[state space]] is the set {0,1,2,3...}, where the value corresponds to the number of memberscustomers in the queue, including any being served. Transitions from state ''i'' to ''i''&nbsp;+&nbsp;1 represent the arrival of a new queue membercustomer: the times between such arrivals have an [[exponential distribution]] with parameter λ. Transitions from state ''i'' to ''i''&nbsp;&minus;&nbsp;1 represent the departure of a membercustomer who has beenjust being served, finishingfinished being served and departing: the length of time required for serving an individual queue membercustomer has a general distribution function. The lengths of times between arrivals and of service periods are [[random variable]]s which are assumed to be [[statistically independent]].

==Steady state distribution==

==Results==

Results for an extended version of this problem, an M/G/''k'' queue with ''k''&nbsp;>&nbsp;1 servers remains an open problem.<ref>{{cite doi|10.1007/s11134-009-9147-4}}</ref> In this model, arrivals are determined by a [[Poisson process]] and jobs can be served by any one of ''k'' servers. 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">{{citeCite journal jstor| last1 = Tijms | first1 = H. C. | last2 = Van Hoorn | first2 = M. H. | last3 = Federgruen | first3 = A. | title = Approximations for the Steady-State Probabilities in the M/G/c Queue | journal = Advances in Applied Probability | volume = 13 | issue = 1 | pages = 186–206 | doi = 10.2307/1426474 | jstor = 1426474| year = 1981 | s2cid = 222335724 }}</ref>

Various approximations for the average queue size,<ref>{{Cite journal | last1 = Ma | first1 = B. N. W. | last2 = Mark | first2 = J. W. | doi = 10.1287/opre.43.1.158 | title = Approximation of the Mean Queue Length of an M/G/c Queueing System | journal = [[Operations Research (journal)|Operations Research]]| volume = 43 | pages = 158–165 | year = 1995 | issue = 1 | jstor = 171768}}</ref> stationary distribution<ref>{{Cite journal | last1 = Breuer | first1 = L. | title = Continuity of the M/G/c queue | doi = 10.1007/s11134-008-9073-x | journal = [[Queueing Systems]]| volume = 58 | issue = 4 | pages = 321–331 | year = 2008 | s2cid = 2345317 }}</ref><ref name="cite jstor|169760">{{cite journal | last1 = Hokstad | first1 = Per | year = 1978 | title = Approximations for the M/G/m Queue | journal = [[Operations Research: A Journal of the Institute for Operations Research and the Management Sciences|Operations Research]] | volume = 26 | issue = 3 | pages = 510–523 | publisher = INFORMS | jstor = 169760 | doi = 10.1287/opre.26.3.510}}</ref> and approximation by a [[reflected Brownian motion]]<ref>{{Cite journal | last1 = Kimura | first1 = T. | title = Diffusion Approximation for an M/G/m Queue | doi = 10.1287/opre.31.2.304 | journal = [[Operations Research (journal)|Operations Research]]| volume = 31 | issue = 2 | pages = 304–321 | year = 1983 | jstor = 170802}}</ref><ref name="yao">{{Cite journal | last1 = Yao | first1 = D. D. | title = Refining the Diffusion Approximation for the M/G/m Queue | doi = 10.1287/opre.33.6.1266 | journal = [[Operations Research (journal)|Operations Research]]| volume = 33 | issue = 6 | pages = 1266–1277 | year = 1985 | jstor = 170637}}</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 journal | last1 = Khazaei | first1 = H. | last2 = Misic | first2 = J. | last3 = Misic | first3 = V. B. | doi = 10.1109/TPDS.2011.199 | title = Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems | journal = IEEE Transactions on Parallel and Distributed Systems | volume = 23 | issue = 5 | pages = 936 | year = 2012 | s2cid = 16934438 }}</ref><ref>{{Cite book | last1 = Khazaei | first1 = H. | last2 = Misic | first2 = J. | last3 = Misic | first3 = V. B. | doi = 10.1109/ICDCSW.2011.13 | chapter = Modelling of Cloud Computing Centers Using M/G/m Queues | title = 2011 31st International Conference on Distributed Computing Systems Workshops | pages = 87 | year = 2011 | isbn = 978-1-4577-0384-3 | s2cid = 16067523 }}</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.

Various approximations for the average queue size,<ref>{{cite doi|10.1287/opre.43.1.158}}</ref> average delay a job experiences<ref name="tijms" /> (where it is known no approximation using only the first two moments can be accurate in all cases<ref>{{cite doi|10.1007/s11134-009-9133-x}}</ref> and a [[Markov–Krein]] characterisation has been shown to produce tight bounds<ref>{{cite doi|10.1007/s11134-011-9248-8}}</ref>), stationary distribution<ref>{{cite doi|10.1007/s11134-008-9073-x}}</ref><ref>{{cite jstor|169760}}</ref> and approximation by a [[reflected Brownian motion]]<ref>{{cite doi|10.1287/opre.31.2.304}}</ref><ref>{{cite doi|10.1287/opre.33.6.1266}}</ref> have been offered by different authors. See the [[M/M/c queue]] article for the case where service times are exponentially distributed.

==Average delay/waiting time==

===M/G/2 queue===

There are numerous approximations for the average delay a job experiences.<ref name="cite jstor|169760"/><ref name="yao" /><ref>{{cite journal | last1 = Hokstad | first1 = Per | year = 1980 | title = The Steady-State Solution of the M/K₂/m Queue | journal = Advances in Applied Probability | volume = 12 | issue = 3 | pages = 799–823 | publisher = Applied Probability Trust | doi = 10.2307/1426432 | jstor = 1426432| s2cid = 124883099 }}</ref><ref>{{cite journal | last1 = Köllerström | first1 = Julian | year = 1974 | title = Heavy Traffic Theory for Queues with Several Servers. I | journal = Journal of Applied Probability | volume = 11 | issue = 3 | pages = 544–552 | publisher = Applied Probability Trust | jstor = 3212698 | doi=10.1017/s0021900200096327}}</ref><ref>{{Cite journal | last1 = Nozaki | first1 = S. A. | last2 = Ross | first2 = S. M. | title = Approximations in Finite-Capacity Multi-Server Queues with Poisson Arrivals | journal = Journal of Applied Probability | volume = 15 | issue = 4 | pages = 826–834 | doi = 10.2307/3213437 | year = 1978 | jstor = 3213437 | s2cid = 32476285 }}</ref><ref>{{cite journal | last1 = Boxma | first1 = O. J. | author-link1 = Onno Boxma | last2 =Cohen | first2 = J. W. | author-link2 = Wim Cohen | first3 = N. | last3 = Huffels | year = 1979 | title = Approximations of the Mean Waiting Time in an M/G/s Queueing System | journal = [[Operations Research (journal)|Operations Research]] | volume = 27 | issue = 6 | pages = 1115–1127 | publisher = INFORMS | jstor = 172087 | doi=10.1287/opre.27.6.1115}}</ref> 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 journal | last1 = Lee | first1 = A. M. | last2 = Longton | first2 = P. A. | doi = 10.1057/jors.1959.5 | title = Queueing Processes Associated with Airline Passenger Check-in | journal = [[Journal of the Operational Research Society]]| volume = 10 | pages = 56–71 | year = 1959 }}</ref> This result is sometimes known as Kingman's law of congestion.<ref>{{Cite journal | last1 = Gans | first1 = N. | last2 = Koole | first2 = G. | last3 = Mandelbaum | first3 = A. | doi = 10.1287/msom.5.2.79.16071 | title = Telephone Call Centers: Tutorial, Review, and Research Prospects | journal = [[Manufacturing & Service Operations Management]] | volume = 5 | issue = 2 | pages = 79 | year = 2003 | url = http://ie.technion.ac.il/Labs/Serveng/files/CCReview.pdf | doi-access = free | archive-date = 2015-12-08 | access-date = 2015-08-29 | archive-url = https://web.archive.org/web/20151208113728/http://ie.technion.ac.il/Labs/Serveng/files/CCReview.pdf | url-status = dead }}</ref>

For an M/G/2 queue, the model with two servers, the problem of determining marginal probabilities can be reduced to solving a pair of [[integral equation]]s<ref>{{cite doi|10.1287/opre.38.3.506}}</ref> or the Laplace transform of the distribution when the service time distribution is a mixture of exponential distributions.<ref>{{cite doi|10.1016/0304-4149(82)90046-1}}</ref> The Laplace transform of queue length<ref>{{cite jstor|1426776}}</ref> and waiting time distributions<ref>{{cite doi|10.1023/A:1017913826973}}</ref> can be computed when the waiting time distribution has a rational Laplace transform.

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

where ''C'' is the [[coefficient of variation]] of the service time distribution. [[Ward Whitt]] described this approximation as “usually an excellent approximation, even given extra information about the service-time distribution."<ref>{{Cite journal | last1 = Whitt | first1 = W. | author-link1 = Ward Whitt| title = Approximations for the GI/G/m Queue| doi = 10.1111/j.1937-5956.1993.tb00094.x | journal = [[Production and Operations Management]]| volume = 2 | issue = 2 | pages = 114–161 | year = 2009 | url = http://www.columbia.edu/~ww2040/ApproxGIGm1993.pdf}}</ref>

However, it is known that no approximation using only the first two moments can be accurate in all cases.<ref name="gbdz">{{Cite journal | last1 = Gupta | first1 = V. | last2 = Harchol-Balter | first2 = M. |author2-link=Mor Harchol-Balter| last3 = Dai | first3 = J. G. | last4 = Zwart | first4 = B. | title = On the inapproximability of M/G/K: Why two moments of job size distribution are not enough | doi = 10.1007/s11134-009-9133-x | journal = [[Queueing Systems]]| volume = 64 | pages = 5–48 | year = 2009 | s2cid = 16755599 | citeseerx = 10.1.1.151.5844 }}</ref>

A [[Markov–Krein]] characterization has been shown to produce tight bounds on the mean waiting time.<ref>{{Cite journal | last1 = Gupta | first1 = V. | last2 = Osogami | first2 = T. | doi = 10.1007/s11134-011-9248-8 | title = On Markov–Krein characterization of the mean waiting time in M/G/K and other queueing systems | journal = Queueing Systems | volume = 68 | issue = 3–4 | pages = 339 | year = 2011 | s2cid = 35061112 }}</ref>

==Inter-departure times==

It is conjectured that the times between departures, given a departure leaves ''n'' customers in a queue, has a mean which as ''n'' tends to infinity is different from the intuitive 1/''μ'' result.<ref>{{Cite journal | last1 = Veeger | first1 = C. | last2 = Kerner | first2 = Y. | last3 = Etman | first3 = P. | last4 = Adan | first4 = I. | title = Conditional inter-departure times from the M/G/s queue | doi = 10.1007/s11134-011-9240-3 | journal = [[Queueing Systems]]| volume = 68 | issue = 3–4 | pages = 353 | year = 2011 | s2cid = 19382087 }}</ref>

==Two servers==

For an M/G/2 queue (the model with two servers) the problem of determining marginal probabilities can be reduced to solving a pair of [[integral equation]]s<ref>{{Cite journal | last1 = Knessl | first1 = C. | last2 = Matkowsky | first2 = B. J. | last3 = Schuss | first3 = Z. | last4 = Tier | first4 = C. | title = An Integral Equation Approach to the M/G/2 Queue | doi = 10.1287/opre.38.3.506 | journal = [[Operations Research (journal)|Operations Research]]| volume = 38 | issue = 3 | pages = 506 | year = 1990 | jstor = 171363}}</ref> or the Laplace transform of the distribution when the service time distribution is a mixture of exponential distributions.<ref>{{Cite journal | last1 = Cohen | first1 = J. W. | author-link1 = Wim Cohen| title = On the M/G/2 queueing model | doi = 10.1016/0304-4149(82)90046-1 | journal = Stochastic Processes and Their Applications | volume = 12 | issue = 3 | pages = 231–248 | year = 1982 | doi-access = free }}</ref> The Laplace transform of queue length<ref>{{cite journal | last1 = Hokstad | first1 = Per | year = 1979 | title = On the Steady-State Solution of the M/G/2 Queue | journal = Advances in Applied Probability | volume = 11 | issue = 1 | pages = 240–255 | publisher = Applied Probability Trust | doi = 10.2307/1426776 | jstor = 1426776| s2cid = 125014523 }}</ref> and waiting time distributions<ref>{{Cite journal | last1 = Boxma | first1 = O. J. | author-link1 = Onno Boxma| last2 = Deng | first2 = Q. | last3 = Zwart | first3 = A. P. | journal = [[Queueing Systems]]| volume = 40 | pages = 5–31 | year = 2002 | doi = 10.1023/A:1017913826973 | title = Waiting-Time Asymptotics for the M/G/2 Queue with Heterogeneous Servers| s2cid = 2513624 }}</ref> can be computed when the waiting time distribution has a rational Laplace transform.

==References==

Line 23 ⟶ 41:

{{DEFAULTSORT:M G k queue}}

[[Category:Single queueing nodes]]

[[Category:StochasticUnsolved processesproblems in mathematics]]