Kingman's Formula
   HOME

TheInfoList



OR:

In
queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because th ...
, a discipline within the mathematical
theory of probability Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...
, Kingman's formula, also known as the VUT equation, is an approximation for the mean waiting time in a
G/G/1 queue In queueing theory, a discipline within the mathematical theory of probability, the G/G/1 queue represents the queue length in a system with a single server where interarrival times have a general (meaning arbitrary) distribution and service times h ...
. The formula is the product of three terms which depend on utilization (U), variability (V) and service time (T). It was first published by
John Kingman Sir John Frank Charles Kingman (born 28 August 1939) is a British mathematician. He served as N. M. Rothschild and Sons Professor of Mathematical Sciences and Director of the Isaac Newton Institute at the University of Cambridge from 2001 unt ...
in his 1961 paper ''The single server queue in heavy traffic''. It is known to be generally very accurate, especially for a system operating close to saturation.


Statement of formula

Kingman's approximation states: :\mathbb E(W_q) \approx \left( \frac \right) \left( \frac\right) \tau where \mathbb E(W_q) is the mean waiting time, ''τ'' is the mean service time (i.e. ''μ'' = 1/''τ'' is the service rate), ''λ'' is the mean arrival rate, ''ρ'' = ''λ''/''μ'' is the utilization, ''ca'' is the
coefficient of variation In probability theory and statistics, the coefficient of variation (CV), also known as normalized root-mean-square deviation (NRMSD), percent RMS, and relative standard deviation (RSD), is a standardized measure of dispersion of a probability ...
for arrivals (that is the standard deviation of arrival times divided by the mean arrival time) and ''cs'' is the coefficient of variation for service times.


References

{{Queueing theory Single queueing nodes