Warteschlangentheorie

Die Warteschlangentheorie (oder Bedienungstheorie) ist ein Teilgebiet der Wahrscheinlichkeitstheorie bzw. des Operations Research und somit ein Beispiel für angewandte Mathematik. Sie beschäftigt sich mit der mathematischen Analyse von Systemen, in denen Aufträge von Bedienungsstationen bearbeitet werden, und gibt Antwort auf die Fragen nach den charakteristischen Größen wie der Stabilität des Wartesystems, der Anzahl der Kunden im System, ihrer Wartezeit usw. Sie unterstützt unter anderem Managemententscheidungen über den Personaleinsatz und den Abfertigungsprozess und hilft ein Performance-Measurement-System auszubauen. Ihre Anwendung reicht von Computern, Telekommunikationssystemen, Verkehrssystemen über Logistik bis zu Fertigungssystemen.

Systematik

Grundsätzlich besteht ein Wartesystem aus einem Bedienbereich, in dem ein oder mehrere Bedienungsstationen Aufträge bearbeiten, und einem Warteraum, in dem eintreffende Aufträge bei aktuell nicht freien bzw. verfügbaren Serviceeinheiten auf die Bedienung warten. Abgefertigte Aufträge verlassen das System. Weitere für die Warteschlangentheorie wichtige Begriffe sind die Warteschlangendisziplin (wer wird wann bedient, d. h. priorisiert?), Systemkapazität (maximale Größe des Warteraumes), die Anzahl der Warteschlangen und die Zusammensetzung der Bedienstufen.

Unter Annahmen über den Ankunftsprozess (z. B. als Poisson-Prozess) und die Bediendauer (z. B. exponentialverteilt) liefert die Warteschlangentheorie dann Aussagen über interessante Leistungsgrößen wie die mittlere Warteschlangenlänge, die Anzahl der Kunden im Wartesystem, die mittlere Wartezeit oder ähnliches.

Von David George Kendall wurde eine einheitliche Notation zur Beschreibung der Wartesysteme entwickelt, die Kendall-Notation. Wartesysteme ohne Warteraum werden als Verlustsysteme bezeichnet.

Zentrale Aussagen sind das Gesetz von Little, Erlang B und Erlang C wie auch der Satz von Gordon–Newell.

Anwendungsbereiche

Die Warteschlangentheorie wird bei der Analyse von Computern, Telekommunikationssystemen (Callcenter), Verkehrssystemen (Verkehrsfluss), Logistik und Fertigungssystemen eingesetzt. Je nach Anwendungsbereich haben die abstrakten Begriffe Auftrag und Bedienungsstation sehr unterschiedliche Bedeutungen.

Computer

Auftrag = Task; Bedienungsstation = CPU

Telekommunikation

Auftrag = Telefonanruf; Bedienungsstation = Telefonleitung

Verkehrssystem

Auftrag = Autofahrer; Bedienungsstation = Tankstelle

Fertigung

Auftrag = zu montierende Maschine; Bedienungsstation = Monteur

Mehrere solcher (einfacher) Wartesysteme können zu sogenannten Warteschlangennetzen zusammengesetzt werden. Zur mathematischen Analyse von Wartesystemen wurden verschiedene Ansätze entwickelt. Dazu gehören Markov-Ketten, Petri-Netze und die ereignisdiskrete Simulation.

Geschichte

Die erste Anwendung der Warteschlangentheorie erfolgte durch den Mathematiker Agner Krarup Erlang 1909 zur Dimensionierung von Telefonvermittlungsanlagen (The Theory of Probabilities and Telephone Conversations). In den 1930er Jahren ermöglichte die Pollaczek-Khintchine-Formel weitere Vereinfachungen der Theorie. Spätere, bedeutende Beiträge kamen von David George Kendall, Dennis Victor Lindley, James R. Jackson, Gordon, Gordon F. Newell, Felix Pollaczek, Carl Adam Petri, Leonard Kleinrock und Paul Ehrenfest. Durch die Entwicklung von Computern und Computernetzwerken gewann die Forschung in diesem Bereich auch an Bedeutung.

Literatur

• Volker Rausch: Bediensysteme der Instandhaltung. Eine Verknüpfung von mathematisch-statistischen Methoden und der Bedientheorie. SVH, Saarbrücken 2010, ISBN 978-3838114927
• Natalja N. Amossova: Bedienungstheorie : Eine Einführung. Teubner, Leipzig 1986, ISBN 3-322-00309-4
• Heinz Häfner: Ein Warteschlangenansatz zur integrierten Produktionsplanung. Physica-Verlag, Heidelberg (zugleich Dissertation U Mannheim) 1992, ISBN 3-7908-0579-3
• Uwe Kiencke: Ereignisdiskrete Systeme : Modellierung und Steuerung verteilter Systeme. 2. überarb. und erw. Auflage, Oldenbourg Verlag, München 2006, ISBN 978-3-486-58011-2
• Markus Sommereder: Modellierung von Warteschlangensystemen mit Markov-Ketten : Grundlagen, Konzepte, Methoden. Verlag Dr. Müller, Saarbrücken (2008), ISBN 978-3-8364-5697-5
• Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S.: Queuing Networks and Markov Chains. Wiley & Sons: Hoboken, New Jersey, 2006.
• Gross, Donald; Harris, Carl M.: Fundamentals of Queuing Theory, Wiley & Sons: New York, 1994.
• Edward D. Lazowska, John Zahorjan, G. Scott Graham, Kenneth C. Sevcik: Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice-Hall, Inc, 1984 (http://www.cs.washington.edu/homes/lazowska/qsp/).

Siehe auch

• Wartezeitparadoxon
• Zufallsverkehr, Erneuerungstheorie, Erlang (Einheit), Netflow, Personalbedarfsplanung, Servicelevel

Weblinks

• Skriptum zur Warteschlangentheorie http://www.ci.tuwien.ac.at/~grill/download/ws.zip
• Einführung mit Warteschlangenrechner und Anwendungen http://www.stochastik.tu-clausthal.de/Presse/Schulen
• Unterlage zur Warteschlangentheorie: http://www.telecomm.at/documents/Warteschlangen.pdf