D/M/1 queue

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In queueing theory, a discipline within the mathematical theory of probability, an 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[edit]

An 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[edit]

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

\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[edit]

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

Waiting times[edit]

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

References[edit]

  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.  edit
  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.  edit
  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". Statistica Neerlandica 62 (3): 299. doi:10.1111/j.1467-9574.2008.00395.x.  edit
  4. ^ a b c 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.  edit