Warteschlangentheorie

Grundlagen

Warteschlangen können in praktisch allen Systemen mit beschränkten Ressourcen auftreten. Man denke z.B. an einen Supermarkt und die dortigen Kassenwarteschlangen. In Simulationsmodellen sind sie sehr häufig vertreten, da oft das Verhalten des Systems unter Knappheitsbedingungen untersucht werden soll. Es ist zwar theoretisch möglich, unendliche Ressourcen oder Kapazitäten zu unterstellen, jedoch ist dies in praxi nicht akzeptabel. Alleine Kostenüberlegungen oder Raumbedarfe stehen diesen Konstrukten entgegen.
Es kommt also immer wieder vor, daß ein Entity vor einem Modellbestandteil ?warten? muß, ehe seine Bearbeitung beginnen kann. Diese Warteschlangen geben zum einen Aufschluß über die Problembereiche im untersuchten System, müssen zum anderen aber auch effektiv verwaltet werden.

Analytisches Vorgehen

Im Rahmen der analytischen Betrachtung von Warteschlangensystemen wird sich der Kendall-Notation bedient. Diese Notation in der Form: A/B/C/D/E/F
bedeutet im Einzelnen:
A: Ankunftsprozeß (Zwischenankunfszeitverteilung)

B: Servicerate (Bedienprozeß, Länge der Bedienung)
Siehe A
C: Anzahl der parallelen Bedienstellen, die zu einer Warteschlange gehören
D: Maximal zulässige Warteschlangenlänge
E: Anzahl der unterschiedlichen Objekte (wird oft weggelassen)
F: Warteschlangendisziplin (Auswahlprinzip aus der Warteschlange)
z.B. FIFO. LIFO, SIRO (Service In Random Order), PRI (Priority)

Vielfach werden auch verkürzte Formen wie M/M/1 oder M/M/S als Standard verwendet. Als Beispiel betrachten wir das System M/M/1/¥/¥/FIFO:
Die Ankunftsrate sei exponentialverteilt mit dem Parameter 1/l, die Servicerate sei ebenfalls exponentialverteilt mit dem Parameter 1/m. Des weiteren bezeichne der Systemzustand Sj die Anzahl der Objekte j im System S, und Pj die Wahrscheinlichkeit des Zustandes Sj. Dann kann man ableiten, daß im stationären Zustand gilt:

Die Notation r=l/m heißt Verkehrsdichte. Im stationären Fall gilt r<1. Daher gilt:
und bezeichnet die Wahrscheinlichkeit, daß j Objekte im System sind (zum Beweis siehe einschlägige Fachliteratur über die Warteschlangentheorie).
Die mittlere Anzahl von Objekten im System ist:

und
Für die mittlere Anzahl von Objekten in der Warteschlange gilt dann:

Obige Formeln ergeben z.B. die folgende Tabelle:

Es ergibt sich also für eine M/M/1/¥/¥/FIFO-Warteschlange:

-Ankunftsrate

-Servicerate
-Wahrscheinlichkeit, daß keine Objekte im System sind:

-Wahrscheinlichkeit, daß n Objekte im System sind:

-Wartewahrscheinlichkeit (Verkehrsdichte):

-Mittlere Anzahl von Objekten im gesamten System:

-Mittlere Anzahl Objekte in der Warteschlange:

Mittlere Wartezeit im gesamten System:

Mittlere Wartezeit in der Warteschlange:

sowie
-Mittlere Länge der nicht-leeren Warteschlange

-Mittlere Wartezeit in der nicht-leeren Warteschlange

Sei W die mittlere Zeit im System, L die mittlere Anzahl im System und l die Ankunftsrate, dann gilt:

und die mittlere Zeit in der Warteschlange ist

Fallstudie Qualitätskontrolle
Es gibt einen Warteplatz für die Paletten mit Fertigteilen und eine Prüfstation. Im Mittel kommen 80 Paletten während der Arbeitszeit von acht Stunden an, die zugehörige Zwischenankunftszeit ist exponentialverteilt. Die Kontrolle einer Palette dauert im Mittel fünf Minuten und ist ebenfalls exponentialverteilt. Eine Prüfstation kostet DM 50 pro Tag, ein Prüfarbeiter DM 60 pro Stunde. Ein Puffer für eine Palette kostet DM 20 pro Tag. Es wird mit 250 Arbeitstagen gerechnet.

1)Wie viele Paletten befinden sich durchschnittlich gleichzeitig im Puffer (Warteschlange)?

2)Wie lange muß eine gerade ankommende Palette durchschnittlich warten?

3)Wie verändern sich die Verhältnisse, wenn eine zweite Prüfstation mit getrennter Warteschlange eingerichtet wird?
l=5, m=12, also:

4)Wie verändern sich die Verhältnisse mit einer gemeinsamen Warteschlange für beide Prüfstationen?
Hierzu benötigt man ein M/M/2-System, also andere Formeln.

5)Welche Variante hat die besten Wirtschaftlichkeitsparameter?
Im Rahmen dieser Berechnungen müssen die Preise berücksichtigt werden.

6)Wie verändern sich die Verhältnisse des Warteschlangensystems bei einer durchschnittlichen Prüfzeit von 6 Minuten statt 5 Minuten? Hier gilt l=m.