___________________________________________________________________________
Inhalt....: Warteschlangen I
Kategorie.: Arbeitsblatt
Mathematik: Stochastik, Statistik
MuPAD.....: 3.1.1
Datum.....: 2007-05-14
Autoren...: Anna Lena Stahr <annalena.stahr@web.de>
Funktionen: proc, local, stats::exponentialRandom, for, _plus, if, else,
Funktionen: stats::mean, print, plot::PointList2d, plot::Function2d,
Funktionen: PointStyle, PointSize, Color, LegendText, LegendVisible,
Funktionen: LegendPlacement, LegendAlignment, expr2text, float,
Funktionen: AxesTitles, max, in, trunc, concat
___________________________________________________________________________
Warteschlangen I
Hinweis: Dieses Notebook wird fortgesetzt in den Notebooks WarteschlangenII und Warteschlangen III.
Warteschlangen bilden sich in vielen Bereichen des täglichen Lebens: vor Supermarktkassen oder Fahrkartenautomaten, bei Fahrzeugkontrollen, im Wartezimmer einer Arztpraxis, an Taxiständen, in Telefonzentralen, vor Autowaschanlagen, in Reparaturwerkstätten, usw.
In diesem aus drei Notebooks bestehenden Paket werden Eigenschaften verschiedener Warteschlangensysteme simuliert und empirisch untersucht.
Das erste Notebook beschäftigt sich zunächst mit der wahrscheinlichkeits-theoretischen Modellierung einer Warteschlange. Es werden die einzelnen Prozesse und Komponenten, aus denen sich ein Warteschlangensystem zusammensetzt, benannt und kurz erläutert.
Anschließend betrachten wir Warteschlangensysteme mit unterschiedlich vielen Bedienstationen, in denen die Bedienzeiten eine feste Dauer haben. Wir untersuchen die zeitliche Entwicklung der Länge der Warteschlange und der Wartezeiten der einzelnen Kunden und berechnen die durchschnittliche Warteschlangenlänge und Wartezeit der Kunden.
Im zweiten Notebook werden wir das Warteschlangensystem M|M|1 kennenlernen und die Wartezeiten der Kunden und die Länge der Warteschlange in diesem System untersuchen.
Im dritten Notebook werden wir zwei Warteschlangensysteme mit begrenzter Systemkapazität, d.h. einem beschränkten Warteraum, untersuchen.
Aufbau dieses Notebooks:
1. Wahrscheinlichkeitstheoretische Modellierung von Warteschlangensystemen
2. Die Untersuchung von Warteschlangensystemen
3. Das Warteschlangensystem M|const|1
4. Das Warteschlangensystem M|const|2
5. Das Warteschlangensystem M|const|s, s in N
1. Wahrscheinlichkeitstheoretische Modellierung von Warteschlangensystemen
Jedes Warteschlangensystem setzt sich aus den folgenden Prozessen und Komponenten zusammen:
Der Ankunftsprozess beschreibt das Eintreffen von Kunden in das Warteschlangensystem. Mit A_n, n in N, beschreiben wir die Zwischenankunftszeit des n. Kunden, d.h. die Zeit, die zwischen der Ankunft des (n-1). und der Ankunft des n. Kunden vergeht. Diese Zeiten seien unabhängig und identisch verteilt.
Der Bedienprozess beschreibt das Bedienen der eingetroffenen Kunden. Auch die Bedienzeiten B_n, n in N, seien unabhängig und identisch verteilt.
Trifft ein Kunde in das System ein und findet keinen freien Schalter vor, so bildet sich eine Warteschlange. Weiter ankommende Kunden reihen sich in diese ein und warten im Warteraum auf ihre Bedienung. Dieser kann entweder unendlich groß oder auf eine bestimmte Anzahl wartender Kunden beschränkt sein.
Die Warteschlangendisziplin beschreibt, in welcher Reihenfolge die eingetroffenen Kunden bedient werden. Wir werden in diesem Notebook und den Notebooks "Warteschlangen II" und "Warteschlangen III" nur Warteschlangensysteme der "first in, first out"-Disziplin untersuchen: Die Kunden werden in der Reihenfolge ihres Eintreffens bedient, z.B. an der Kasse eines Supermarkts oder am Fahrkartenschalter eines Bahnhofs.
Wir definieren die folgenden Zufallsvariablen und Parameter:
|
X_s |
Anzahl der bis zum Zeitpunkt s eingetroffenen Kunden |
|
Y_s |
Anzahl der bis zum Zeitpunkt s bedienten Kunden |
|
L_s |
=X_s-Y_s, Anzahl der Kunden im Warteschlangensystem zum Zeitpunkt s |
|
A_n |
Zwischenankunftszeit (ZAZ) des n. Kunden |
|
A*_n |
Ankunftszeit (AZ) des n. Kunden |
|
B_n |
Bedienzeit (BZ) des n. Kunden |
|
B*_n |
Ende der Bedienzeit (EB) des n. Kunden |
|
LA |
mittlere Anzahl ankommender Kunden pro Zeiteinheit |
|
MU |
mittlere Anzahl bedienter Kunden pro Zeiteinheit |
|
KG |
Gesamtzahl der ankommenden Kunden |
|
BE |
konstante Bedienzeit |
|
VW |
virtuelle Wartezeit: Die virtuelle Wartezeit ist für jeden Zeitpunkt die Zeit, die der Schalter noch zur Bedienung aller bestehenden Forderungen benötigt. |
|
WZ |
Wartezeit eines angekommenen Kunden |
|
WL |
Länge der Warteschlange |
2. Die Untersuchung von Warteschlangensystemen
Bei der Untersuchung von Warteschlangensystemen ist u.a. die Beantwortung folgender Fragen von Interesse:
- Gibt es eine stationäre Verteilung der Anzahl der Kunden im Warteschlangensystem, d.h. pendelt sich die Anzahl der Kunden im System in einen Gleichgewichtszustand ein?
- Wie groß ist die durchschnittliche Anzahl wartender Kunden im Gleichgewicht?
- Wie lang ist die durchschnittliche Wartezeit eines Kunden?
Zur Beantwortung dieser Fragen führen wir den Begriff der Verkehrsdichte eines Warteschlangensystems ein.
Definition:
Die Verkehrsdichte rho eines Warteschlangensystems ist definiert als der Quotient aus dem Erwartungswert der Bedienzeiten und dem Erwartungswert der Zwischenankunftszeiten:
rho:=E(B_1)/E(A_1)
Für die verschiedenen Warteschlangensysteme existieren nur für bestimmte Werte von rho stationäre Verteilungen. Beachten Sie dazu bitte die Anmerkung 2 am Ende des Dokuments.
3. Das Warteschlangensystem M|const|1
In dem Warteschlangensystem M|const|1 sind die Zwischenankunftszeiten A_n, n in N, exponentialverteilt, die Bedienzeiten B_n, n in N, sind konstant, es gibt einen Schalter und der Warteraum ist unbegrenzt.
Für die Anzahl der Kunden in einem M|const|1-Warteschlangensystem existiert eine stationäre Verteilung, wenn im Mittel pro Zeiteinheit weniger Kunden ankommen als bedient werden, d.h.
LA<(1/BE).
Die Prozedur "WarteMconst1" plottet die Wartezeit eines jeden Kunden und die Länge der Warteschlange bei seiner Ankunft und berechnet die durchschnittliche Wartezeit der Kunden und die durchschnittliche Warteschlangenlänge. Sie bekommt dazu die mittlere Anzahl LA ankommender Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Zwischenankunftszeiten übergeben (diese muss natürlich > 0 sein), die konstante Dauer BE der Bedienzeiten und die Gesamtanzahl KG ankommender Kunden.
WarteMconst1:= proc(LA,BE,KG)
local VW,ZAZ,A,L1,L2,wartemittel,laengemittel,f1,f2,f3,f4;
begin
VW:= 0: // virtuelle Wartezeit
ZAZ:= stats::exponentialRandom(0,LA);
A:= [ZAZ()$i=1..KG]; // ZAZ der Kunden
L1:= [[0,0] $ KG];
L2:= [[0,0] $ KG];
for i from 1 to KG do
L1[i][1]:= _plus(A[k] $ k=1..i); // AZ des i-ten Kunden
if A[i] < VW
then L1[i][2]:=VW-A[i] // WZ des i-ten Kunden
else L1[i][2]:=0
end_if;
L2[i][1]:= i; // Nummer des i-tn Kunden
L2[i][2]:= trunc(L1[i][2]/BE); // WL bei Ankunft des i-ten Kunden
VW:= L1[i][2]+BE;
end_for;
wartemittel:= stats::mean(L1[i][2] $ i=1..KG);
// durchschnittliche Wartezeit
laengemittel:= stats::mean(L2[i][2] $ i=1..KG);
// durchschnittliche Warteschlangenlänge
if LA*BE >= 1
then print("Für diese Parameterwerte existiert keine stationäre Verteilung!")
end_if;
f1:= plot::PointList2d(L1, PointStyle=XCrosses, Color=RGB::Red);
f2:= plot::Function2d(wartemittel, x=0..L1[KG][1], LegendText="durschnittliche Wartezeit");
plot(f1, f2, AxesTitles=["Ankunftszeit","Wartezeit"],
LegendVisible=TRUE, LegendPlacement=Bottom, LegendAlignment=Left);
print("durchschnittliche Wartezeit: ".expr2text(float(wartemittel)));
f3:= plot::PointList2d(L2, PointSize=1.5, Color=RGB::Red);
f4:= plot::Function2d(laengemittel, x=0..KG,
LegendText="durschnittliche Länge der Warteschlange");
plot(f3,f4,AxesTitles=["Kundennummer","WL"], LegendVisible=TRUE,LegendPlacement=Bottom,
LegendAlignment=Left);
print("durchschnittliche Länge der Warteschlange: ".expr2text(float(laengemittel)));
end_proc;
WarteMconst1(1, 0.8, 500)
"durchschnittliche Wartezeit: 2.123957039"
"durchschnittliche Länge der Warteschlange: 2.218"
Für Werte LA und BE, für die keine stationäre Verteilung der Anzahl der Kunden im System existiert, ergeben sich deutlich zunehmende Wartezeiten der Kunden und eine immer länger werdende Warteschlange.
4. Das Warteschlangensystem M|const|2
Das Warteschlangensystem M|const|2 unterscheidet sich von dem M|const|1-Warteschlangensystem nur dadurch, dass es nicht nur einen, sondern zwei Schalter gibt, vor denen sich eine Warteschlange bildet. Der erste Kunde in der Warteschlange wird dann an dem zuerst frei werdenden Schalter bedient.
Eine stationäre Verteilung existiert für die Anzahl der Kunden in einem M|const|2-Warteschlangensystem, wenn im Mittel pro Zeiteinheit pro Schalter weniger Kunden ankommen als bedient werden, d.h.
LA<(2/BE).
Die Prozedur "WarteMconst2" plottet die Wartezeit eines jeden Kunden und berechnet die durchschnittliche Wartezeit. Sie bekommt dazu die mittlere Anzahl LA ankommender Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Zwischenankunftszeiten übergeben, die konstante Dauer BE der Bedienzeiten und die Gesamtanzahl KG der ankommenden Kunden.
*** Die virtuelle Wartezeit nach der Ankunft des i. Kunden (i>=2) berechnet
sich dabei in einem M|const|2-Warteschlangensystem aus der
Wartezeit des (i-1). Kunden
+ dessen Bedienzeit
- der Zwischenankunftszeit des i. Kunden.
WarteMconst2:=proc(LA,BE,KG)
local VW,ZAZ,A,L3,wartemittel,f1,f2;
begin
VW:=0; //virtuelle Wartezeit//
ZAZ:=stats::exponentialRandom(0,LA);
A:=[ZAZ()$i=1..KG]; //ZAZ der Kunden//
L3:=[[0,0]$KG];
for i from 1 to KG do
L3[i][1]:= _plus(A[k] $ k=1..i); // AZ des i. Kunden
if A[i]<VW
then L3[i][2]:= VW-A[i] // WZ des i. Kunden
else L3[i][2]:= 0
end_if;
if i=1
then VW:= 0
else VW:= max(0,L3[i-1][2]+BE-A[i]) //***
end_if;
end_for;
wartemittel:= stats::mean(L3[i][2] $ i=1..KG);
// durchschnittliche Wartezeit
if LA*BE >= 2
then print("Für diese Parameterwerte existiert keine stationäre Verteilung!")
end_if;
f1:=plot::PointList2d(L3,PointStyle=XCrosses);
f2:=plot::Function2d(wartemittel,x=0..L3[KG][1], LegendText="durschnittliche Wartezeit");
plot(f1, f2, AxesTitles=["Ankunftszeit", "Wartezeit"],
LegendVisible=TRUE,LegendPlacement=Bottom, LegendAlignment=Left);
print("durchschnittliche Wartezeit: ".expr2text(float(wartemittel)));
end_proc;
WarteMconst2(1, 1.8, 500)
"durchschnittliche Wartezeit: 2.986710947"
5. Das Warteschlangensystem M|const|s, s in N
Das Warteschlangensystem M|const|s, s in N, ist eine Verallgemeinerung der Warteschlangensysteme M|const|1 und M|const|2 auf ein Modell mit unbegrenztem Warteraum und s Schaltern, vor denen sich eine Warteschlange bildet. So ein Warteschlangensystem findet man z.B. in vielen öffentlichen Auskunftszentren.
Für die Anzahl der Kunden in einem M|const|s-Warteschlangensystem existiert eine stationäre Verteilung, wenn im Mittel pro Zeiteinheit pro Schalter weniger Kunden ankommen als bedient werden, d.h.
LA < (s/BE).
Die Prozedur "WarteMconst_s" plottet wiederum die Wartezeit eines jeden Kunden und berechnet den durchschnittlichen Wert. Sie bekommt dazu die mittlere Anzahl LA ankommender Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Zwischenankunftszeiten übergeben, die konstante Dauer BE der Bedienzeiten, die Gesamtanzahl KG der ankommenden Kunden und die Anzahl s der Schalter.
*** Die virtuelle Wartezeit nach der Ankunft des i. Kunden (i>=s)
berechnet sich dabei in einem M|const|s-Warteschlangensystem
aus der Wartezeit des (i-(s-1)). Kunden
+ dessen Bedienzeit
- der Zeit, die zwischen der Ankunft des i. Kunden und des (i-(s-1)).
Kunden vergangen ist.
WarteMconst_s:=proc(LA,BE,KG,s)
local VW,ZAZ,A,L3,wartemittel,f1,f2;
begin
VW:=0: // virtuelle Wartezeit
ZAZ:=stats::exponentialRandom(0,LA);
A:=[ZAZ()$i=1..KG]; // ZAZ der Kunden
L3:=[[0,0]$KG];
for i from 1 to KG do
L3[i][1]:= _plus(A[k] $ k=1..i); // AZ des i. Kunden
if A[i] < VW
then L3[i][2]:= VW-A[i] // WZ des i. Kunden
else L3[i][2]:= 0
end_if;
if i in {k $ k=1..s-1}
then VW:= 0
else VW:= max(0,L3[i-(s-1)][2]+BE-(L3[i][1]-L3[i-(s-1)][1])) //***
end_if;
end_for;
wartemittel:=stats::mean(L3[i][2]$i=1..KG);
// durchschnittliche Wartezeit
if LA*BE >= s
then print("Für diese Parameterwerte existiert keine stationäre Verteilung!")
end_if;
f1:=plot::PointList2d(L3,PointStyle=XCrosses);
f2:=plot::Function2d(wartemittel,x=0..L3[KG][1], LegendText="durschnittliche Wartezeit");
plot(f1,f2,AxesTitles=["Ankunftszeit","Wartezeit"], LegendVisible=TRUE,LegendPlacement=Bottom, LegendAlignment=Left);
print("durchschnittliche Wartezeit: ".expr2text(float(wartemittel)));
end_proc;
WarteMconst_s(1,4.8,200,5)
"durchschnittliche Wartezeit: 1.633327791"
___________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen zum Einsatz von MuPAD in der Lehre finden Sie auf unserem WebPortal schule.mupad.de bzw. studium.mupad.de.
2. Mathematische Formeln in diesem Notebook stammen aus der Examensarbeit "Theorie und Simulation von Warteschlangen", die von der Autorin im Rahmen der Ersten Staatsprüfung für das Lehramt an Gymnasien im Jahr 2006 am Institut für Mathematische Stochastik an der Georg-August Universität in Göttingen angefertigt wurde. Die programmierten Warteschlangensysteme wurden im Rahmen dieser Arbeit ebenfalls mathematisch untersucht. Der interessierte Leser sei darauf verwiesen. Entsprechende Teile der Arbeit können gerne auf Anfrage bei der Autorin angefordert werden.
___________________________________________________________________________