Jump to content

M/D/c queue

From Wikipedia, the free encyclopedia

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]

Crommelin showed that, writing Pn for the stationary probability of a system with n or fewer customers, [5]

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–354. doi:10.1214/aoms/1177728975. JSTOR 2236285.
  2. ^ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63 (1–4): 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.