Pollaczek-Chintschin-Formel

In der Warteschlangentheorie, einem Teilgebiet der Wahrscheinlichkeitstheorie, ist die Pollaczek-Chintschin-Formel eine Formel zur Berechnung der mittleren Warteschlangenlänge bei einem Bedienmodell, dessen Anforderungsstrom Poisson-verteilt ist und dessen Bedienzeiten einer beliebigen Verteilung unterliegen (ein M/G/1-Modell in der Kendall-Notation). Sie kann ebenso zur Berechnung der durchschnittlichen Wartezeit in diesem Modell verwendet werden.

Geschichte

Die Formel wurde zunächst von Felix Pollaczek 1930 veröffentlicht und von Alexander Chintschin zwei Jahre später überarbeitet.

Durchschnittliche Warteschlangenlänge

Die Formel gibt die mittlere Warteschlangenlänge $L$ mit

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

an. Hierbei sind

• $\lambda$ die Ankunftsrate des Poisson-Stroms,
• $1/\mu$ die durchschnittliche Abfertigungszeit der Abfertigungszeitverteilung $S$,
• $\rho =\lambda /\mu$ die Auslastung und
• $\mathrm{Var}(S)$ die Varianz der Abfertigungszeitverteilung $S$.

Für eine stabile Warteschlangenlänge ist es notwendig, dass $\rho <1$ gilt, da sonst die Anfragen schneller ankommen, als sie abgefertigt werden. Die Verkehrsdichte liegt zwischen $0$ und $1$. Dies bezeichnet die durchschnittliche Leerlaufzeit des Bedienelements. Sollte die Ankunftsrate ${\lambda }_a$ größer oder gleich der Bedienrate ${\lambda }_s$ sein, geht die Wartezeit gegen unendlich. Der Varianzterm der Formel resultiert aus dem Wartezeitparadoxon.

Durchschnittliche Wartezeit

Die Zeit $W$ bezeichne die durchschnittliche Zeit im System, dann gilt $W=W^{\prime }+{\mu }^{-1}$, wobei $W^{\prime }$ die durchschnittliche Wartezeit und $\mu$ die Bedienrate ist. Unter Verwendung von Littles Gesetz,

$L=\lambda W$

mit

• $L$ als durchschnittliche Warteschlangenlänge,
• $\lambda$ als Ankunftsrate des Poissonstroms und
• $W$ als durchschnittliche Zeit im System

gilt

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

Als Formel der durchschnittlichen Wartezeit folgt dann

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