Pollaczek-Chintschin-Formel

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 | Quelltext bearbeiten]

Die Formel gibt die mittlere Warteschlangenlänge mit

an.[5] 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.[6]

Durchschnittliche Wartezeit

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

.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Felix Pollaczek: Über eine Aufgabe der Wahrscheinlichkeitstheorie. In: Mathematische Zeitschrift. Band 32, 1930, S. 64–100, doi:10.1007/BF01194620.
  2. Alexander Chintschin: Mathematical theory of a stationary queue. In: Matematicheskii Sbornik. Band 39, Nr. 4, 1932, S. 73–84 (mathnet.ru).
  3. 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.
  4. 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.
  5. John Haigh: Probability Models. Springer, 2002, ISBN 1-85233-431-2, S. 192.
  6. 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]).
  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.