Fork/Join-Warteschlangennetze

Kapitel 2 Das Dekompositionsverfahren nach Kühn/Whitt (S. 17-18)

Das Dekompositionsverfahren nach Kühn/Whitt ist ein Analyseverfahren für eine allgemeine Klasse offener Warteschlangennetze. Es wurde Mitte der 70er Jahre von P.J. Kühn vorgestellt [59, 60] und diente zunächst der Analyse von Telekommunikationssystemen. Eine entsprechende Software–technische Realisierung wurde zu Beginn der 80er Jahre von W. Whitt mit dem Queueing Network Analyzer präsentiert [94, 93]. Das Ziel des Dekompositionsverfahrens liegt in der zeiteffizienten Analyse von offenen Nicht–Produktform–Netzen unter gewissen Approximationsannahmen. Die wesentliche Lösungsidee besteht darin, ein Warteschlangennetz in eine Menge disjunkter Subnetze zu zerlegen und diese isoliert voneinander bzgl. ihres Ankunftsverhaltens zu analysieren. Die Ankunftsprozesse und die aus der Analyse resultierenden Abgangsprozesse bilden somit die Schnittstelle der Subnetze zu ihrer Umgebung.

Prinzipiell bestehen somit die zentralen Schritte des Dekompositionsverfahrens in einer geeigneten Zerlegung eines Warteschlangennetzes in eine Menge disjunkter Subnetze, die sich unter Zeitaspekten e.zient analysieren lassen, und in der Bestimmung des Verkehrs.usses innerhalb des Netzes, d.h. in der Bestimmung der Ankunfts– und Abgangsprozesse der Subnetze. Im allgemeinen ist die isolierte Analyse der Subnetze und die Bestimmung des Verkehrsflusses wechselseitig abhängig, da einerseits die Analyse der Subnetze die Kenntnis des Verkehrsflusses voraussetzt und andererseits die Bestimmung des Verkehrs.usses die vorherige Analyse der Subnetze impliziert.

Zur detaillierten Beschreibung des Dekompositionsverfahrens nach Kühn/Whitt wird im folgenden zunächst die dem Verfahren zugängliche Modellklasse spezi.ziert. Auf dieser Basis werden im Anschluß die Grundlagen der Analyse erläutert.

2.1 Analysierbare Modellklasse

Das Dekompositionsverfahren nach Kühn/Whitt eignet sich zur Analyse offener Warteschlangennetze mit einer Kundenklasse und einer festen Anzahl an Stationen. Die Stationen besitzen je einen einzigen Bediener, der an der Station eintre.ende Kunden gemäß ihrer Ankunftsreihenfolge bedient (FCFS). Weiterhin zeichnen sich die Stationen durch unbegrenzte Warter äume aus. Kundenübergänge sind potentiell zwischen allen Stationen des Netzes möglich. Insbesondere sind Ankünfte aus der Umgebung und Abgänge in die Umgebung an allen Netzstationen erlaubt.

Das dynamische Verhalten der Kunden im Netz ist durch ihre Zwischenankunfts– und Bedienzeitverteilungen an den Stationen des Netzes sowie durch Routingwahrscheinlichkeiten zwischen den Stationen gekennzeichnet. Im Unterschied zu Produktform–Netzen dürfen die Zwischenankunftszeiten und Bedienzeiten beliebige kontinuierliche nicht–negative Wahrscheinlichkeitsverteilungen besitzen. Kundenübergänge zwischen den Stationen erfolgen dagegen ebenso wie bei Produktform–Netzen gemäß Markov’schem Routing, d.h. nach Beendigung der Bedienung an der i–ten Netzstation wechseln Kunden mit der festen Wahrscheinlichkeit qij zur j–ten Netzstation für eine weitere Bedienung.

2.2 Grundlagen der Analyse

Zur Analyse eines derartigen Warteschlangennetzes sind bisher keine exakten allgemeinen Verfahren bekannt. Schwierigkeiten bereiten insbesondere die allgemeinen Zwischenankunfts– und Bedienzeitverteilungen. In dem Dekompositionsverfahren nach Kühn/Whitt werden daher die Ankunftsprozesse aller Stationen durch stationäre Erneuerungsprozesse approximiert, d.h. es wird davon ausgegangen, daß die Zwischenankunftszeiten an den Stationen unabhängig identisch verteilt sind. Ebenso wird davon ausgegangen, daß die Bedienzeiten aller Kunden je Station unabhängig identisch verteilt sind. Ferner werden bei der Analyse lediglich die ersten beiden Momente dieser Verteilungen in Form des Erwartungswertes bzw. der Rate und des Variationskoe.zienten berücksichtigt.