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μβδ)/μ^2(1 – δ).[4]

Waiting times

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

References

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. doi:10.1214/aoms/1177728975. JSTOR 2236285.
2. Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63: 3–4. doi:10.1007/s11134-009-9147-4.
3. Janssen, A. J. E. M.; Van Leeuwaarden, J. S. H. (2008). "Back to the roots of the M/D/s queue and the works of Erlang, Crommelin and Pollaczek" (PDF). Statistica Neerlandica. 62 (3): 299. doi:10.1111/j.1467-9574.2008.00395.x.
4. Jansson, B. (1966). "Choosing a Good Appointment System--A Study of Queues of the Type (D, M, 1)". Operations Research. 14 (2): 292–312. doi:10.1287/opre.14.2.292. JSTOR 168256.