Einleitung
Die Analyse von allgemeinen geschlossenen Warteschlangensystemen erweist sich auch heute noch als schwieriges Problem. Mit numerischen Verfahren kann man zwar theoretisch für alle Netze eine Lösung angeben, doch bei vielen großen Netzen spricht dabei der benötigte Platzbzw. Zeitbedarf gegen einen solchen Weg der Analyse. Ein anderer Weg der Berechnung ist die Beschränkung auf sogenannte BCMP- oder Produktformnetze. Für diesen Typ von Warteschlangennetzen existieren exakte Lösungsverfahren (z.B. die Mittelwertanalyse), doch auch hier ist der Platz- bzw. der Zeitbedarf nicht zu unterschätzen.
Deshalb ist man schon sehr frühzeitig auf die Idee gekommen, approximative Verfahren zur Lösung von Produktformnetzen und später auch für allgemeine Netze zu entwickeln. Doch die Verfahren für die allgemeinen Netze sind entweder zu ungenau oder zu aufwendig. Die hier vorgestellte Summationsmethode ist im Gegensatz dazu sehr einfach, leicht zu verstehen, und auch für mehrere Auftragsklassen bzw. für allgemeine Netze anwendbar, wobei die Genauigkeit der Ergebnisse im Vergleich zu den exakten Ergebnissen oder zu den Ergebnissen, die man durch Simulationen erhalten hat, zufriedenstellend ist. Eine weitere Anwendung der Summationsmethode ist die Optimierung von Leistungsgrößen in Netzen.
Warteschlangennetze
Jeder Knoten des Netzes besteht aus einer Warteschlange, in die die ankommenden Aufträge eingereiht werden, und mi identischen Bedieneinheiten mit der Bedienrate µi zur Abfertigung der Aufträge. Für die Analyse eines Netzes müssen die folgenden Größen bekannt sein:
N = Anzahl der Knoten
K = Anzahl der Aufträge
Für alle Knoten i = 1,..., N
mi = Anzahl der Bedieneinheiten
µi = Bedienrate
ei = Besuchshäufigkeit
Sind nur die Übergangswahrscheinlichkeiten pij, i,j i,j = 1,..., N, bekannt, so lassen sich die Besuchshäufigkeiten ei folgendermaßen bestimmen:
Abbildung in dieser Leseprobe nicht enthalten
wobei es im geschlossenen Netz lediglich N-1 unabhängige Gleichungen für die Besuchshäufigkeiten gibt. Man setzt in diesem Fall meist e1 = 1 und rechnet die Werte der anderen ei, i = 2,...,N, in Abhängigkeit von e1 aus.
BCMP- oder Produktform(warteschlangen)netze
BCMP- oder Produktformnetze sind spezielle Warteschlangennetze, die dadurch charakterisiert sind, daß sie die exakte Bestimmung der Leistungsgrößen unter Umgehung der globalen Gleichgewichtsgleichungen ermöglichen. Die einzelnen Knoten eines solchen Warteschlangennetzes müssen einige Voraussetzungen hinsichtlich der Zwischenankunfts- bzw. Bedienzeit sowie der Warteschlangendisziplin erfüllen, damit die Bestimmung der Leistungsgrößen über die sogenannten lokalen Gleichgewichtsgleichungen möglich ist. Folgende Knotentypen besitzen diese Voraussetzungen:
- Typ-1: M/M/m - FCFS
Knoten dieses Typs haben eine exponentiell verteilte Zwischenankunftszeit, eine exponentiell verteilte Bedienzeit und m identische Bedieneinheiten. Die Warteschlangendisziplin FCFS (First-Come-First-Served) bedeutet, daß die Aufträge in der Reihenfolge ihrer Ankunft bedient werden. Dieser Typ wird zur Modellierung von E/A-Geräten und von Platten verwendet.
- Typ-2: M/G/1 - PS[RR]
Knoten dieses Typs haben eine exponentiell verteilte Zwischenankunftszeit, eine beliebige Bedienzeit und eine einzige Bedieneinheit. Die Warteschlangendisziplin RR (Round Robin) bedeutet, daß der aktuelle und noch nicht beendete Auftrag nach einer fest vorgegebenen Zeitscheibe verdrängt und wieder in die Warteschlange eingereiht wird. Die Warteschlangendisziplin PS (Processor Sharing) ist Round Robin mit infinitesimal kleiner Zeitscheibe, so daß der Eindruck entsteht, daß alle Aufträge gleichzeitig bedient würden (mit entsprechend längerer Bedienzeit). Dieser Typ wird zur Modellierung von CPU's verwendet.
- Typ-3: M/G/∞ = Infinite Server (IS)
Knoten dieses Typs haben eine exponentiell verteilte Zwischenankunftszeit, eine beliebige Bedienzeit und unendlich viele identische Bedieneinheiten. Dieser Typ wird zur Modellierung von Terminals verwendet.
- M/G/1 - LCFS
Knoten dieses Typs haben eine exponentiell verteilte Zwischenankunftszeit, eine beliebige Bedienzeit und eine einzige Bedieneinheit. Die Warteschlangendisziplin LCFS (Last-Come- First-Served) bedeutet, daß der zuletzt ankommende Auftrag zuerst bedient wird. Eine Anwendung für diesen Knoten-Typ ist mir nicht bekannt.
Jedes Warteschlangennetz, das aus Kombinationen dieser 4 Knotentypen modelliert werden kann, ist ein BCMP-Netz, und es können die Leistungsgrößen eines solchen Netzes mit z.B. der Mittelwertanalyse exakt ermittelt werden.
Dennoch gibt es viele für die Praxis relevante Warteschlangennetze, die nicht auf BCMP-Netze zurückgeführt werden können!
Leistungsgrößen eines Warteschlangennetzes
Die wichtigsten Leistungsgrößen eines Warteschlangennetzes sind (nach Bolch):
- Auslastung ρ
Bei Wartesystemen mit einer Bedieneinheit ("single server") gibt die Auslastung ρ den
Bruchteil der Gesamtzeit an, den die Bedieneinheit aktiv (belegt) ist. Sie berechnet sich zu
Abbildung in dieser Leseprobe nicht enthalten
Bei mehreren Bedieneinheiten ("multiple servers") gibt die Auslastung auch den mittleren Anteil der aktiven Bedieneinheiten an. Da m⋅µ die Gesamtbedienrate ist, gilt
Abbildung in dieser Leseprobe nicht enthalten
Der Gleichgewichtszustand eines Warteschlangennetzes ist genau dann erreicht (stabiles System), wenn ρ < 1 ist, d.h. es dürfen pro Zeiteinheit im Mittel nicht mehr Aufträge ankommen als bedient werden können.
- Durchsatz λ
Der Durchsatz eines Warteschlangennetzes ist definiert als die mittlere Anzahl von Aufträgen, die pro Zeiteinheit fertig bedient werden (Abgangsrate). Da im statistischen Gleichgewicht die Abgangsrate eines Warteschlangennetzes gleich der Ankunftsrate dieses Warteschlangennetzes ist, berechnet sich der Durchsatz λ wie folgt:
Abbildung in dieser Leseprobe nicht enthalten
- Antwortzeit t und Wartezeit w
Als Antwortzeit (Verweilzeit) bezeichnet man die Gesamtheit der Zeit, die ein Auftrag im Wartesystem verbringt. Die Wartezeit w gibt die Zeit an, die ein Auftrag in der Warteschlange warten muß, bis seine Bearbeitung beginnt. Es gilt:
Antwortzeit = Wartezeit + Bedienzeit
Da w und t meistens als Zufallsgrößen gegeben sind, wird ihr Mittelwert berechnet:
Abbildung in dieser Leseprobe nicht enthalten
- Warteschlangenlänge Q
Die Anzahl der Aufträge in der Warteschlange wird Warteschlangenlänge genannt und mit Q bezeichnet. Es gilt nach dem Gesetz von Little für die mittlere Warteschlangenlänge
- Anzahl der Aufträge im Wartesystem k
Für die mittlere Anzahl der Aufträge im Wartesystem gilt
Abbildung in dieser Leseprobe nicht enthalten
wobei p(k) die Wahrscheinlichkeit ist, daß sich k Aufträge im Wartesystem befinden. Die mittlere Anzahl der Aufträge läßt sich auch mit dem Gesetz von Little berechnen:
Abbildung in dieser Leseprobe nicht enthalten
Analyse von Warteschlangennetzen
Als Grundlage der hier vorgestellten Summationsmethode dient der Zusammenhang zwischen dem Durchsatz λi und der mittleren Auftragszahl ki eines Knotens mit lastunabhängigen Bedienraten:
Abbildung in dieser Leseprobe nicht enthalten
Dieses Bild stimmt mit der intuitiven Vorstellung und der Erfahrung überein:
- Bei niedrigem Durchsatz ist zu erwarten, daß die mittlere Auftragszahl klein ist, da die Abstände zwischen zwei ankommenden Aufträgen sehr groß sind.
- Bei hohem Durchsatz sind die Ankunftsabstände klein, d.h. es befinden sich viele Aufträge im System, wobei eine weitere geringfügige Erhöhung des Durchsatzes eine starke Erhöhung der Anzahl der Aufträge zur Folge hat.
Für Netzknoten, bei denen die Zahl der Bedieneinheiten (m) größer oder gleich der Zahl der Aufträge (K) ist (also z.B. bei den M/G/∞-Knoten, d.h. den Typ-3-Knoten (IS) in BCMP-Netzen) ergibt sich für den Zusammenhang zwischen λi und ki eine Gerade (Gesetz von Little)
Abbildung in dieser Leseprobe nicht enthalten
Allgemein gilt, daß sich die Funktion fi(λi) immer mehr einer Geraden nähert, je größer die Zahl der Bedieneinheiten ist.
Der Zusammenhang zwischen dem Durchsatz λi im Knoten i und den sich dort aufhaltenden Aufträgen ki kann man darstellen als
Abbildung in dieser Leseprobe nicht enthalten
Die Funktion fi hat dabei folgende Eigenschaften:
- fi(0) = 0
- Der Definitionsbereich von fi ist wegen 0 ≤ ρi ≤ 1 und 0 ≤ ki ≤ K 0 ≤ λi ≤ µi⋅mi bzw. 0 ≤ λ ≤ µi⋅K (für IS)
- fi ist streng monoton steigend mit λi, d.h. es gilt für ∆λi > 0
Abbildung in dieser Leseprobe nicht enthalten
Die Monotonie ist bei lastabhängigen Bedienraten im Allgemeinen nicht gegeben und muß deshalb im Einzelfall überprüft werden. Bei "Multiple Server"-Knoten bleibt die Monotonie jedoch erhalten.
Analyse von Warteschlangennetzen mit der Summationsmethode BCMP-Netze mit einer Auftragsklasse
Zur Analyse von BCMP-Netzen können folgende Funktionen verwendet werden:
Abbildung in dieser Leseprobe nicht enthalten
Nur der letzte Fall liefert exakte Ergebnisse, die beiden anderen Fälle sind geeignete Approximationen, deren Herleitung im folgenden dargestellt wird:
• Die Gleichung für die Typen 1(M/M/1), 2 und 4 läßt sich aus der Gleichung für ki in offenen Netzen herleiten
Abbildung in dieser Leseprobe nicht enthalten
wobei noch ein Korrekturfaktor (K-1)/K eingeführt wird, so daß sich bei einer Auslastung von ρi = 1 im Knoten i alle K Aufträge aufhalten, d.h. ki = K.
- Die Idee des Korrekturfaktors wird auch bei der Gleichung für den Typ-1(M/M/m) verwendet. Die Funktion Pm(ρ) gibt dabei die Wartewahrscheinlichkeit an, daß ein ankommender Auftrag nicht sofort bedient werden kann, d.h. Pm(ρ) = P(k ≥ m). Sie berechnet sich zu
Abbildung in dieser Leseprobe nicht enthalten
Es existiert auch eine Schätzfunktion für Pm(ρ):
Abbildung in dieser Leseprobe nicht enthalten
Sind die Funktionen fi für alle Knoten i gegeben, so kann man folgende Systemgleichung für geschlossene Netze aufstellen:
Abbildung in dieser Leseprobe nicht enthalten
Mit der Beziehung λi = λ⋅ei erhält man eine Gleichung zu Bestimmung des Gesamtdurchsatzes λ des Netzes:
Abbildung in dieser Leseprobe nicht enthalten
Wegen der Monotonie der Funktionen fi und der daraus resultierenden Monotonie der Funktion g(λ) kann man den Gesamtdurchsatz λ des Netzes durch Intervallschachtelung mit folgendem Algorithmus bestimmen (für mi = ∞ setze mi = K):
{ Initialisierung }
Abbildung in dieser Leseprobe nicht enthalten
Die übrigen Leistungsgrößen ergeben sich dann folgendermaßen: Für i = 1, ..., N berechne die
- Durchsätze:
Abbildung in dieser Leseprobe nicht enthalten
- Auslastungen:
Abbildung in dieser Leseprobe nicht enthalten
- mittleren Auftragszahlen:
Abbildung in dieser Leseprobe nicht enthalten
- mittleren Antwortzeiten:
Abbildung in dieser Leseprobe nicht enthalten
Die Vorteile dieses Verfahrens sind zum einen die sehr einfache Berechnung der Leistungsgrößen des Netzes und zum anderen die Laufzeit bzw. der Platzbedarf. Für die letzten beiden Größen ergeben sich folgende Abschätzungen:
- Laufzeit:
T(N) = O(N)
- Platzbedarf:
S(N) = O(N)
Um die Leistungsfähigkeit der Summationsmethode zu verdeutlichen, sollen anhand eines repräsentativen Beispiels eines BCMP-Netzes die exakten Leistungsgrößen mit den durch die Summationsmethode berechneten Werten verglichen werden.
Beispiel:
Für das obige Rechnernetz gelten folgende Eingabegrößen:
Abbildung in dieser Leseprobe nicht enthalten
Die Anzahl der Aufträge ist K = 3.
Die exakte Berechnung der Leistungsgrößen mit der Mittelwertanalyse liefert folgendes
Ergebnis:
Abbildung in dieser Leseprobe nicht enthalten
Für das gleiche Netz ergibt sich mit der Summationsmethode folgendes Ergebnis:
Abbildung in dieser Leseprobe nicht enthalten
Die Summationsmethode lieferte auch bei zahlreichen anderen BCMP-Netzen für die Praxis ausreichend genaue Ergebnisse. In allen untersuchten Fälle ergaben sich für den Durchsatz und die Auslastung sehr gute Werte. Für die Anzahl der Aufträge und die Verweilzeit wurde eine Abweichung von 15% nicht überschritten, wobei im Mittel der Fehler bei ca. 5% lag.
Nicht-BCMP-Netze mit einer Auftragsklasse
Bei der Einführung zusätzlicher Knotentypen wird die Funktion fi(λi) = ki für Einzelbedienstationen des entsprechenden Typs herangezogen und mit einem geeigneten Korrekturfaktor versehen, so daß bei ρi = 1 die Anzahl der Aufträge im Knoten i gleich K ist und nicht gegen ∞ strebt. Mit diesem Korrekturfaktor versehen lautet z.B. die Approximationsformel für Knoten vom Typ M/G/m-FCFS
Abbildung in dieser Leseprobe nicht enthalten
wobei cb den Variationskoeffizienten des Bedienprozesses bezeichnet. Beispiel:
Abbildung in dieser Leseprobe nicht enthalten
Die Anzahl der Aufträge ist K = 30.
Eine durchgeführte Simulation liefert folgendes Ergebnis:
Abbildung in dieser Leseprobe nicht enthalten
Die Summationsmethode liefert folgendes Ergebnis:
Abbildung in dieser Leseprobe nicht enthalten
Die Untersuchung weiterer Warteschlangenmodelle ergab für den Durchsatz Abweichungen zu den Simulationsergebnissen zwischen 5% und 10%.
Warteschlangen-Netze mit mehreren Auftragsklassen
Bei Warteschlangen-Netzen mit mehreren Auftragsklassen müssen die für die Analyse wichtigen
Beziehungen erweitert werden (i = 1, ..., N, r = 1, ..., R):
Abbildung in dieser Leseprobe nicht enthalten
Es existieren jetzt R Systemgleichungen zur Bestimmung der λr:
Abbildung in dieser Leseprobe nicht enthalten
Die Funktionen fir(λir) = kir , i = 1, ..., N, r = 1, ..., R, der einzelnen Knoten haben nun folgendes Aussehen, wobei im zweiten Fall wieder das Prinzip des Korrekturfaktors verwendet wird:
Abbildung in dieser Leseprobe nicht enthalten
Zur Bestimmung der Durchsätze λr wird wieder die Intervallschachtelung wie beim Einklassenfall verwendet. Für die Laufzeit bzw. den Platzbedarf dieses Verfahrens ergibt sich folgendes:
- Laufzeit:
T(N, R) = O(N ⋅ R)
- Platzbedarf:
S(N,R) = O(N⋅ R)
Optimierung von Leistungsgrößen mit der Summationsmethode
Bei der Optimierung von Leistungsgrößen wie etwa Antwortzeiten, Durchsätze, Auslastungen, u.s.w., werden als Entscheidungsgrößen häufig die optimalen Bedienraten gesucht, welche unter bestimmten Nebenbedingungen eine vorgegebene Leistungsgröße optimieren. Im folgenden wird beispielhaft eine Durchsatzmaximierung bei linearer Kostenbeschränkung durchgeführt, d.h. für ein vorgegebenes Warteschlangennetz soll der Gesamtdurchsatz maximiert werden, wobei die Bedienraten µi einer in diesem Fall linearen Kostenbeschränkung unterliegen. Die Gesamtkosten des Netzes werden vorgegeben und können als Geldbetrag interpretiert werden, den man zur Anschaffung der einzelnen Stationen zur Verfügung hat. Formal ausgedrückt bedeutet dieser Sachverhalt folgendes:
Abbildung in dieser Leseprobe nicht enthalten
Auf die Einzelheiten der Berechnung soll dabei nicht eingegangen werden, da die Optimierung von Warteschlangennetzen nicht Thema dieses Seminars ist. Wer sich dennoch mit diesem Thema beschäftigen möchte, der sollte das Originalpaper (siehe Literaturliste) zur Summationsmethode lesen.
Um die Formeln möglichst einfach zu halten, wird auf den bei vielen Formeln sonst üblichen Korrekturfaktor verzichtet, da bei großem Auftragsvolumen dieser Korrekturfaktor (K-1)/K nahe bei 1 liegt. Bei kleinen Werten von K ist die Verwendung des Korrekturfaktors in Hinblick auf die Genauigkeit des Endergebnisses in Betracht zu ziehen. Mit den bekannten Beziehungen erhält man folgende Formel für fi(λi):
Abbildung in dieser Leseprobe nicht enthalten
für Typ 3(IS)
Gesucht sind nun die Bedienraten µi, welche des Gesamtdurchsatz maximieren und die schon erwähnte lineare Kostenbeschränkung erfüllen. Neben dieser Kostenbeschränkung müssen die
Bedienraten auch noch die Systemgleichung erfüllen, die in diesem Fall folgendes Aussehen hat:
Abbildung in dieser Leseprobe nicht enthalten
Durch Aufstellen der sogenannten Lagrangefunktion L(λ, µ1, ..., µN, y1, y2) mit Zielgröße λ und zwei Lagrangemultiplikatoren y1, y2 läßt sich durch Differenzieren nach λ, µ1, ..., µN, y1, y2 dieses Optimierungsproblem lösen. Man erhält folgendes Endergebnis:
Abbildung in dieser Leseprobe nicht enthalten
Hier lassen sich also explizit Gleichungen für den Gesamtdurchsatz und die Bedienraten angeben. Bei nichtlinearer Kostenfunktion (in der Praxis bedeutend häufiger) müssen die optimalen Bedienraten mit Hilfe von Iterationsverfahren berechnet werden. Weitere Optimierungsprobleme sind: Kostenminimierung bei festem Durchsatz, Minimierung der Antwortzeit bestimmter Stationen, u.s.w. .
Schlußbemerkung und Ausblick
Die Vorteile der Summationsmethode liegen im geringen Zeit- und Platzbedarf, in der Transparenz und in der Tatsache, daß die gesuchten Leistungsgrößen eines Netzes unmittelbar
und nicht durch die Benutzung von komplizierten Zwischengrößen wie etwa Normalisierungskonstante und Zustandswahrscheinlichkeiten berechnet werden können. Das Verfahren liefert gute Näherungswerte für die Leistungsgrößen von allgemeinen geschlossenen Warteschlangennetzen.
Obwohl durch die Einführung eines einzigen Nicht-BCMP-Knotens in ein bestehendes Netzwerk die Markoveigenschaft des Ankunftsprozesses für alle Knoten des Modells verloren geht, werden auch in diesem Fall brauchbare Werte erzielt. Dies ist auf das Aussehen der Funktion fi(λi) zurückzuführen, die auch für allgemeine Ankunftsprozesse einen ähnlichen Verlauf wie in der Abbildung auf Seite 5 aufweist.
Die mit der Summationsmethode erzielten Ergebnisse sind unter Umständen durch die Veränderung der Funktion fi(λi) noch verbesserungsfähig. Man könnte z.B. bei Nicht-BCMP- Netzen für alle Knoten eine allgemeine Ankunftsverteilung annehmen und dadurch die Berechnung realistischer gestalten. Z.B. kann die mittlere Anzahl der Aufträge in G/G/m-FCFS-
Knoten mit folgender Formel geschätzt werden:
Abbildung in dieser Leseprobe nicht enthalten
Die Größe ca ist der Variationskoeffizient des Ankunftsprozesses.
Weiterhin ist die Summationsmethode sehr gut zur Lösung von Optimierungsproblemen geeignet, da der Zusammenhang zwischen der gesuchten Größe (z.B. dem Durchsatz λ) und den Entscheidungsgrößen (z.B. die Bedienraten µ) in einfacher Weise festgelegt ist.
Literaturliste:
G. Bolch, G. Fleischmann, R. Schreppel:
"Ein funktionales Konzept zur Analyse von Warteschlangennetzen und Optimierung von Leistungsgrößen",
Informatik-Fachberichte 154 (1987), S. 327-342.
G. Bolch:
"Leistungsbewertung von Rechensystemen mittels analytischer Warteschlangenmodelle", Teubner-Verlag Stuttgart (1989).
A-priori-Fehlerabschätzung der Summationsmethode
Seien λu(t), λ0(t) die im t. Iterationsschritt bestimmten Intervallgrenzen und λ(t) der im t. Iterationsschritt berechnete Durchsatz des Warteschlangensystems. Sei außerdem λ* der
Durchsatz, der die Systemgleichung exakt löst, d.h. es gilt
Abbildung in dieser Leseprobe nicht enthalten
(analog der a-priori-Fehlerabschätzung des Intervallschachtelungsverfahrens zur Bestimmung von Nullstellen stetiger Funktionen).
Will man eine bestimmte Genauigkeit ε des Durchsatzes λ(t) in jedem Fall garantieren, d.h.
Abbildung in dieser Leseprobe nicht enthalten
dann möchte man auch eine Aussage über die Anzahl der dazu nötigen Iterationsschritte machen. Dazu wird die a-priori-Fehlerabschätzung folgendermaßen umgeformt
Abbildung in dieser Leseprobe nicht enthalten
Für die minimale Anzahl der Iterationsschritte tε, die ausgeführt werden müssen, um die geforderte Genauigkeit ε des Ergebnisses in jedem Fall erzielen zu können, gilt also
Abbildung in dieser Leseprobe nicht enthalten
Häufig gestellte Fragen
Was ist das Hauptthema dieser Analyse von Warteschlangensystemen?
Das Hauptthema ist die Analyse von allgemeinen geschlossenen Warteschlangensystemen, insbesondere die Anwendung und Leistungsfähigkeit der Summationsmethode zur Berechnung von Leistungsgrößen in diesen Systemen.
Was sind BCMP- oder Produktformnetze?
BCMP- oder Produktformnetze sind spezielle Warteschlangennetze, die sich durch die Möglichkeit der exakten Bestimmung der Leistungsgrößen auszeichnen, ohne die globalen Gleichgewichtsgleichungen zu benötigen. Sie setzen bestimmte Voraussetzungen an die Zwischenankunfts- und Bedienzeiten sowie die Warteschlangendisziplin voraus.
Welche Knotentypen werden in BCMP-Netzen unterschieden?
Es werden vier Knotentypen unterschieden: Typ-1 (M/M/m - FCFS), Typ-2 (M/G/1 - PS[RR]), Typ-3 (M/G/∞ = Infinite Server (IS)) und M/G/1 - LCFS.
Welche Leistungsgrößen sind für Warteschlangennetze relevant?
Die wichtigsten Leistungsgrößen sind Auslastung (ρ), Durchsatz (λ), Antwortzeit (t), Wartezeit (w), Warteschlangenlänge (Q) und die Anzahl der Aufträge im Wartesystem (k).
Wie funktioniert die Summationsmethode zur Analyse von Warteschlangennetzen?
Die Summationsmethode basiert auf dem Zusammenhang zwischen dem Durchsatz (λi) und der mittleren Auftragszahl (ki) eines Knotens. Sie nutzt Funktionen (fi(λi)) zur Beschreibung dieser Beziehung und löst eine Systemgleichung, um den Gesamtdurchsatz des Netzes zu bestimmen. Dieser wird dann iterativ verfeinert.
Welche Vorteile bietet die Summationsmethode?
Die Summationsmethode zeichnet sich durch einfache Berechnung, geringen Zeit- und Platzbedarf, Transparenz und die Möglichkeit zur direkten Berechnung von Leistungsgrößen ohne komplexe Zwischengrößen aus. Sie liefert gute Näherungswerte für allgemeine geschlossene Warteschlangennetze.
Wie wird die Summationsmethode auf Nicht-BCMP-Netze angewendet?
Für Nicht-BCMP-Netze wird die Funktion fi(λi) für Einzelbedienstationen des entsprechenden Typs herangezogen und mit einem Korrekturfaktor versehen, um sicherzustellen, dass bei ρi = 1 die Anzahl der Aufträge im Knoten i gleich K ist.
Wie werden Warteschlangennetze mit mehreren Auftragsklassen analysiert?
Bei Warteschlangennetzen mit mehreren Auftragsklassen werden die relevanten Beziehungen erweitert, um die verschiedenen Auftragsklassen (r) zu berücksichtigen. Es entstehen R Systemgleichungen zur Bestimmung der λr.
Kann die Summationsmethode zur Optimierung von Leistungsgrößen verwendet werden?
Ja, die Summationsmethode kann zur Optimierung von Leistungsgrößen wie Antwortzeiten oder Durchsätze verwendet werden. Ein Beispiel ist die Durchsatzmaximierung unter linearer Kostenbeschränkung, bei der die optimalen Bedienraten gesucht werden.
Wie genau ist die Summationsmethode im Vergleich zu exakten Lösungen oder Simulationen?
Die Summationsmethode liefert in vielen Fällen für die Praxis ausreichend genaue Ergebnisse. In untersuchten Fällen ergaben sich für den Durchsatz und die Auslastung sehr gute Werte. Für die Anzahl der Aufträge und die Verweilzeit wurde eine Abweichung von 15% nicht überschritten, wobei im Mittel der Fehler bei ca. 5% lag.
Was sind die Grenzen der Summationsmethode?
Obwohl die Summationsmethode gut funktioniert, kann die Einführung eines einzigen Nicht-BCMP-Knotens in ein bestehendes Netzwerk die Markoveigenschaft des Ankunftsprozesses für alle Knoten des Modells verloren geht. Es werden weiterhin brauchbare Werte generiert, aber die Ergebnisse sind unter Umständen durch die Veränderung der Funktion fi(λi) noch verbesserungsfähig.
Wie lässt sich die Genauigkeit der Summationsmethode verbessern?
Eine Möglichkeit zur Verbesserung der Genauigkeit besteht darin, bei Nicht-BCMP-Netzen für alle Knoten eine allgemeine Ankunftsverteilung anzunehmen und dadurch die Berechnung realistischer zu gestalten, z.B. durch Verwendung von Formeln zur Schätzung der mittleren Anzahl der Aufträge in G/G/m-FCFS-Knoten.
Was ist die A-priori-Fehlerabschätzung der Summationsmethode?
Die A-priori-Fehlerabschätzung dient dazu, die minimale Anzahl der Iterationsschritte zu bestimmen, die ausgeführt werden müssen, um eine geforderte Genauigkeit ε des Ergebnisses in jedem Fall erzielen zu können. Sie gibt also eine Garantie, dass die berechneten Werte innerhalb eines bestimmten Fehlers liegen.
- Arbeit zitieren
- Michael Savoric (Autor:in), 1995, Die Summationsmethode, München, GRIN Verlag, https://www.hausarbeiten.de/document/111620
