Pollaczek-Chinchin formula

In queuing theory , a branch of probability theory , the Pollaczek-Chintschin formula is a formula for calculating the mean queue length for a service model whose request flow is Poisson-distributed and whose service times are subject to any distribution (an M / G / 1 model in the 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 in 1930 and revised by Alexander Chintschin two years later.

Average queue length

The formula is the average queue length with ${\displaystyle L}$

${\displaystyle L=\rho +{\frac {\rho ^{2}+\lambda ^{2}\operatorname {Var} (S)}{2(1-\rho )}}}$

on. Here are

• ${\displaystyle \lambda }$the arrival rate of the Poisson current ,
• ${\displaystyle 1/\mu }$the average handling time of the handling time distribution , ${\displaystyle S}$
• ${\displaystyle \rho =\lambda /\mu }$ the utilization and
• ${\displaystyle \operatorname {Var} (S)}$the variance of the dispatch time distribution . ${\displaystyle S}$

For a stable queue length it is necessary that this applies, otherwise the requests will arrive faster than they are processed. The traffic density is between and . This indicates the average idle time of the control element. If the arrival rate is greater than or equal to the service rate , the waiting time approaches infinity. The variance term of the formula results from the waiting time paradox . ${\displaystyle \rho <1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \lambda _{a}}$ ${\displaystyle \lambda _{s}}$

Average waiting time

The time denotes the average time in the system, then the following applies , where is the average waiting time and the service rate. Using Little's Law , ${\displaystyle W}$ ${\displaystyle W=W'+\mu ^{-1}}$ ${\displaystyle W'}$ ${\displaystyle \mu }$

${\displaystyle L=\lambda W}$

With

• ${\displaystyle L}$ as the average queue length,
• ${\displaystyle \lambda }$ as the arrival rate of the Poisson stream and
• ${\displaystyle W}$ than the average time in the system

applies

${\displaystyle W={\frac {\rho +\lambda \mu \operatorname {Var} (S)}{2(\mu -\lambda )}}+\mu ^{-1}}$.

The formula for the average waiting time then follows

${\displaystyle W'={\frac {L}{\lambda }}-\mu ^{-1}={\frac {\rho +\lambda \mu \operatorname {Var} (S)}{2(\mu -\lambda )}}}$.

Individual evidence

1. ↑ Felix Pollaczek : About a task of the probability theory . In: Mathematical Journal . tape 32 , 1930, pp. 64-100 , doi : 10.1007 / BF01194620 .
2. ↑ Alexander Chintschin : Mathematical theory of a stationary queue . In: Matematicheskii Sbornik . tape 39 , no. 4 , 1932, pp. 73-84 ( mathnet.ru ).
3. ↑ Lajos Takács: Review: JW Cohen, The Single Server Queue . In: Annals of Mathematical Statistics . tape 42 , no. 6 , 1971, p. 2162-2164 , doi : 10.1214 / aoms / 1177693087 .
4. ^ John Kingman : The first Erlang century - and the next . In: Queuing Systems . tape 63 , no. 3-4 , 2009, doi : 10.1007 / s11134-009-9147-4 .
5. ^ John Haigh: Probability Models . Springer, 2002, ISBN 1-85233-431-2 , pp. 192 .
6. ^ Robert B. Cooper, Shun-Chen Niu, Mandyam M. Srinivasan: Some Reflections on the Renewal-Theory Paradox in Queuing Theory . In: Journal of Applied Mathematics and Stochastic Analysis . tape 11 , no. 3 , 1998, p. 355–368 ( fau.edu [PDF; 196 kB ]).
7. ^ Peter G. Harrison, Naresh M. Patel: Performance Modeling of Communication Networks and Computer Architectures . Addison-Wesley, 1992, ISBN 0-201-54419-9 , pp. 228 .