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.

Waiting time distribution

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

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

\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.

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. "The theory of probabilities and telephone conversations" (PDF). Nyt Tidsskrift for Matematik B 20: 33–39. 1909. Archived from the original (PDF) on 2012-02-07.
  4. Franx, G. J. (2001). "A simple solution for the M/D/c waiting time distribution". Operations Research Letters 29 (5): 221–229. doi:10.1016/S0167-6377(01)00108-0.
  5. Crommelin, C.D. (1932). "Delay probability formulas when the holding times are constant". P.O. Electr. Engr. J. 25: 41–50.
This article is issued from Wikipedia - version of the Saturday, August 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.