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]

References

↑ 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.
↑ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63: 3–4. doi:10.1007/s11134-009-9147-4.
↑ 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.
1 2 3 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.

Queueing theory

Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue

Arrival processes	Poisson process Markovian arrival process Rational arrival process

Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network

Service policies	FIFO LIFO Processor sharing Round-robin Shortest job first Shortest remaining time

Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method

Limit theorems	Fluid limit Mean field theory Heavy traffic approximation Reflected Brownian motion

Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue

Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering

Category

This article is issued from Wikipedia - version of the 6/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.