M/G/k queue: Difference between revisions

Revision as of 11:50, 13 June 2013

Latest revision as of 10:41, 17 July 2025

(36 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]] 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>

{{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>{{citeCite journal doi| 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 customers in the queue, including any being served. Transitions from state ''i'' to ''i''&nbsp;+&nbsp;1 represent the arrival of a new queue customer: 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 customer who has beenjust being served, finishingfinished being served and departing: the length of time required for serving an individual queue customer 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==

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> 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 name="yao">{{cite doi|10.1287/opre.33.6.1266}}</ref> have been offered by different authors

==Average Delaydelay/waiting time==

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>

There are numerous approximations for the average delay a job experiences.<ref>{{cite jstor|169760}}</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>

:<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>{{citeCite journal doi| 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">{{citeCite journal doi| 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]] characterisationcharacterization has been shown to produce tight bounds on the mean waiting time.<ref>{{citeCite journal doi| 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>{{citeCite journal doi| 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>{{citeCite journal doi| 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 jstorjournal | 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>{{citeCite journal doi| 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 35 ⟶ 41:

{{DEFAULTSORT:M G k queue}}

[[Category:Single queueing nodes]]

[[Category:Stochastic processes]]

[[Category:Unsolved problems in mathematics]]