Pollaczek-Chintschin-Formel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 poissonverteilt 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[Bearbeiten]

Die Formel wurde zunächst von Felix Pollaczek 1930 veröffentlicht[1] und von Alexander Chintschin zwei Jahre später überarbeitet.[2][3][4]

Durchschnittliche Warteschlangenlänge[Bearbeiten]

Die Formel gibt die mittlere Warteschlangenlänge L mit

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

an.[5] Hierbei sind

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

Für eine endliche 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.[6]

Durchschnittliche Wartezeit[Bearbeiten]

Die Zeit W bezeichne die durchschnittliche Zeit im System, dann gilt W=W'+\mu^{-1}, wobei W' 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 \operatorname{Var}(S)}{2(\mu-\lambda)} + \mu^{-1}.

Als Formel der durchschnittlichen Wartezeit folgt dann[7]

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

Einzelnachweise[Bearbeiten]

  1.  Felix Pollaczek: Über eine Aufgabe der Wahrscheinlichkeitstheorie. In: Mathematische Zeitschrift. 32, 1930, S. 64–100, doi:10.1007/BF01194620.
  2.  Alexander Chintschin: Mathematical theory of a stationary queue. In: Matematicheskii Sbornik. 39, Nr. 4, 1932, S. 73–84.
  3.  Lajos Takács: Review: J. W. Cohen, The Single Server Queue. In: Annals of Mathematical Statistics. 42, Nr. 6, 1971, S. 2162–2164, doi:10.1214/aoms/1177693087.
  4.  John Kingman: The first Erlang century — and the next. In: Queueing Systems. 63, Nr. 3–4, 2009, doi:10.1007/s11134-009-9147-4.
  5.  John Haigh: Probability Models. Springer, 2002, ISBN 1-85233-431-2, S. 192.
  6.  Robert B. Cooper, Shun-Chen Niu, Mandyam M. Srinivasan: In: Journal of Applied Mathematics and Stochastic Analysis. 11, Nr. 3, 1998, S. 355–368.
  7.  Peter G. Harrison, Naresh M. Patel: Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley, 1992, ISBN 0-201-54419-9, S. 228.