M/D/c queue (original) (raw)

From Wikipedia, the free encyclopedia

In queueing theory, a discipline within the mathematical theory of probability, an M/D/c queue represents the queue length in a system having c servers, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation.[1] Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory.[2][3] The model is an extension of the M/D/1 queue which has only a single server.

An M/D/c 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 system, including any currently in service.

Arrivals occur at rate λ according to a Poisson process and move the process from state i to i + 1.
Service times are deterministic time D (serving at rate μ = 1/D).
c servers serve customers from the front of the queue, according to a first-come, first-served discipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.
The buffer is of infinite size, so there is no limit on the number of customers it can contain.

Waiting time distribution

[edit]

Erlang showed that when ρ = (λ D)/c < 1, the waiting time distribution has distribution F(y) given by[4]

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} .} $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 P n for the stationary probability of a system with n or fewer customers,[5]

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.} $\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.$

^ 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.
^ 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.
^ "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.
^ 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.
^ Crommelin, C.D. (1932). "Delay probability formulas when the holding times are constant". P.O. Electr. Engr. J. 25: 41–50.