SWZ  >  
Forschungsprojekte  >  
Warteschlangensimulation

Warteschlangensimulation

Warteschlangen treten in vielen Situationen in Produktion und Logistik auf. Sie entstehen immer dann, wenn der Kundenankunftsstrom nicht exakt mit der verfügbaren Bedienleistung abgeglichen werden kann:

  • Bei Inbound-Callcentern können die Zeitpunkte, an denen Kunden anrufen, nicht exakt vorhergesagt werden, so dass entweder Agenten auf Verdacht in Bereitschaft gehalten werden müssen oder aber Kunden gegebenenfalls warten müssen.
  • Die exakten Ankunftszeiten von Flugzeugen am Zielflughafen hängen von verschiedenen Witterungsbedingungen, vor allem von Windrichtung und Stärke, ab. Daher ist eine exakte Vorabfestlegung von Landezeitslots nur bedingt möglich bzw. müssen Flugzeuge immer wieder Warteschleifen fliegen oder ab am Boden auf eine Startfreigabe warten, wenn zuerst ein verspätet eintreffendes Flugzeug eine Landeerlaubnis erhalten muss.
  • In der variantenreichen industriellen Fertigung schwanken die Bedienzeiten an einzelnen Stationen in Abhängigkeit von den konkreten Eigenschaften des jeweiligen Werkstücks. Daher ist auch hier, insbesondere bei Losgröße 1, eine vollständig getaktete Fertigung nicht immer möglich. Soll dennoch eine hohe Auslastung der Maschinen sichergestellt werden, so kann dies nur über Pufferbestände vor den Anlagen erfolgen.

Generell sind Warteschlangen meist unerwünscht, da diese entweder zu unnötigen Zeitverlusten führen (Callcenter-Warteschlange), direkt unnötige Kosten zur Folge haben (Kerosinverbrauch durch Warteschleifen vor einer Landung) oder indirekt Kosten verursachen (Kapitalbindung durch Lagerbestände, lange und schlecht vorhersagbare Liefertermine). Ziel der Warteschlangentheorie ist es daher, Bediensysteme so auszulegen, dass die sich zusätzlichen Kosten z.B. durch mehr Bediener und die finanziellen Vorteile durch kurze Warteschlangen in einem optimalen Verhältnis befinden.

Warteschlangentheorie und Simulation

Die Warteschlangentheorie als Teilgebiet der Stochastik wurde vor über 100 Jahren von Agner Krarup Erlang begründet. Ursprüngliches Hauptanwendungsgebiet war die Personalbedarfsplanung in manuellen Telefonvermittlungstellen. Seit den 1950er Jahren traten vermehrt Fragen aus der industriellen Fertigung in den Fokus der Forschung. Auf Basis der analytischen Warteschlangentheorie können Wartezeitverteilungen für einfache Modelle exakt bestimmt werden und können Kenngrößen für komplexere Modelle und Warteschlangennetze approximiert werden.

Je komplexer die zu betrachtenden Modelle sind, desto weiter sinkt jedoch die Güte der jeweiligen Modelle. Mit dem Verfügbarwerden von immer mehr Rechenleistung rückt daher seit ca. den 1980er Jahren die Simulation von Warteschlangenmodellen immer mehr in den Mittelpunkt der Forschung. Mit Hilfe von Simulationsmodellen lassen sich prinzipiell alle denkbaren Modelle und Fragestellungen abbilden. Die Güte der Ergebnisse wird lediglich durch die verfügbare Rechenleistung limitiert. Bewegten sich die notwendigen Rechenzeiten im letzten Jahrhundert noch im Bereich von Stunden und Tagen, so sind heute einige Sekunden bis hin zu wenigen Minuten für die Simulation üblich. - Für einfache Modelle reicht bereits die Rechenleistung eines Smartphones aus.

Simulatoren

Im Rahmen der Forschung am SWZ sind die folgenden 4 Simulationswerkzeuge entstanden. Die drei Desktop-Programme stehen als Opensource zum kostenlosen Download zur Verfügung. Die Webapp steht zur kostenlosen Nutzung über die Webseiten des SWZ zur Verfügung:

Bei dem Mini Simulator handelt es sich um eine vollständig in Javascript implentierte Webapp, die in jedem modernen Browser (einschließlich Tablets und Smartphones) ausgeführt werden kann. In der App wird ein G/G/c/K+M-Modell abgebildet, d.h. ein Modell bestehend aus einer Warteschlange und einem Bedienschalter. Abgebildet werden können Batch-Ankünfte, Batch-Bedienungen, Ungeduld der Kunden, Wiederholer und Weiterleitungen.

Der Mini Callcenter Simulator bildet im Wesentlichen dasselbe G/G/c/K+G Modell ab, welches die Webapp beinhaltet. Er verfügt jedoch über wesentlich mehr Wahrscheinlichkeitsverteilungen, die für Zwischenankunfts-, Bedienzeit-, Nachbearbeitungszeit-, Wartezeittoleranz- und Wiederholabständeverteilung verwendet werden können. Auch werden wesentlich mehr Kenngrößen aufgezeichnet und stehen verschiedene Exportmöglichkeiten für die Simulationsergebnisse bereit. Des Weiteren können die Simulationsergebnisse direkt entsprechenden Erlang-C-Ergebnissen gegenübergestellt werden und es können Erklärungen angezeigt werden, warum an welchen Stellen Abweichungen auftreten.

Der Mini Callcenter Simulator benötigt eine Java-Laufzeitumgebung und wurde als Opensource veröffentlicht.

Der Callcenter Simulator ist darauf ausgerichtet, reale Callcenter-Systeme bestehend aus mehreren Teil-Callcentern, verschiedenen Anrufergruppen, verschiedenen Agentengruppen (mit verschiedenen Skill-Leveln und verschiedenen Schichtplänen), komplexen Zuweisungsregeln usw. abzubilden. Er kann unmittelbar zur Personalbedarfsplanung und zur Analyse von möglichen Steuerungsstrategien in großen Callcenter-Verbünden eingesetzt werden. Über die reine Simulation hinaus stellt das Programm auch Funktionen zur automatischen Optimierung der Agentenanzahlen zur Verfügung.

Der Callcenter Simulator benötigt eine Java-Laufzeitumgebung und wurde als Opensource veröffentlicht.

Der Warteschlangensimulator ermöglicht die Simulation beliebiger, komplexer Warteschlangennetze. Die Modelle werden im Warteschlangensimulator in Form von Fließbildern definiert. Optional kann während der Simulation der Modelle eine Animation, die die Bewegung der Kunden durch das System verdeutlich, angezeigt werden. Zur automatisierten Untersuchung von verschiedenen Modellen können automatisch Parameterreihen erstellt werden und auch ein Optimierer steht zur Verfügung. Des Weiteren können während der Simulation von Modellen direkt externe Datenquellen angebunden werden und auch (Teil-)Ergebnisse direkt an externe Programme (z.B. Datenbanken) übergeben werden.

Der Warteschlangensimulator benötigt eine Java-Laufzeitumgebung und wurde als Opensource veröffentlicht.

Kontakt

Dr. Alexander Herzog

Geschäftsführer des Simulationswissenschaftlichen Zentrums
Arbeitsgruppe Stochastische Modelle in den Ingenieurwissenschaften
Institut für Mathematik
Technische Universität Clausthal

Raum 313, Arnold-Sommerfeld-Straße 6, 38678 Clausthal-Zellerfeld
Raum 115, Erzstraße 1, 38678 Clausthal-Zellerfeld
E-Mail: Alexander.Herzog@tu-clausthal.de
Telefon: +49 5323 72-2966, Fax: +49 5323 72-2304