M/D/c queue

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.

Model definition

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

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

${\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 P_n for the stationary probability of a system with n or fewer customers, ^[5]

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