M/G/k queue

<h2 id="model-definition">Model definition</h2>
A queue represented by a M/G/k queue is a stochastic process whose <a href="/facts/State_space/H1vjb3LL">state space</a> 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 + 1 represent the arrival of a new customer: the times between such arrivals have an <a href="/facts/Exponential_distribution/yY3EdV0u">exponential distribution</a> with parameter λ. Transitions from state i to i − 1 represent the departure of a customer who has just finished being served: the length of time required for serving an individual customer has a general distribution function. The lengths of times between arrivals and of service periods are <a href="/facts/Random_variable/TwTBXnLT">random variables</a> which are assumed to be <a href="/facts/Statistically_independent/NUzQtnUL">statistically independent</a>.

<h2 id="steady-state-distribution">Steady state distribution</h2>
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."<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
Various approximations for the average queue size,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> stationary distribution<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> and approximation by a <a href="/facts/Reflected_Brownian_motion/Wb4Knnzv">reflected Brownian motion</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> have been offered by different authors. Recently a new approximate approach based on <a href="/facts/Laplace_transform/0Ge4MIc9">Laplace transform</a> for steady state probabilities has been proposed by Hamzeh Khazaei et al..<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> This new approach is yet accurate enough in cases of large number of servers and when the distribution of service time has a <a href="/facts/Coefficient_of_variation/V8ddKkz4">Coefficient of variation</a> more than one.

<h2 id="average-delaywaiting-time">Average delay/waiting time</h2>
There are numerous approximations for the average delay a job experiences.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> The first such was given in 1959 using a factor to adjust the mean waiting time in an <a href="/facts/M%2fM%2fc_queue/MXB6lmQ1">M/M/c queue</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> This result is sometimes known as Kingman's law of congestion.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

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

where C is the <a href="/facts/Coefficient_of_variation/V8ddKkz4">coefficient of variation</a> of the service time distribution. <a href="/facts/Ward_Whitt/pHujNfB4">Ward Whitt</a> described this approximation as “usually an excellent approximation, even given extra information about the service-time distribution."<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
However, it is known that no approximation using only the first two moments can be accurate in all cases.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>
A <a href="/facts/Markov%25E2%2580%2593Krein/VCElQIyX">Markov–Krein</a> characterization has been shown to produce tight bounds on the mean waiting time.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h2 id="inter-departure-times">Inter-departure times</h2>
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.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>

<h2 id="two-servers">Two servers</h2>
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 <a href="/facts/Integral_equation/LCu4Imfq">integral equations</a><a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> or the Laplace transform of the distribution when the service time distribution is a mixture of exponential distributions.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> The Laplace transform of queue length<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> and waiting time distributions<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> can be computed when the waiting time distribution has a rational Laplace transform.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63 (1–4): 3–4. doi:10.1007/s11134-009-9147-4. S2CID 38588726. <a href="/wiki/John_Kingman" target="_blank">/wiki/John_Kingman</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Tijms, H. C.; Van Hoorn, M. H.; Federgruen, A. (1981). "Approximations for the Steady-State Probabilities in the M/G/c Queue". Advances in Applied Probability. 13 (1): 186–206. doi:10.2307/1426474. JSTOR 1426474. S2CID 222335724. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Ma, B. N. W.; Mark, J. W. (1995). "Approximation of the Mean Queue Length of an M/G/c Queueing System". Operations Research. 43 (1): 158–165. doi:10.1287/opre.43.1.158. JSTOR 171768. <a href="/wiki/Operations_Research_(journal)" target="_blank">/wiki/Operations_Research_(journal)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Breuer, L. (2008). "Continuity of the M/G/c queue". Queueing Systems. 58 (4): 321–331. doi:10.1007/s11134-008-9073-x. S2CID 2345317. <a href="/wiki/Queueing_Systems" target="_blank">/wiki/Queueing_Systems</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Hokstad, Per (1978). "Approximations for the M/G/m Queue". Operations Research. 26 (3). INFORMS: 510–523. doi:10.1287/opre.26.3.510. JSTOR 169760. <a href="/wiki/Operations_Research:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences" target="_blank">/wiki/Operations_Research:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Kimura, T. (1983). "Diffusion Approximation for an M/G/m Queue". Operations Research. 31 (2): 304–321. doi:10.1287/opre.31.2.304. JSTOR 170802. <a href="/wiki/Operations_Research_(journal)" target="_blank">/wiki/Operations_Research_(journal)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Yao, D. D. (1985). "Refining the Diffusion Approximation for the M/G/m Queue". Operations Research. 33 (6): 1266–1277. doi:10.1287/opre.33.6.1266. JSTOR 170637. <a href="/wiki/Operations_Research_(journal)" target="_blank">/wiki/Operations_Research_(journal)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Khazaei, H.; Misic, J.; Misic, V. B. (2012). "Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems". IEEE Transactions on Parallel and Distributed Systems. 23 (5): 936. doi:10.1109/TPDS.2011.199. S2CID 16934438. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Khazaei, H.; Misic, J.; Misic, V. B. (2011). "Modelling of Cloud Computing Centers Using M/G/m Queues". 2011 31st International Conference on Distributed Computing Systems Workshops. p. 87. doi:10.1109/ICDCSW.2011.13. ISBN 978-1-4577-0384-3. S2CID 16067523. <a href="978-1-4577-0384-3" target="_blank">978-1-4577-0384-3</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Hokstad, Per (1978). "Approximations for the M/G/m Queue". Operations Research. 26 (3). INFORMS: 510–523. doi:10.1287/opre.26.3.510. JSTOR 169760. <a href="/wiki/Operations_Research:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences" target="_blank">/wiki/Operations_Research:_A_Journal_of_the_Institute_for_Operations_Research_and_the_Management_Sciences</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Yao, D. D. (1985). "Refining the Diffusion Approximation for the M/G/m Queue". Operations Research. 33 (6): 1266–1277. doi:10.1287/opre.33.6.1266. JSTOR 170637. <a href="/wiki/Operations_Research_(journal)" target="_blank">/wiki/Operations_Research_(journal)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Hokstad, Per (1980). "The Steady-State Solution of the M/K2/m Queue". Advances in Applied Probability. 12 (3). Applied Probability Trust: 799–823. doi:10.2307/1426432. JSTOR 1426432. S2CID 124883099. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Köllerström, Julian (1974). "Heavy Traffic Theory for Queues with Several Servers. I". Journal of Applied Probability. 11 (3). Applied Probability Trust: 544–552. doi:10.1017/s0021900200096327. JSTOR 3212698. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Nozaki, S. A.; Ross, S. M. (1978). "Approximations in Finite-Capacity Multi-Server Queues with Poisson Arrivals". Journal of Applied Probability. 15 (4): 826–834. doi:10.2307/3213437. JSTOR 3213437. S2CID 32476285. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Boxma, O. J.; Cohen, J. W.; Huffels, N. (1979). "Approximations of the Mean Waiting Time in an M/G/s Queueing System". Operations Research. 27 (6). INFORMS: 1115–1127. doi:10.1287/opre.27.6.1115. JSTOR 172087. <a href="/wiki/Onno_Boxma" target="_blank">/wiki/Onno_Boxma</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Gupta, V.; Harchol-Balter, M.; Dai, J. G.; Zwart, B. (2009). "On the inapproximability of M/G/K: Why two moments of job size distribution are not enough". Queueing Systems. 64: 5–48. CiteSeerX 10.1.1.151.5844. doi:10.1007/s11134-009-9133-x. S2CID 16755599. <a href="/wiki/Mor_Harchol-Balter" target="_blank">/wiki/Mor_Harchol-Balter</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Lee, A. M.; Longton, P. A. (1959). "Queueing Processes Associated with Airline Passenger Check-in". Journal of the Operational Research Society. 10: 56–71. doi:10.1057/jors.1959.5. <a href="/wiki/Journal_of_the_Operational_Research_Society" target="_blank">/wiki/Journal_of_the_Operational_Research_Society</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Gans, N.; Koole, G.; Mandelbaum, A. (2003). "Telephone Call Centers: Tutorial, Review, and Research Prospects" (PDF). Manufacturing & Service Operations Management. 5 (2): 79. doi:10.1287/msom.5.2.79.16071. <a href="http://ie.technion.ac.il/Labs/Serveng/files/CCReview.pdf" target="_blank">http://ie.technion.ac.il/Labs/Serveng/files/CCReview.pdf</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Whitt, W. (2009). "Approximations for the GI/G/m Queue" (PDF). Production and Operations Management. 2 (2): 114–161. doi:10.1111/j.1937-5956.1993.tb00094.x. <a href="/wiki/Ward_Whitt" target="_blank">/wiki/Ward_Whitt</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Gupta, V.; Harchol-Balter, M.; Dai, J. G.; Zwart, B. (2009). "On the inapproximability of M/G/K: Why two moments of job size distribution are not enough". Queueing Systems. 64: 5–48. CiteSeerX 10.1.1.151.5844. doi:10.1007/s11134-009-9133-x. S2CID 16755599. <a href="/wiki/Mor_Harchol-Balter" target="_blank">/wiki/Mor_Harchol-Balter</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Gupta, V.; Osogami, T. (2011). "On Markov–Krein characterization of the mean waiting time in M/G/K and other queueing systems". Queueing Systems. 68 (3–4): 339. doi:10.1007/s11134-011-9248-8. S2CID 35061112. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Veeger, C.; Kerner, Y.; Etman, P.; Adan, I. (2011). "Conditional inter-departure times from the M/G/s queue". Queueing Systems. 68 (3–4): 353. doi:10.1007/s11134-011-9240-3. S2CID 19382087. <a href="/wiki/Queueing_Systems" target="_blank">/wiki/Queueing_Systems</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Knessl, C.; Matkowsky, B. J.; Schuss, Z.; Tier, C. (1990). "An Integral Equation Approach to the M/G/2 Queue". Operations Research. 38 (3): 506. doi:10.1287/opre.38.3.506. JSTOR 171363. <a href="/wiki/Operations_Research_(journal)" target="_blank">/wiki/Operations_Research_(journal)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Cohen, J. W. (1982). "On the M/G/2 queueing model". Stochastic Processes and Their Applications. 12 (3): 231–248. doi:10.1016/0304-4149(82)90046-1. <a href="/wiki/Wim_Cohen" target="_blank">/wiki/Wim_Cohen</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Hokstad, Per (1979). "On the Steady-State Solution of the M/G/2 Queue". Advances in Applied Probability. 11 (1). Applied Probability Trust: 240–255. doi:10.2307/1426776. JSTOR 1426776. S2CID 125014523. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Boxma, O. J.; Deng, Q.; Zwart, A. P. (2002). "Waiting-Time Asymptotics for the M/G/2 Queue with Heterogeneous Servers". Queueing Systems. 40: 5–31. doi:10.1023/A:1017913826973. S2CID 2513624. <a href="/wiki/Onno_Boxma" target="_blank">/wiki/Onno_Boxma</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
</ol>

M/G/k queue open-in-new

M/G/k queue