___________________________________________________________________________
Inhalt....: Warteschlangen III
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: trunc, float, plot::PointList2d, plot::Function2d, AxesTitles,
Funktionen: LegendText, LegendVisible, LegendPlacement, LegendAlignment,
Funktionen: PointStyle, PointSize, Color, print, expr2text, stats::mean,
Funktionen: listlib::setDifference, concat
___________________________________________________________________________
Warteschlangen mit begrenztem Warteraum
Dieses Notebook ist als Fortsetzung der Notebooks "Warteschlangen I" und "Warteschlangen II" 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 zwei weitere Warteschlangensysteme kennenlernen, das M|const|1|m-Warteschlangensystem und das M|M|1|m-Warteschlangensystem. Bei diesen Systemen handelt es sich um Warteschlangensysteme mit begrenzten Warteräumen, d.h. einer Beschränkung der maximalen Anzahl wartender Kunden. Die Warteschlangensysteme M|const|1|m und M|M|1|m unterscheiden sich von den M|const|1- und M|M|1-Warteschlangensystemen nur dadurch, dass der Warteraum auf maximal m wartende Kunden beschränkt ist, d.h. dass sich maximal m+1 Kunden im System aufhalten können.
Aufbau dieses Notebooks:
1. Das M|const|1|m-Warteschlangensystem
2. Das M|M|1|m-Warteschlangensystem
1. Das M|const|1|m-Warteschlangensystem
Das M|const|1|m-Warteschlangensystem ist ein M|const|1-Warteschlangensystem mit einem auf m, m in N, Kunden begrenzten Warteraum, d.h. dass entweder der Warteraum z.B. räumlich auf m wartende Kunden begrenzt ist oder dass die Kunden, die in dieses Warteschlangensystem eintreffen, so ungeduldig sind, dass sie sich nicht in die Warteschlange einreihen, wenn sie bereits m wartende Kunden vor sich sehen.
Die Prozedur "WarteMconst1m" plottet die Wartezeit eines jeden Kunden und die Länge der Warteschlange bei seiner Ankunft und berechnet die durchschnittliche Warteschlangenlänge und Wartezeit der Kunden. 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 ankommender Kunden und die maximale Anzahl m wartender Kunden.
WarteMconst1m:=proc(LA,BE,KG,m)
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. Kunden
if A[i] < VW
then L1[i][2]:= VW-A[i] // WZ des i. Kunden
else L1[i][2]:= 0
end_if;
L2[i][1]:=i; // Nummer des i. Kunden
L2[i][2]:=trunc(L1[i][2]/BE);
// WL bei Ankunft des i. Kunden
if L2[i][2] < m // Warteschlange nicht zu lang
then VW:= L1[i][2]+BE // der Kunde stellt sich an
else VW:= L1[i][2] // der Kunde stellt sich nicht an
end_if;
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
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 bei Ankunft des Kunden"], LegendVisible=TRUE, LegendPlacement=Bottom, LegendAlignment=Left);
print("durchschnittliche Länge der Warteschlange: ".expr2text(float(laengemittel)))
end_proc;
WarteMconst1m(1,1,500,3)
"durchschnittliche Wartezeit: 1.69177654"
"durchschnittliche Länge der Warteschlange: 1.252"
Wir variieren nun die Werte LA und BE, indem wir sowohl die mittlere Anzahl ankommender Kunden pro Zeiteinheit als auch die Bediendauer immer größer werden lassen.
WarteMconst1m(2,2,500,3)
"durchschnittliche Wartezeit: 6.442757337"
"durchschnittliche Länge der Warteschlange: 2.726"
WarteMconst1m(3,3,500,3)
"durchschnittliche Wartezeit: 10.07623941"
"durchschnittliche Länge der Warteschlange: 2.87"
WarteMconst1m(4,4,500,3)
"durchschnittliche Wartezeit: 13.70086189"
"durchschnittliche Länge der Warteschlange: 2.918"
Wir stellen fest, dass in einem M|const|1|m-Warteschlangensystem immer eine stationäre Verteilung der Anzahl der Kunden im System existiert. Dafür sorgt die begrenzte Systemkapazität: Die Warteschlange kann nicht beliebig lang werden und so können auch die Wartezeiten der Kunden einen bestimmten Wert nicht überschreiten.
2. Das M|M|1|m-Warteschlangensystem
Das M|M|1|m-Warteschlangensystem ist ein System mit exponential-verteilten Zwischenankunfts- und Bedienzeiten, einem Schalter und einem auf m Kunden begrenzten Warteraum.
In der Prozedur "WarteMM1m", die die Wartezeit eines jeden Kunden plottet und die durchschnittliche Wartezeit der Kunden berechnet, wird die begrenzte Systemkapazität nicht durch eine maximale Anzahl m wartender Kunden sondern durch eine maximale Wartezeit w realisiert. Die Kunden, die in dieses System eintreffen, sind so ungeduldig, dass sie sich nicht in die Warteschlange einreihen, wenn ihre Wartezeit den Wert w überschreiten würde. Die Anzahl der potentiellen Kunden, die dem Warteschlangensystem deswegen verloren gehen, wird von der Prozedur ebenfalls berechnet.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, die Gesamtanzahl KG ankommender Kunden und die maximale Wartezeit w.
WarteMM1m:=proc(LA,MU,KG,w)
local VW,ZAZ,BZ,A,B,L1,L2,L3,wartemittel,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
L1:= [[0,0]$KG];
L2:= [];
for i from 1 to KG do
L1[i][1]:=_plus(A[k]$k=1..i); // AZ des i. Kunden
if A[i]<VW
then L1[i][2]:=VW-A[i] // WZ des i. Kunden
else L1[i][2]:=0
end_if;
if L1[i][2]<w // Wartezeit nicht zu lang
then VW:=L1[i][2]+B[i] // Kunde stellt sich an
else VW:=L1[i][2]; // Kunde stellt sich nicht an
L2:=L2.[L1[i]]; // alle Kunden, die sich nicht anstellen
end_if;
end_for;
L3:= listlib::setDifference(L1,L2); // Wartezeiten
wartemittel:=stats::mean(L3[i][2]$i=1..nops(L3));
// durchschnittliche Wartezeit
f1:= plot::Function2d(wartemittel, x=0..max(L3[i][1]$i=1..nops(L3)), LegendText="durchschnittliche Wartezeit", LineWidth=0.5);
f2:= plot::PointList2d(L3);
plot(f1, f2, AxesTitles=["Ankunftszeit","Wartezeit"], LegendVisible=TRUE, LegendPlacement=Top, LegendAlignment=Right);
print("durchschnittliche Wartezeit: ".expr2text(wartemittel));
print("Von ".nops(L1).
" potentiellen Kunden reihten sich ".nops(L2).
" nicht in die Warteschlange ein!");
end_proc;
WarteMM1m(2,2,1000,10)
"durchschnittliche Wartezeit: 5.68225175"
"Von 1000 potentiellen Kunden reihten sich 79 nicht in die Warteschlange ein!"
Auch in diesem Warteschlangensystem können wir durch Variation der Werte LA und MU feststellen, dass für beliebige Werte eine stationäre Verteilung existiert und die Wartezeiten der Kunden den vorgegebenen Wert nicht überschreiten:
WarteMM1m(3,2,1000,10)
"durchschnittliche Wartezeit: 8.907653636"
"Von 1000 potentiellen Kunden reihten sich 345 nicht in die Warteschlange ein!"
WarteMM1m(5,2,1000,10)
"durchschnittliche Wartezeit: 9.289340063"
"Von 1000 potentiellen Kunden reihten sich 565 nicht in die Warteschlange ein!"
___________________________________________________________________________
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.
___________________________________________________________________________