Pollaczek–Khinchine formula

In queuing theory, a branch of probability theory, the Pollaczek - Khinchin formula is a formula to calculate the average queue length at an operating model whose request stream is a Poisson distribution and the service times of any distribution subject to ( a M/G/1-Modell in Kendall notation). It can also be used to calculate the average waiting time in this model.

History

The formula was first published by Felix Pollaczek 1930 and revised by Alexander Khinchin two years later.

Average queue length

The formula returns the average queue length

Of. Here are

  • The arrival rate of the Poisson stream,
  • The average turnaround time of check-in time distribution,
  • The utilization and
  • The variance of the service time distribution.

For a finite queue length, it is necessary that applies, otherwise the requests arrive faster than they can be handled. The traffic density is between and. This means the average idle time of the control. If the arrival rate be greater than or equal to the service rate, the waiting time goes to infinity. The variance term of the formula is due to the waiting time paradox.

Average waiting time

The term denotes the average time in the system, is considered, the average waiting time and the operating rate. Using Little's law,

With

  • As average queue length,
  • As arrival rate of Poissonstroms and
  • As the average time in the system

Applies

As a formula, the average waiting time is then followed by

Kendall's notation Mathematische Zeitschrift Digital Object Identifier Annals of Mathematical Statistics John Kingman
655123
de