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

                   =P0(1-λΔt) + P1μΔt -  P1λΔ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:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Die Summe aller Wahrscheinlichkeiten ist gleich 1.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Der Term

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

lässt sich ersetzten durch

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

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):

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Ersetzt man

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

durch

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

so erhält man für n:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

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

Tutorial

Wenn Sie sich näher mit einem M/M/1-System beschäftigen möchten, können Sie dies anhand eines Tutorials der Universität Melbourne, das auch die Möglchkeit bietet, eigene Beispiele zu lösen. Auf den Seiten der Fernuniversität Hagen findes Sie ein Java-Applet zur Simulation von Warteschlangen.

Vorlesung/Lecture

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

• Queuing Theory (English)