M/D/c queue

From Wikipedia, the free encyclopedia
  (Redirected from M/D/k queue)
Jump to: navigation, search

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

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.

  • Arrivals occur at rate λ according to a Poisson process and move the process from state i to i + 1.
  • Service times are deterministic time D (serving at rate μ = 1/D).
  • c servers serve customers 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.

Waiting time distribution[edit]

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[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. ^ "The theory of probabilities and telephone conversations". Nyt Tidsskrift for Matematik B 20: 33–39. 1909. Archived from the original 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.  edit
  5. ^ Crommelin, C.D. (1932). "Delay probability formulas when the holding times are constant". P.O. Electr. Engr. J. 25: 41–50.