M/D/c queue

<h2 id="model-definition">Model definition</h2>
An M/D/c 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 system, including any currently in service. 

<ul><li>Arrivals occur at rate λ according to a <a href="/facts/Poisson_process/8uphjAUc">Poisson process</a> and move the process from state i to i + 1.</li>
<li>Service times are deterministic time D (serving at rate μ = 1/D).</li>
<li>c servers serve customers from the front of the queue, according to a <a href="/facts/First-come,_first-served/8NDl56EM">first-come, first-served</a> discipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.</li>
<li>The buffer is of infinite size, so there is no limit on the number of customers it can contain.</li></ul>
<h2 id="waiting-time-distribution">Waiting time distribution</h2>
Erlang showed that when ρ = (λ D)/c < 1, the waiting time distribution has distribution F(y) given by<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

F
        (
        y
        )
        =
        
          ∫
          
            0
          
          
            ∞
          
        
        F
        (
        x
        +
        y
        −
        D
        )
        
          
            
              
                λ
                
                  c
                
              
              
                x
                
                  c
                  −
                  1
                
              
            
            
              (
              c
              −
              1
              )
              !
            
          
        
        
          e
          
            −
            λ
            x
          
        
        
          d
        
        x
        ,
        
        y
        ≥
        0
        
        c
        ∈
        
          N
        
        .
      
    
    {\displaystyle F(y)=\int _{0}^{\infty }F(x+y-D){\frac {\lambda ^{c}x^{c-1}}{(c-1)!}}e^{-\lambda x}{\text{d}}x,\quad y\geq 0\quad c\in \mathbb {N} .}

Crommelin showed that, writing Pn for the stationary probability of a system with n or fewer customers,
<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

P
 
 (
 W
 ≤
 x
 )
 =
 
 ∑
 
 n
 =
 0
 
 
 c
 −
 1
 
 
 
 P
 
 n
 
 
 
 ∑
 
 k
 =
 1
 
 
 m
 
 
 
 
 
 (
 −
 λ
 (
 x
 −
 k
 D
 )
 
 )
 
 (
 k
 +
 1
 )
 c
 −
 1
 −
 n
 
 
 
 
 (
 (
 K
 +
 1
 )
 c
 −
 1
 −
 n
 )
 !
 
 
 
 
 e
 
 λ
 (
 x
 −
 k
 D
 )
 
 
 ,
 
 m
 D
 ≤
 x
 <
 (
 m
 +
 1
 )
 D
 .
 
 
 {\displaystyle \mathbb {P} (W\leq x)=\sum _{n=0}^{c-1}P_{n}\sum _{k=1}^{m}{\frac {(-\lambda (x-kD))^{(k+1)c-1-n}}{((K+1)c-1-n)!}}e^{\lambda (x-kD)},\quad mD\leq x<(m+1)D.}

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

<ol>
<li id="fn:1">Kendall, D. G. (1953). "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain". The Annals of Mathematical Statistics. 24 (3): 338–354. doi:10.1214/aoms/1177728975. JSTOR 2236285. <a href="/wiki/David_George_Kendall" target="_blank">/wiki/David_George_Kendall</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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. <a href="/wiki/John_Kingman" target="_blank">/wiki/John_Kingman</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"The theory of probabilities and telephone conversations" (PDF). Nyt Tidsskrift for Matematik B. 20: 33–39. 1909. Archived from the original (PDF) on 2012-02-07. <a href="https://web.archive.org/web/20120207184053/http://oldwww.com.dtu.dk/teletraffic/erlangbook/pps131-137.pdf" target="_blank">https://web.archive.org/web/20120207184053/http://oldwww.com.dtu.dk/teletraffic/erlangbook/pps131-137.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Franx, G. J. (2001). "A simple solution for the M/D/c waiting time distribution". Operations Research Letters. 29 (5): 221–229. doi:10.1016/S0167-6377(01)00108-0. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Crommelin, C.D. (1932). "Delay probability formulas when the holding times are constant". P.O. Electr. Engr. J. 25: 41–50. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

M/D/c queue open-in-new

M/D/c queue