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 Bearbeiten
Die Formel wurde zunächst von Felix Pollaczek 1930 veröffentlicht und von Alexander Chintschin zwei Jahre später überarbeitet.
Durchschnittliche Warteschlangenlänge Bearbeiten
Die Formel gibt die mittlere Warteschlangenlänge mit
an. Hierbei sind
- die Ankunftsrate des Poisson-Stroms,
- die durchschnittliche Abfertigungszeit der Abfertigungszeitverteilung ,
- die Auslastung und
- die Varianz der Abfertigungszeitverteilung .
Für eine stabile Warteschlangenlänge ist es notwendig, dass gilt, da sonst die Anfragen schneller ankommen, als sie abgefertigt werden. Die Verkehrsdichte liegt zwischen und . Dies bezeichnet die durchschnittliche Leerlaufzeit des Bedienelements. Sollte die Ankunftsrate größer oder gleich der Bedienrate sein, geht die Wartezeit gegen unendlich. Der Varianzterm der Formel resultiert aus dem Wartezeitparadoxon.
Durchschnittliche Wartezeit Bearbeiten
Die Zeit bezeichne die durchschnittliche Zeit im System, dann gilt , wobei die durchschnittliche Wartezeit und die Bedienrate ist. Unter Verwendung von Littles Gesetz,
mit
- als durchschnittliche Warteschlangenlänge,
- als Ankunftsrate des Poissonstroms und
- als durchschnittliche Zeit im System
gilt
Als Formel der durchschnittlichen Wartezeit folgt dann
Einzelnachweise Bearbeiten
- Felix Pollaczek: Über eine Aufgabe der Wahrscheinlichkeitstheorie. In: Mathematische Zeitschrift. Band 32, 1930, S. 64–100, doi:10.1007/BF01194620.
- Alexander Chintschin: Mathematical theory of a stationary queue. In: Matematicheskii Sbornik. Band 39, Nr. 4, 1932, S. 73–84 (mathnet.ru).
- Lajos Takács: Review: J. W. Cohen, The Single Server Queue. In: Annals of Mathematical Statistics. Band 42, Nr. 6, 1971, S. 2162–2164, doi:10.1214/aoms/1177693087.
- John Kingman: The first Erlang century — and the next. In: Queueing Systems. Band 63, Nr. 3–4, 2009, doi:10.1007/s11134-009-9147-4.
- John Haigh: Probability Models. Springer, 2002, ISBN 1-85233-431-2, S. 192.
- Robert B. Cooper, Shun-Chen Niu, Mandyam M. Srinivasan: Some Reflections on the Renewal-Theory Paradox in Queueing Theory. In: Journal of Applied Mathematics and Stochastic Analysis. Band 11, Nr. 3, 1998, S. 355–368 (fau.edu [PDF; 196 kB]).
- Peter G. Harrison, Naresh M. Patel: Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley, 1992, ISBN 0-201-54419-9, S. 228.