___________________________________________________________________________
Inhalt....: Warteschlangen II
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: plot::Function2d, plot::PointList2d, AxesTitles, Color,
Funktionen: LegendText, LegendVisible, LegendPlacement, LegendAlignment,
Funktionen: LineWidth, print, expr2text, stats::mean, max, min, ceil,
Funktionen: trunc, concat, float
___________________________________________________________________________
Die Warteschlange M|M|1
Dieses Notebook ist als Fortsetzung des Notebooks "Warteschlangen I" zu verstehen. Die verwendeten Abkürzungen, wie z.B. ZAZ für "Zwischenankunftszeit", werden in der Legende am Ende des Dokuments erläutert.
In diesem Notebook werden wir ein weiteres Warteschlangensystem kennenlernen, das M|M|1-Warteschlangensystem. In dem Warteschlangensystem M|M|1 sind sowohl die Zwischenankunftszeiten A_n, n in N, als auch die Bedienzeiten B_n, n in N, exponentialverteilt, es gibt einen Schalter und der Warteraum ist unbegrenzt.
Aufbau dieses Notebooks:
1. Der Ankunftsprozess des M|M|1-Warteschlangensystems
2. Die Wartezeiten der Kunden
3. Die Länge der Warteschlange
4. Das Warteschlangensystem M|M|1
1. Der Ankunftsprozess des M|M|1-Warteschlangensystems
In dem M|M|1-Warteschlangensystem wollen wir zunächst den Ankunftsprozess und die Zufallsvariable X_s, s>0, die uns die Anzahl der bis zum Zeitpunkt s angekommenen Kunden angibt, untersuchen.
Aus der Exponentialverteilung der Zwischenankunftszeiten folgt ein poissonverteilter Kundenankunftsstrom (siehe Anmerkung 2 am Ende des Dokuments): Wir nehmen an, dass die Zwischenankunftszeiten exponentialverteilt sind zum Parameter LA>0. Die Zufallsvariable X_s, s>0, ist dann poissonverteilt zum Parameter (LA*s). Ihr Erwartungswert E(X_s) ist gleich LA*s.
Die Prozedur "AnzahlAnkuenfte" plottet die Anzahl der angekommenen Kunden in einem M|M|1-Warteschlangensystem in Abhängigkeit der Zeit und berechnet die Anzahl der bis zum Zeitpunkt s, s>0, angekommenen Kunden. Diese wird mit dem erwarteten Wert (siehe oben) verglichen. Die Prozedur bekommt die mittlere Anzahl LA ankommender Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Zwischenankunftszeiten übergeben (diese muss natürlich > 0 sein), die Gesamtanzahl KG der ankommenden Kunden und den Zeitpunkt s.
AnzahlAnkuenfte:=proc(LA,KG,s)
local X_s,ZAZ,A,L1,m,X,ank,f1,f2,EW;
begin
s:= trunc(s);
X_s:= 0;
ZAZ:= stats::exponentialRandom(0,LA);
A:= [ZAZ()$i=1..KG]; // ZAZ der Kunden
L1:= [[0,0]$KG];
for i from 1 to KG do
L1[i][1]:= i; // Nummer des i. Kunden
L1[i][2]:= _plus(A[k]$k=1..i); // AZ des i. Kunden
if L1[i][2] <=s then
X_s:=X_s+1; // zählt die angekommenen Kunden bis zum Zeitpunkt s
end_if;
end_for;
m:= ceil(L1[KG][2]);
X:= [[0,0]$m];
for n from 1 to m do
ank:=0;
for i from 1 to KG do
if L1[i][2] <= n then // AZ des i. Kunden kleiner als n
ank:=ank+1; // zählt die angekommenen Kunden bis zur Zeit n
end_if;
end_for;
X[n][1]:= n; // Zeitpunkt n
X[n][2]:= ank; // bis n angekommene Kunden
end_for;
f1:= plot::Function2d(LA*x, Color=RGB::Red, x=0..n, LegendText="erwartete Anzahl",LineWidth=0.5);
f2:= plot::PointList2d(X);
plot(f1, f2, LegendVisible=TRUE, LegendPlacement=Top, LegendAlignment=Right, AxesTitles=["Zeit", "angekommene Kunden"]);
EW:= LA*s; // erwartete Kundenanzahl bis zum Zeitpunkt s
print("erwartete Anzahl zum Zeitpunkt ".s.": ".expr2text(EW));
print("tatsächliche Anzahl: X_".expr2text(s=X_s));
end_proc;
AnzahlAnkuenfte(2,100,10)
"erwartete Anzahl zum Zeitpunkt 10: 20"
"tatsächliche Anzahl: X_10 = 27"
2. Die Wartezeiten der Kunden
In diesem Abschnitt wollen wir die Wartezeiten der Kunden in einem M|M|1-Warteschlangensystem untersuchen.
Für die Anzahl der Kunden in einem M|M|1-Warteschlangensystem existiert eine stationäre Verteilung, wenn im Mittel pro Zeiteinheit weniger Kunden ankommen als bedient werden, d.h. LA<MU (siehe Anmerkung 2).
Die Prozedur "WartezeitMM1" berechnet und plottet die Wartezeiten der einzelnen Kunden in Abhängigkeit ihrer Ankunftszeiten und die durchschnittliche Wartezeit der Kunden. Sie bekommt dazu die mittlere Anzahl LA ankommender Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Zwischenankunftszeiten übergeben, die mittlere Anzahl MU bedienter Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Bedienzeiten und die Gesamtanzahl der ankommenden Kunden. In der Prozedur benutzen wir die Variable VW, die virtuelle Wartezeit. Die virtuelle Wartezeit ist für jeden Zeitpunkt die Zeit, die der Schalter noch zur Bedienung aller bestehenden Forderungen benötigt.
WartezeitMM1:=proc(LA,MU,KG)
local VW,ZAZ,BZ,A,B,L3,mittel,f1,f2;
begin
VW:= 0: // virtuelle Wartezeit
ZAZ:= stats::exponentialRandom(0,LA);
BZ:= stats::exponentialRandom(0,MU);
A:= [ZAZ()$i=1..KG]; // ZAZ der Kunden
B:= [BZ()$i=1..KG]; // BZ 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;
VW:= L3[i][2]+B[i];
end_for;
mittel:=stats::mean(L3[i][2]$i=1..KG);
// durchschnittliche Wartezeit
if LA > MU // stationäre Verteilung existiert nicht
then print("Für diese Parameterwerte existiert keine stationäre Verteilung!");
end_if;
f1:= plot::Function2d(mittel, Color=RGB::Red, x=0..L3[KG][1], LineWidth=0.5, LegendText="durchschnittliche Wartezeit");
f2:= plot::PointList2d(L3);
plot(f1, f2, AxesTitles=["Ankunftszeit","Wartezeit"], LegendVisible=TRUE, LegendPlacement=Top, LegendAlignment=Right);
print("durchschnittliche Wartezeit: ".expr2text(mittel));
end_proc
WartezeitMM1(0.45,0.5,1000)
"durchschnittliche Wartezeit: 15.48148683"
3. Die Länge der Warteschlange
Jetzt werden wir uns mit der Warteschlangenlänge in einem M|M|1-Warteschlangensystem beschäftigen.
Die Prozedur "WarteschlangeMM1" berechnet und plottet die Länge der Warteschlange in Abhängigkeit der Zeit und die durchschnittliche Warteschlangenlänge.
*** Die Anzahl L_s der wartenden Kunden zum Zeitpunkt s, s>0,
berechnet sich dabei aus der Anzahl der bis zum Zeitpunkt s
eingetroffenen Kunden und der Anzahl der bis zum Zeitpunkt s
bedienten Kunden:
Die Prozedur bekommt die mittlere Anzahl LA ankommender Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Zwischenankunftszeiten übergeben, die mittlere Anzahl MU bedienter Kunden pro Zeiteinheit als Parameter für die Exponentialverteilung der Bedienzeiten und die Gesamtanzahl ankommender Kunden.
WarteschlangeMM1:= proc(LA,MU,KG)
local ZAZ,BZ,A,B,L1,L2,ank,bed,m,X,Y,L,d,f1,f2,mittel,f3,f4;
begin
ZAZ:= stats::exponentialRandom(0,LA);
BZ:= stats::exponentialRandom(0,MU);
A:= [ZAZ() $ i=1..KG]; // ZAZ der Kunden
B:= [BZ() $ i=1..KG]; // BZ der Kunden
L1:= [[0,0] $ KG];
L2:= [[0,0] $ KG];
for i from 1 to KG do
L1[i][1]:=i; // Nummer des i. Kunden
L1[i][2]:=_plus(A[l]$l=1..i); // AZ des i. Kunden
L2[i][1]:=i; // Nummer des i. Kunden
end_for;
L2[1][2]:=L1[1][2]+B[1]; // EB des 1. Kunden
for i from 2 to KG do
L2[i][2]:=max(L1[i][2],L2[i-1][2])+B[i] // EB des i. Kunden
end_for;
m:= ceil(L1[KG][2]);
// zeitliche Dauer des Ankunfts- und Bedienprozesses//
X:= [[0,0]$m];
Y:= [[0,0]$m];
L:= [[0,0]$m];
for n from 1 to m do
ank:=0;
bed:=0;
for i from 1 to KG do
if L1[i][2]<=n then // AZ des i. Kunden kleiner als n
ank:=ank+1; // zählt die angekommenen Kunden bis zur Zeit n
end_if;
if L2[i][2] <= n then // EB des i. Kunden kleiner als n
bed:=bed+1; // zählt die bedienten Kunden bis zur Zeit n
end_if;
end_for;
X[n][1]:=n; // Zeitpunkt n
X[n][2]:=ank; // bis n angekommene Kunden
Y[n][1]:=n; // Zeitpunkt n
Y[n][2]:=bed; // bis n bediente Kunden
d:=ank-bed;
L[n][1]:=n; // Zeitpunkt n
L[n][2]:=d; // WL zur Zeit n
end_for;
f1:= plot::PointList2d(X, Color=RGB::Red, Legend="angekommene Kunden");
f2:= plot::PointList2d(Y,Legend="bediente Kunden");
plot(f1, f2, AxesTitles=["Zeit","Anzahl Kunden"], LegendVisible=TRUE, LegendPlacement=Top, LegendAlignment=Right);
mittel:= stats::mean(L[i][2]$i=1..m);
// durchschnittliche Warteschlangenlänge
if LA > MU // stationäre Verteilung existiert nicht
then print ("Für diese Parameterwerte existiert keine stationäre Verteilung!");
end_if;
f3:= plot::PointList2d(L);
f4:= plot::Function2d(mittel, Color=RGB::Red, LegendText="durchschnittliche Länge der Warteschlange", LineWidth=0.5,x=0..m);
plot(f3,f4,AxesTitles=["Zeit","WL"], LegendVisible=TRUE, LegendPlacement=Top, LegendAlignment=Right);
print("durchschnittliche Länge der Warteschlange: ". expr2text(float(mittel)));
end_proc;
WarteschlangeMM1(0.8,0.9,1000)
"durchschnittliche Länge der Warteschlange: 13.31174439"
4. Das Warteschlangensystem M|M|1
Zum Abschluss dieses Notebooks betrachten wir die Prozedur "MM1ZeitLaenge", die sowohl die Wartezeiten der einzelnen Kundenals auch die Länge der Warteschlange in Abhängigkeit der Zeit und die durchschnittlichen Werte berechnet und plottet.
MM1ZeitLaenge:= proc(LA,MU,KG)
local VW,ZAZ,BZ,A,B,L1,L2,L3,wartemittel,ank,bed,m,L,d,f1,f2,f3,f4,laengemittel;
begin
VW:= 0: // virtuelle Wartezeit
ZAZ:= stats::exponentialRandom(0,LA);
BZ:= stats::exponentialRandom(0,MU);
A:= [ZAZ()$i=1..KG]; // ZAZ der Kunden
B:= [BZ()$i=1..KG]; // BZ der Kunden
L1:= [[0,0]$KG];
L2:= [[0,0]$KG];
L3:= [[0,0]$KG];
for i from 1 to KG do
L1[i][1]:= i; // Nummer des i. Kunden
L1[i][2]:= _plus(A[l]$l=1..i); // AZ des i. Kunden
L2[i][1]:= i; // Nummer des i. Kunden
end_for;
L2[1][2]:= L1[1][2]+B[1]; // EB des 1. Kunden
for i from 2 to KG do
L2[i][2]:= max(L1[i][2],L2[i-1][2])+B[i] // EB des i. Kunden
end_for;
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;
VW:= L3[i][2]+B[i];
end_for;
m:= ceil(L1[KG][2]); // zeitliche Dauer des Ankunfts- und Bedienprozesses
L:=[[0,0]$m];
for n from 1 to m do
ank:=0;
bed:=0;
for i from 1 to KG do
if L1[i][2]<=n then // AZ des i. Kunden kleiner als n
ank:=ank+1; // zählt die angekommenen Kunden bis zur Zeit n
end_if;
end_for;
for j from 1 to KG do
if L2[j][2]<=n then // EB des i. Kunden kleiner als n
bed:=bed+1; // zählt die bedienten Kunden bis zur Zeit n
end_if;
end_for;
d:=ank-bed;
L[n][1]:=n;
L[n][2]:=d; //WL zur Zeit n//
end_for;
wartemittel:= stats::mean(L3[i][2] $ i=1..KG);
// durchschnittliche Wartezeit
laengemittel:= stats::mean(L[i][2] $ i=1..m);
// durchschnittliche Warteschlangenlänge
if LA > MU // stationäre Verteilung existiert nicht
then print("Für diese Parameterwerte existiert keine stationäre Verteilung!");
end_if;
f1:= plot::Function2d(wartemittel, Color=RGB::Red, x=0..L3[KG][1], LineWidth=0.5, LegendText="durchschnittliche Wartezeit");
f2:= plot::PointList2d(L3);
plot(f1, f2, AxesTitles=["Ankunftszeit","Wartezeit"], LegendVisible=TRUE,LegendPlacement=Top, LegendAlignment=Right);
print("durchschnittliche Wartezeit: ".expr2text(wartemittel));
f3:= plot::Function2d(laengemittel,Color=RGB::Red, x=0..L[m][1],LineWidth=0.5, LegendText="durchschnittliche Länge der Warteschlange");
f4:= plot::PointList2d(L);
plot(f3, f4, AxesTitles=["Zeit","WL"], LegendVisible=TRUE, LegendPlacement=Top, LegendAlignment=Right);
print("durchschnittliche Länge der Warteschlange: ".
expr2text(float(laengemittel)));
end_proc;
MM1ZeitLaenge(1.2,1.5,1000)
"durchschnittliche Wartezeit: 2.563919913"
"durchschnittliche Länge der Warteschlange: 3.856793146"
Bei vielen Warteschlangensystemen gilt die Annahme exponentialverteilter Zwischenankunfts- und Bedienzeiten als statistisch gesichert. Es ist jedoch auch interessant, die obigen Prozeduren so umzuschreiben, dass die Zeiten anderen Verteilungen unterliegen. So können z.B. Warteschlangensysteme mit Zwischenankunfts- und Bedienzeiten, die auf einem bestimmten Zeitintervall gleichverteilt sind, empirisch untersucht werden. Auch die Untersuchung von
Warteschlangensystemen mit unterschiedlich verteilten Zwischenankunfts- und Bedienzeiten stellt eine reizvolle Aufgabenstellung dar.
___________________________________________________________________________
Legende:
|
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 |
|
ZAZ |
Zwischenankunftszeit |
|
AZ |
Ankunftszeit |
|
BZ |
Bedienzeit |
|
EB |
Ende der Bedienzeit |
|
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 |
|
rho |
Verkehrsdichte des Warteschlangensystems (siehe "Warteschlangen I") |
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.
___________________________________________________________________________