D/M/1 queue

In queueing theory, a discipline within the mathematical theory of probability, a D/M/1 queue represents the queue length in a system having a single server, where arrivals occur at fixed regular intervals and job service requirements are random with an exponential distribution. The model name is written in Kendall's notation.^[1] Agner Krarup Erlang first published a solution to the stationary distribution of a D/M/1 and D/M/k queue, the model with k servers, in 1917 and 1920.^[2][3]

Model definition

A D/M/1 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 deterministically at fixed times β apart.
• Service times are exponentially distributed (with rate parameter μ).
• A single server serves customers one at a time 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.

Stationary distribution

When μβ > 1, the queue has stationary distribution^[4]

${\displaystyle \pi _{i}={\begin{cases}0&{\text{ when }}i=0\\(1-\delta )\delta ^{i-1}&{\text{ when }}i>0\end{cases}}}$

where δ is the root of the equation δ = e^{-μβ(1 – δ)} with smallest absolute value.

Idle times

The mean stationary idle time of the queue (period with 0 customers) is β – 1/μ, with variance (1 + δ − 2μβδ)/μ²(1 – δ).^[4]

Waiting times

The mean stationary waiting time of arriving jobs is (1/μ) δ/(1 – δ).^[4]