Warteschlangentheorie

Einleitung

In der Warteschlangentheorie werden Bedienungssysteme, bei denen Ankunfts- und Abfertigungsprozesse auftreten, analysiert. Warteschlangen treten z.B.: in der Fertigung, in Supermärkten oder in Verkehrssystemen auf. Neben der Analyse dieser Prozesse ist es Aufgabe der Warteschlangentheorie einen möglichst optimalen Ausgleich zwischen Abfertigungs- und Wartekosten zu schaffen.

Darstellung von Wartesystemen

Notation nach Kendall und Lee:
A/B/s: (d, e)

mit
A: Ankunftsprozess
B: Abfertigungsprozess
s: Anzahl der Abfertigungsstationen
d: Anzahl der Elemente, die sich in der Warteschlange befinden können
e: Auswahlprozess, nach dem bestimmt wird, welche Elemente der Warteschlange bedient werden (z.B.: zufällige Auswahl oder First-In-First-Out)

Die Ankunfts- und Abfertigungsprozesse werden durch Wahrscheinlichkeitsverteilungen simuliert.

Beispiel

Im Folgenden wird das Grundmodell, das M/M/1: (∞, FIFO) Wartesystem analysiert

M= Markov; die Ankunftsprozesse werden als zufällig und voneinander unabhängig betrachtet, sie werden je nach Sichtweise(Zeit-/Ereignisbezogen) durch die Poisson-/Exponentialverteilung simuliert; es gibt eine Bedienstation; es gibt keine Beschränkung für die Größe der Warteschlange; es wird nach dem First-In-First-Out Prinzip bedient. Diese Größen werden im Folgenden Abschnitt bestimmt.

Es wird ein festes Zeitintervall T betrachtet.

λ= die durchschnittliche Anzahl der Ankünfte in T
μ= die durchschnittliche Anzahl der Abfertigungen in T
Interessant erscheint die durchschnittliche Länge der Warteschlange, sowie die durchschnittliche Wartezeit einer Person.

Ausgangspunkt ist ein sehr kleines Zeitintervall Δt in dem nur eine Person hinzukommen oder abgefertigt werden kann.
Die Wahrscheinlichkeit(P), dass sich kein Element in der Warteschlange befindet ist gleich der Wahrscheinlichkeit, dass sich keins in der Warteschlange befindet und innerhalb Δt kein neues hinzukommt, zuzüglich der Wahrscheinlichkeit, dass sich ein Element in der Warteschlange befindet und dieses abgefertigt wird, jedoch kein neues hinzukommt.

P₀= P₀(1-λΔt) + P₁(1-λΔt)μΔt
=P₀(1-λΔt) + P₁μΔt - P₁λΔtμΔt
=P₀(1-λΔt) + P₁μΔt (Δt²ist zu vernachlässigen)
somit ergibt sich die Wahrscheinlichkeit, dass sich eine Person im System befindet zu
P₁= (λ/μ)P₀
Diese Formel lässt sich verallgemeinern zu:
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik1.jpg
Die Summe aller Wahrscheinlichkeiten ist gleich 1.
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik2.jpg
Der Term
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik3.jpg
lässt sich ersetzten durch
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik4.jpg
da λ kleiner als μ ist (geometrische Reihe).
Man erhält also:
P₀= 1-(λ/μ)
Die durchschnittliche Länge der Warteschlange(Erwartungswert) ist gleich der Wahrscheinlichkeit, dass eine Warteschlange der Länge i auftritt multipliziert mit i, aufsummiert über alle i (Beim Würfel beträgt der Erwartungswert 3,5= 1/6*1+1/6*2+1/6*3+1/6*4+1/6*5+1/6*6):

http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik5.jpg

Ersetzt man
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik6.jpg
durch
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik7.jpg
so erhält man für n:
http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Grafik8.jpg
Die durchschnittliche Verweilzeit t_v eines Elementes im System ergibt sich aus der durchschnittlichen Länge der Warteschlange dividiert durch die durchschnittlichen Ankünfte pro Zeiteinheit:
t_v = n/λ = 1/(μ-λ)
Die durchschnittliche Wartezeit t_w ist gleich der durchschnittlichen Verweilzeit abzüglich der durchschnittlichen Abfertigungszeit:
t_w = 1/(μ-λ) -1/μ

Zahlenbeispiel zur M/M/1: (∞, FIFO) Warteschlange

Im folgende Zahlenbeispiel wird das Wartesystem eines Geschäftes untersucht. Im Durchschnitt besuchen pro Stunde 15 Personen das Geschäft (λ), eine Verkäuferin kann pro Stunde 20 Personen bedienen (μ).
Die durchschnittliche Länge der Warteschlange beträgt n=λ/(μ-λ)= 15/5 =3
Die Verweilzeit beträgt tv= n/λ= 3/15 = 0,2h bzw. 12min
Die Wartezeit beträgt tw= tv – 1/ μ = 0,2- 1/20 = 0,15h bzw. 9min

Nun wird eine neue Verkäuferin eingestellt. Sie kann pro Stunde durchschnittlich nur 18 Personen bedienen.
Die durchschnittliche Länge der Warteschlange beträgt nun n=λ/(μ-λ)= 15/3 =5
Die Verweilzeit beträgt tv= n/λ= 5/15 = 0,33h bzw.20min
Die Wartezeit beträgt tw= tv – 1/ μ = 0,33- 1/18 = 0,278h bzw. 16,67min

Vorlesung

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

06.02.2007

Warteschlangentheorie 06.02.2007 (Download)
Warteschlangentheorie 06.02.2007 (Stream)
Warteschlangentheorie 06.02.2007 (scaled Stream)

Achtung: die Dateien können fehlerhaft sein! Sobald dies möglich ist, werden aktuelle Mitschnitte aus dem WS 07/08 zur Verfügung gestellt.
Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.