Mit Hilfe der Warteschlangentheorie lassen sich Prozesse untersuchen, bei denen Ankünfte und/oder Bedienungen gewissen zeitlichen Schwankungen unterliegen:

• In einem Kundenservice-Callcenter treffen Anrufe zu zufälligen Zeitpunkten ein. Die Bedienungen der Kunden dauern ebenfalls unterschiedlich lange.
• An einem Flughafen treffen Flugzeug abhängig von den jeweiligen Witterungsverhältnissen (insbesondere abhängig von Windgeschwindigkeit und -richtung) meist etwas früher oder etwas später als geplant ein.
• Bei einer Werkstattfertigung lässt sich die genaue Bedienzeit (insbesondere an Stationen mit Handarbeit) nicht exakt angeben, so dass die Durchlaufzeiten durch die Produktion schwanken.

Sind Ankünfte und Bedienungen getaktet (d.h. trifft z.B. alle exakt 60 Sekunden ein Kunde ein und dauert eine Bedienung immer exakt 59 Sekunden), so entstehen keine Warteschlangen. In allen anderen Fällen kann es zu temporären Staus kommen. Die Warteschlangentheorie liefert Erkenntnisse darüber, wie lang die entstehenden Warteschlangen im Mittel sind, wie lange Kunden im Mittel warten müssen und auch, wie die Verteilung der Wartezeiten ausfällt.

Auf dieser Basis können die Betreiber der Systeme Optimierungen vornehmen. So wird im Callcenter-Bereich häufig angestrebt, dass 80% der Anrufer nicht länger als 20 Sekunden warten müssen. Bei bekannter mittlerer Anzahl an Anrufern pro Minute und bekannter mittlerer Bediendauer ist nun die notwendige Anzahl an Bedienern gesucht, um diese Vorgaben zu erfüllen.

Aktuelle Untersuchungen zeigen, dass Werkstücke auf dem Weg durch eine Produktion typischerweise 75% der gesamten Durchlaufzeit warten, d.h. eine Verkürzung der mittleren Wartezeiten hat einen erheblichen Einfluss auf die Gesamtdurchlaufzeit.

In der Warteschlangentheorie spricht man stets von „Kunden“ und „Bedienern“. Bei den Kunden kann es sich konkret z.B. um Flugzeuge handeln und bei den Bedienern dann um Landebahnen usw.

Ankünfte werden in Kunden pro Stunde, Kunden pro Minute usw. gemessen, d.h. es wird betrachtet, wie viele Kunden im Mittel in einer bestimmten Zeitspanne eintreffen. Statt mit der mittleren Anzahl an Ankünften zu arbeiten, wird meist die mittlere Zeit zwischen zwei Ankünften, die sogenannte mittlere Zwischenankunftszeit E[I] verwendet. Je kleiner E[I] ist, desto mehr Kunden treffen pro Zeiteinheit ein.

Für die Untersuchung eines Warteschlangensystems kommt es darauf an, wie gleichmäßig die Kunden eintreffen. Trifft alle exakt 60 Sekunden ein Kunde ein und dauert eine Bedienung jeweils exakt 59 Sekunden, so muss niemand warten. Beträgt der Abstand zwischen zwei Ankünften jedoch einmal 30 und einmal 90 Sekunden (also im Mittel immer noch 60 Sekunden), so wird es zu Wartezeiten kommen. Daher ist es hilfreich, wenn auch die Standardabweichung der Zwischenankunftszeiten Std[I] bekannt ist. Wenn die Kunden die Warteschlangen nicht einsehen können und sich nicht absprechen, so gilt Std[I]=E[I]. Bei getakteten Ankünften gilt Std[I]=0.

Alternativ zur mittleren Zwischenankunftszeit E[I] wird auch häufig die Ankunftsrate λ angegeben. Sie ist der Kehrwert der mittleren Zwischenankunftszeit. D.h. eine kurze mittleren Zwischenankunftszeit entspricht einem hohen Wert von λ:

Einer mittleren Zwischenankunftszeit von 2 Minuten entspricht also beispielsweise eine Ankunftsrate von ½ Kunden pro Minute.

Die Bedienungen werden über die mittlere Bediendauer E[S] charakterisiert. Je größer E[S] ist, desto länger dauert eine Bedienung.

Auch hier gilt: Je gleichmäßiger die Bedienungen sind, desto weniger Wartezeiten entstehen. Daher ist es auch hier von Vorteil, wenn die Streuung der Bediendauern in Form der Standardabweichung der Bediendauern Std[S] bekannt ist.

Analog zur Ankunftsrate definiert man die Bedienrate µ als den Kehrwert der mittleren Bediendauer. Je längere die mittlere Bediendauer, desto kleiner ist µ:

Beträgt die mittlere Bediendauer z.B. 3 Minuten, so entspricht dies einer Bedienrate von 1/3 Kunden pro Minute.

Die Bedienreihenfolge gibt an, welcher der wartenden Kunden als nächstes bedient werden soll. Bilden die Kunden eine klassische Warteschlange, so wird der Kunde, der bereits am längsten gewartet hat, d.h. ganz vorne in der Schlange steht, als nächstes bedient. Man spricht dann von der First come first serve (FCFS) bzw. First in first out (FIFO) Bedienregel. Handelt es sich bei den Kunden jedoch um (schwere) Werkstücke, die gestapelt wurden, so kann das unterste Werkstück diesem Stapel ggf. nicht direkt entnommen werden, d.h. es wird oben auf den Stapel aufgelegt und auch von oben gezogen. In diesem Fall gilt die Last come first serve (LCFS) bzw. die Last in first out (LIFO) Bedienregel.

LIFO führt zu stark unterschiedlichen Durchlaufzeiten einzelner Werkstücke durch die Produktion. – Ist ein Werkstück erst einmal ganz unten im Stapel, kommt es dort so schnell nicht mehr weg. Um die Durchlaufzeiten möglichst gut vorhersehbar zu gestalten, sollte daher wann immer möglich auf LIFO verzichtet werden.

Treffen Kunden verschiedener Typen an einer Warteschlange ein, so kann außerdem die Auswahl des jeweils als nächstes zu bedienenden Kunden über eine Prioritätsformel erfolgen.

Im einfachsten Fall werden Ankünfte und Bedienungen lediglich über Ankunfts- und Bedienrate beschrieben, d.h. ein jeweils komplexer Prozess wird durch nur eine einzige Zahl charakterisiert. Trifft alle exakt 2 Minuten ein Kunde am System ein, so ergibt sich eine mittlere Zwischenankunftszeit von 2 Minuten bzw. eine Ankunftsrate von 0,5 Kunden pro Minute. Beträgt die Zwischenankunftszeit nun jedoch im Wechsel 1 und 3 Minuten, so gilt genauso, dass die mittlere Zwischenankunftszeit 2 Minuten beträgt, allerdings dürfte es deutlich schwieriger werden, einen solchen Kundenankunftsstrom ohne Wartezeiten zu bedienen.

Daher ist es sinnvoll, nicht nur die mittleren Zeitdauern zu berücksichtigen, sondern weitere Kenngrößen, wie z.B. die Streuung (ausgedrückt über die Standardabweichung oder den Variationskoeffizient) zu verwenden.

In der analytischen Warteschlangentheorie kann nur die Exponentialverteilung verwendet werden. Bei dieser gilt stets Erwartungswert=Standardabweichung. Ist dies in dem abzubildenden realen System nicht der Fall, so bildet das Modell die Realität nicht adäquat ab. In Simulationsmodellen kann hingegen praktisch jede beliebe Wahrscheinlichkeitsverteilung verwendet werden. Typisch sind folgende:

• Deterministisch: Die Kunden treffen alle mit exakt demselben Abstand ein bzw. die Bedienungen dauern alle exakt gleich lange. Es ist also Standardabweichung=0.
• Exponentialverteilung: Es gilt Standardabweichung=Erwartungswert. Dies stellt eine sehr hohe Streuung dar. Bei Bedienprozessen ist die Standardabweichung meist kleiner als der Erwartungswert der Bedienzeiten. Bei den Zwischenankunftszeiten gilt jedoch Standardabweichung=Erwartungswert, wenn die Kunden unabhängig voneinander eintreffen bzw. die Warteschlangen nicht einsehen können. Die Zwischenankunftszeiten an einem Kundenservice-Callcenter sind beispielsweise exponentiell verteilt.
• Log-Normal- und Gamma-Verteilung: Diese beiden Verteilungen eignen sich gleichermaßen zur Abbildung von Bedienzeiten. Bei beiden sind Erwartungswert und Standardabweichung individuell einstellbar. Die Möglichkeit, diese Verteilungen verwenden zu können, stellt einen der großen Vorteile der Simulation gegenüber den analytischen Formeln dar. In anderen Wissenschaftsgebieten (z.B. der Finanz- und Versicherungsmathematik) muss zwischen den beiden Verteilungen genau unterschieden werden; die Log-Normalverteilung ist heavy tailed, die Gamma-Verteilung nicht. Für die Abbildung seltener Großschadensereignissen ist diese Eigenschaft von großer Bedeutung. Für die Modellierung von Bediendauern ist sie jedoch unerheblich.

Zusammenfassend gilt: Für die Zwischenankunftszeiten eignet sich in vielen Fällen die Exponentialverteilung (und es muss dann nur die mittlere Zwischenankunftszeit eingestellt werden). Für die Bedienzeiten sollte die Log-Normal- oder die Gamma-Verteilung verwendet werden. Hier müssen dann die mittlere Bediendauer und auch die Standardabweichung der Bediendauern angegeben werden.

Ist die Standardabweichung der Bediendauern nicht bekannt, so werden meist Werte im Bereich 0,2x bis 0,8xErwartungswert verwendet. Je höher der menschliche Einfluss auf die Bediendauern ist, desto höher sollte die Standardabweichung gewählt werden bzw. je stärker der Prozess automatisiert ist, desto niedriger sollte die Standardabweichung gewählt werden.

Warteschlangenmodelle lassen sich durch die sogenannte Kendall-Notation beschreiben. In der einfachsten Form hat diese Beschreibung folgendes Aussehen:

Zwischenankunftszeiten / Bedienzeiten / Anzahl Bediener / Warte- und Bedienraumgröße

Für die Zwischenankunfts- und die Bedienzeiten wird „M“ für die Exponentialverteilung „E_k“ für die Erlang-k-Verteilung, „D“ für deterministische Werte und „G“ für eine allgemeine, d.h. nicht explizit bekannte Verteilung, eingesetzt.

Beispiele:

• M/M/1/∞
  beschreibt ein Bediensystem mit exponentiell verteilten Zwischenankunfts- und Bedienzeiten, einem Bediener und einem unbeschränkten Warte- und Bedienraum.
• M/G/5/5
  beschreibt ein Bediensystem mit exponentiell verteilten Zwischenankunftszeiten und Bedienzeiten, die einer nicht näher bekannten Verteilung unterliegen (d.h. nur E[S] und Std[S] bekannt sind). Das System verfügt über 5 Bediener. Der Warte- und Bedienraum weist 5 Plätze auf. Da wir auch genau 5 Bediener haben, heißt das, dass es keine Warteschlange geben kann. Trifft ein neuer Kunde ein, während alle Bediener belegt sind, so wird dieser abgewiesen.

Zur Beschreibung komplexerer Modelle gibt es zahlreiche Erweiterungen der Kendall-Notation.

Die Auslastung ρ ist ein Wert zwischen 0 und 1. Sie ergibt sich, wenn die Arbeitslast durch die Anzahl an Bedienern geteilt wird:

Während derjenige, der die Bediener bezahlen muss bzw. die Bedienstationen kaufen muss, sich eine hohe Auslastung wünscht (da so die Stückkosten niedriger ausfallen), bedeuten aus Kundensicht hohe Werte von r im Mittel lange Wartezeiten.

In einem Warteschlangensystem ohne Warteabbrecher oder sonstiger Besonderheiten bedeutet die Voraussetzung ρ<1, dass λ<cµ sein muss.

Die mittlere Wartezeit E[W] der Kunden ergibt sich bei einfachen Modellen durch eine analytische Formel (siehe unten) oder bei komplexeren Modellen durch eine Simulation.

Die gesamte Zeitdauer, die ein Kunde an einer Bedienstation verbringt, setzt sich aus der Wartezeit und der Bedienzeit zusammen. Für die mittlere Verweilzeit E[V] gilt:

Die mittlere Verweilzeit ist die Summe aus der mittleren Wartezeit E[W] und der mittleren Bediendauer E[S].

Im industriellen Kontext wird die Verweilzeit auch als die Durchlaufzeit bezeichnet. Ziel ist es üblicherweise, die Durchlaufzeit zu minimieren. Da die notwendigen Bedienzeiten meist durch die Arbeitsgeschwindigkeit der jeweiligen Maschinen fest vorgegeben sind, bedeutet dies praktisch, dass die vermeidbaren Wartezeiten reduziert werden sollen.

Unter der Annahme, dass die Maschinen bei langen Warteschlangen nicht schneller oder langsamer arbeiten, also die Wartezeiten und die Bediendauern stochastisch unabhängig sind, ist auch die Streuung der Durchlaufzeiten gleich der Summe aus der Streuung der Warte- und der Bedienzeiten. Eine hohe Streuung der Durchlaufzeiten bedeutet, dass die Fertigstellungstermine einzelner Produkte nur schlecht prognostiziert werden können, d.h. vorab zugesagte Liefertermine häufig nicht eingehalten werden können. Folglich will man die Streuung der Durchlaufzeiten möglichst geringhalten. Da die Streuung der Bedienzeiten meist ebenso wenig beeinflusst werden kann wie die mittlere Bediendauer, bedeutet dies, dass die Streuung der Wartezeiten minimiert werden soll.

Die Abkürzung „WIP“ steht für „Work units in process“, d.h. die Anzahl an Werkstücken in dem Prozess (wartend oder in Bedienung). Die mittlere Anzahl an Werkstücken bzw. Kunden im System wird mit E[N] bezeichnet.

Interessiert man sich nur für die mittlere Anzahl an wartenden Kunden, so verwendet man das Symbol E[N_Q].

Die Formel von Little stellt einen Zusammenhang zwischen der Anzahl an Kunden im System und der mittleren Verweilzeit bzw. zwischen der Anzahl an wartenden Kunden und der mittleren Wartezeit her:

Das bedeutet: Sind die Ankunftsrate λ und die mittlere Anzahl an Werkstücken im System E[N] bekannt, so lässt sich die mittlere Durchlaufzeit direkt berechnen:

Die Verweilzeit setzt sich additiv aus Warte- und Bedienzeit zusammen:

Setzt man in diese Formel für E[V] und E[W] die Terme aus der umgestellten Formel von Little ein, multipliziert mit λ und ersetzt λ/µ durch a, so ergibt sich:

D.h. die mittlere Warteschlangenlänge und die mittlere Anzahl an Kunden im System unterscheiden sich genau um a bzw. im Mittel befinden sich a Kunden in Bedienung.

Sind λ, µ und c vorgegeben, so reicht es aus, eine der weiteren Größen E[W], E[V], E[NQ] oder E[N] zu kennen, um die jeweils anderen Größen berechnen zu können. Allerdings ist genau diese Ermittlung einer der vier Größen in den meisten Fällen nicht einfach. 

Für M/M/1-Modelle, d.h. bei exponentiell verteilten Zwischenankunfts- und Bedienzeiten und einem Bediener, lassen sich die Kenngrößen noch leicht berechnen. Es gelten:

Sind die Zwischenankunftszeiten und die Bedienzeiten exponentiell verteilt und existieren c≥1 Bediener in dem System, so handelt es sich gemäß der Kendall-Notation um ein M/M/c-Modell. Für dieses lässt sich zunächst P(W≤t), d.h. die Wahrscheinlichkeit, dass ein Kunde höchstens t≥0 Sekunden warten muss, mit Hilfe der Erlang-C-Formel berechnen:

mit

Daraus lassen sich dann auch die anderen Kenngrößen ableiten:

Die Erlang-C-Formel kann auch noch um ungeduldige Kunden (d.h. mögliche Warteabbrecher) erweitert werden. Auf einen Abdruck dieser Formel soll an dieser Stelle verzichtet werden. Unter folgender Adresse steht ein Erlang-C-Online-Rechner bereit:

https://www.mathematik.tu-clausthal.de/interaktiv/warteschlangentheorie/erlang-c/

Es werden dort auch Excel-, OpenOffice/LibreOffice-, R-, Python- und Javascript-Dateien bereitgestellt, um die Erlang-Formeln in eigenen Projekten zu nutzen.

Sind die Zwischenankunfts- oder die Bedienzeiten nicht mehr exponentiell verteilt, d.h. gelten nicht mehr E[I]=Std[I] und E[S]=Std[S], so lassen sich die Modelle für c>1 bereits nicht mehr exakt lösen. Für diesen Fall steht die Allen-Cunneen-Näherungsformel zur Verfügung.

Die Allen-Cunneen-Näherungsformel basieren auf der Erlang-C-Formel und erweitern diese um einen Korrekturfaktor, um die Abweichung von Std[I] und Std[S] von den Erlang-C-Werten so gut wie möglich zu kompensieren. Wenn E[NQ]M/M/c der Erwartungswert für die Warteschlangenlänge im Erlang-C-Fall ist, gelten folgende Näherungen:

Dabei sind SCV[I] und SCV[S] die quadrierten Variationskoeffizienten der Zwischenankunfts- bzw. der Bedienzeiten:

Die Allen-Cunneen-Näherungsformel ist entstanden, in dem viele Simulationen (damals auf Großrechnern und unter Inkaufnahme langer Laufzeiten) durchgeführt wurden und die Ergebnisse den Erlang-C-Ergebnissen gegenübergestellt wurden. Es wurde dann der von Std[I] und Std[S] abhängige Korrekturfaktor (SCV[I]+SCV[S])/2 so entworfen, dass die Simulationsergebnisse möglichst gut (aber nicht perfekt) widergegeben werden.

Da die damaligen Großrechner-Wochen heute Smartphone-Sekunden sind, lohnt es sich nur noch bedingt, diese Formeln (die nur jeweils Näherungen liefern) zu verwenden.

Mit Simulationsmethoden lassen sich prinzipiell alle gewünschten Modelleigenschaften eines Warteschlangennetzes abbilden. Im Gegensatz zu Näherungsformeln handelt es sich dann auch um jeweils (im Rahmen der gewählten Simulationslaufzeit) exakte Ergebnisse.

Die Laufzeiten für viele Modelle bewegen sich im einstelligen Sekundenbereich, so dass frühere Aussagen, dass Simulationen zu langsam seien und lieber eine (ungenaue, aber schnelle) Näherungsformel verwendet werden sollte, heute überholt sind.

Bei dem im Folgenden vorgestellten Web-Diensten bzw. Desktop-Programmen handelt es sich durchgängig um kostenlose Angebote bzw. Opensource-Software.

Der Warteschlangensimulator stellt einen sehr leichten Einstieg in die Simulation von Warteschlangensysteme dar: Um die Mathematik kümmert sich der Simulator – als Nutzer muss man nur das Modell als Fließbild aufmalen und kann sich dann zusehen, wie die kleinen virtuellen Kunden in einer Animation durch das System laufen. Auch die gesamte Statistikerfassung erfolgt automatisch im Hintergrund.

Im Warteschlangensimulator stehen auch direkt eine ganze Reihe von Beispielmodellen zur Verfügung, so dass die Animation eines Modells direkt nach der Installation starten kann.

Installation des Warteschlangensimulators:

1. Es wird eine Java-Laufzeitumgebung in der Version 8 oder höher benötigt, z.B. gerne die neuste Java-LTS-Version der Eclipse-Foundation.
2. Der Warteschlangensimulator steht als Installer oder als zip-Archiv zum Download zur Verfügung. Der Installer kann den Simulator mit oder auch ohne Admin-Rechte installieren. Das zip-Archiv kann an einem beliebigen Ort entpackt werden und der Simulator ist sofort einsatzbereit.

• Dr. Alexander Herzog