Warteschlangentheorie

Warteschlangenprobleme kommen in den verschiedensten Anwendungen vor. Der Artikel gibt einen Überblick über das Grundmodell der Warteschlangentheorie, seine Varianten und Bezeichnungen. Die wichtigsten Kenngrößen werden definiert und ihre Beziehungen untereinander erläutert.

Die Warteschlangentheorie befasst sich mit der Beschreibung und Bewertung von Bedienungssystemen. Zur Beschreibung dient ein einfaches, in Abbildung 1 dargestelltes Grundmodell. Es besteht aus dem Bedienungsschalter, der über eine oder mehrere parallel arbeitende gleichartige Arbeitsplätze bzw. Maschinen verfügt, und aus einem Warteraum. Die Kunden treffen einzeln und zu zufälligen Zeitpunkten vor dem Bedienungssystem ein. Ein neu ankommender Kunde wird bedient, sofern mindestens eine der Maschinen frei ist, andernfalls muss er sich in die Warteschlange einreihen. Die Zeit zwischen zwei aufeinanderfolgenden Ankünften wird Zwischenankunftszeit und die Zeit für einen Bedienungsvorgang Bedienungszeit genannt.

Abbildung 1.: Grundmodell eines Bedienungssystems

Die Begriffe Kunde und Schalter können in der Praxis unterschiedliche Bedeutungen haben. Die ersten Anwendungen bezogen sich auf die Telekommunikationstechnik; der dänische Ingenieur und Mathematiker A.K. Erlang begründete die Warteschlangentheorie mit einer Publikation über die Dimensionierung von Fernsprechvermittlungsstellen, in diesem Fall werden die eingehenden Telefonanrufe durch freie Leitungen „bedient“. Mittlerweile werden durch Warteschlangentheorie auch andere Bereiche erschlossen: Computerprogramme, die in einem Rechnerverbund zirkulieren, Werkstücke, die von einer Maschine bearbeitet werden sollen, Fahrzeuge, die an einer Verkehrsampel warten, Flugzeug-Rotationen, die durch einen Flugplan koordiniert werden, usw. In allen Fällen geht es um die Beseitigung von Engpässen, die Verkürzung von Durchlaufzeiten  bzw. die Reduzierung von Warteschlangen.

Um praktische Probleme realitätsnah modellieren zu können, muss das Grundmodell auf vielfältige Weise variiert werden:

• Die Kunden werden nicht einzeln, sondern gruppenweise bedient (Systeme mit Gruppenbedienung)

• Einige Kunden verlassen das System, bevor sie bedient worden sind (Wartesysteme mit Zeitbeschränkungen)

• Nicht alle Bedienungsgeräte stehen jedem Kunden zur Verfügung (Bedienungssysteme mit eingeschränkter Erreichbarkeit)

• Einige Kunden scheuen sich, in das Bedienungssystem einzutreten, weil ihnen die Warteschlange zu lang erscheint (Wartesysteme mit ungeduldigen Kunden)

• Ein Kunde höherer Priorität verdrängt einen Kunden niedrigerer Priorität aus dem Bedienungsprozess (Bedienungssysteme mit Prioritätensteuerung)

Die Bedienungsregel legt fest, in welcher Reihenfolge die wartenden Kunden abgefertigt werden sollen. Gebräuchlich sind:

FIFO (FCFS) First In, First Out (First Come, First Served). Die Bedienung erfolgt in der Reihenfolge der Ankünfte.
LIFO (LCFS) Last In, First Out (Last Come, First Served). Die Bedienung erfolgt in umgekehrter Reihenfolge der Ankünfte.
SIRO Selection In Random Order. Der nächste Kunde wird zufällig ausgewählt.
Non-preemptive Priority relative Priorität. Manche Kunden werden gegenüber anderen Kunden vorrangig behandelt. Der laufende Bedienungsprozess wird jedoch nicht unterbrochen.
Preemptive Priorität absolute Priorität. Besitzt der neu ankommende Kunde gegenüber den anderen Kunden im System eine höhere Priorität, so wird der laufende Bedienungsprozess unterbrochen und mit der neuen Forderung fortgesetzt. Die alte Forderung wird zurückgestellt.
RR Round Robin: Jeder Kunde kann den Bediener jeweils nur für ein bestimmtes Zeitintervall in Anspruch nehmen. Kunden, deren Abfertigung mehr Zeit benötigt, müssen sich deshalb mehrmals hintereinander in die Warteschlange einreihen.

Zur symbolischen Kennzeichnung von Bedienungssystemen haben D.G. Kendall und B.W. Gnedenko die Notation

A/B/c/m

eingeführt. Die Buchstaben A und B markieren hierbei den Verteilungstyp der Zwischenankunfts- und Bedienungszeiten. Der Buchstabe c steht für die Anzahl der parallelen Bediener, m bezeichnet die Kapazität des Warteraums.

Für den Verteilungstyp sind folgende Abkürzungen gebräuchlich:

D    Deterministische Verteilung,
M    Exponentialverteilung,
Ek    Erlang-Verteilung mit dem Parameter k (k=1,2,…),
Hk    Hyperexponentialverteilung mit dem Parameter k (k=1,2,…),
PH    Phasen-Typ-Verteilung,
G    Allgemeine Verteilung.

Zur Leistungsbewertung von Bedienungssystemen werden folgende Prozesse herangezogen:

• Die Anzahl der Kunden im System

  N_t. Dieser Prozess gibt an, wie viele Kunden sich zur Zeit

  t im Bedienungssystem (einschließlich Schalter) aufhalten.

• Der Prozess der aufeinanderfolgenden Verweilzeiten

  V_n, die Zufallsvariable

  V_n bezeichnet die Zeit, die der

  n-te Kunde im Bedienungssystem verweilt.

Zwischen diesen Größen besteht der folgende Zusammenhang (Formel von Little):

wobei lambda die mittlere Ankunftsrate pro Zeiteinheit bezeichnet. Mit anderen Worten: Die mittlere Verweilzeit im System erhält man, indem man die durchschnittliche Anzahl von Kunden im System durch die mittlere Ankunftsrate pro Zeiteinheit dividiert.

Literatur

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