Warteschlangen-Theorie
aus www.iwiki.de, der freien Wissensdatenbank
Die Warteschlangentheorie ist ein Teilgebiet des Operations Research und ein Beispiel für Angewandte Mathematik. Wenn Einheiten, die bedient werden sollen bzw. wollen, oder Einrichtungen, die diese Bedienung durchführen, sollen "warten", d.h. Leerzeiten (Wartezeiten) durchmachen, treten Warteschlangen- oder Wartezeitprobleme auf.
Inhaltsverzeichnis |
Allgemeines
Man unterscheidet Warteschlangen in:
- Zugangswarteschlangen
Anzahl der ankommenden Einheiten > verfügbare Abfertigungszeit
- Abgangswarteschlangen
Anzahl freier Bedienstationen > Anzahl der ankommenden Einheiten
Ziele der systematischen Behandlung
- Beschreibung der Warteschlangenprobleme, um diese transparent zu machen
- Errechung optimaler Lösungen (Minimierung der Summe Warte- und Bedienkosten)
Schematisierung des Problems
| Reservoir:
Gesamtheit der Einheiten, die in das Wartesystem eindringen können. Man unterscheidet hierbei zwischen einem geschlossenen System (endlich viele Einheiten) und einem offenen System ("unendlich" viele Einheiten)
Ort, an dem die Einheiten warten (z.B. Schlange vor der Essensausgabe der Mensa). Für den Zugang zur Bedienstation gibt es verschiedene Auswahlprinzipien: FIFO (First In First Out) LIFO (Last In First Out) SIRO (Selection In Random Order) SO (Shortest Operation) Sonstige Prioritäten Ungeduldige Kunden (Sie können die Schlange verlassen)
Ort, an dem die Einheiten bedient werden (z.B. Essensausgabe der Mensa)
Einheiten, die das Wartesystem verlassen
|  |
Analytische Lösungsmethoden
Um analytische Lösungsansätze zu verwenden, muss ein "einfaches" Warteschlangenproblem vorliegen. Diese müssen folgende Bedingungen erfüllen:
- die Ankünfte und Anfertigungen des Warteschlangensystem müssen sich durch handliche Wahrscheinlichkeitsverteilungen beschreiben lassen
- die Abfertigung erfolgt nach FIFO
- die in das Wartesystem eingetretenen Einheiten müssen auch angefertigt werden
Ein Lösungsansatz, welcher der Praxis recht nahe kommt, ist die Poisson-Verteilung. Man unterstellt dabei, dass sich für jedes Zeitintervall t die gleiche Wahrscheinlichkeit für die Ankunft eines Elements ergibt. Die Poisson-Verteilung gibt die Wahrscheinlichkeit dafür an, dass in einem Zeitabschnitt der Länge t genau n Ankünfte zu erwarten sind.
Die Formel zur Bestimmung der Wahrscheinlichkeit lautet:
