Decomposition of discrete-time open tandem queues with Poisson arrivals and general service times

In der Grobplanungsphase vernetzter Logistik- und Produktionssysteme ist man häufig daran interessiert, mit geringem Berechnungsaufwand eine zufriedenstellende Approximation der Leistungskennzahlen des Systems zu bestimmen. Hierbei bietet die Modellierung mittels zeitdiskreter Methoden gegenüber der zeitkontinuierlichen Modellierung den Vorteil, dass die gesamte Wahrscheinlichkeitsverteilung der Leistungskenngrößen berechnet werden kann. Da Produktions- und Logistiksysteme in der Regel so konzipiert sind, dass sie die Leistung nicht im Durchschnitt, sondern mit einer bestimmten Wahrscheinlichkeit (z.B. ... mehr95%) zusichern, können zeitdiskrete Warteschlangenmodelle detailliertere Informationen über die Leistung des Systems (wie z.B. der Warte- oder Durchlaufzeit) liefern.

Für die Analyse vernetzter zeitdiskreter Bediensysteme sind Dekompositionsmethoden häufig der einzig praktikable und recheneffiziente Ansatz, um stationäre Leistungsmaße in den einzelnen Bediensystemen zu berechnen. Hierbei wird das Netzwerk in die einzelnen Knoten zerlegt und diese getrennt voneinander analysiert. Der Ansatz basiert auf der Annahme, dass der Punktprozess des Abgangsstroms stromaufwärts liegender Stationen durch einen Erneuerungsprozess approximiert werden kann, und so eine unabhängige Analyse der Bediensysteme möglich ist. Die Annahme der Unabhängigkeit ermöglicht zwar eine effiziente Berechnung, führt jedoch zu teilweise starken Approximationsfehlern in den berechneten Leistungskenngrößen.

Der Untersuchungsgegenstand dieser Arbeit sind offene zeitdiskrete Tandem-Netzwerke mit Poisson-verteilten Ankünften am stromaufwärts liegenden Bediensystem und generell verteilten Bedienzeiten. Das Netzwerk besteht folglich aus einem stromaufwärts liegenden M/G/1-Bediensystem und einem stromabwärts liegenden G/G/1-System. Diese Arbeit verfolgt drei Ziele, (1) die Defizite des Dekompositionsansatzes aufzuzeigen und dessen Approximationsgüte mittels statistischer Schätzmethoden zu bestimmen, (2) die Autokorrelation des Abgangsprozesses des M/G/1-Systems zu modellieren um die Ursache des Approximationsfehlers erklären zu können und (3) einen Dekompositionsansatz zu entwickeln, der die Abhängigkeit des Abgangsstroms berücksichtigt und so beliebig genaue Annäherungen der Leistungskenngrößen ermöglicht.

Im ersten Teil der Arbeit wird die Approximationsgüte des Dekompositionsverfahrens am stromabwärts liegenden G/G/1-Bediensystem mit Hilfe von Linearer Regression (Punktschätzung) und Quantilsregression (Intervallschätzung) bestimmt. Beide Schätzverfahren werden jeweils auf die relativen Fehler des Erwartungswerts und des 95%-Quantils der Wartezeit im Vergleich zu den simulierten Ergebnissen berechnet. Als signifikante Einflussfaktoren auf die Approximationsgüte werden die Auslastung des Systems und die Variabilität des Ankunftsstroms identifiziert.

Der zweite Teil der Arbeit fokussiert sich auf die Berechnung der Autokorrelation im Abgangsstroms des M/G/1-Bediensystems. Aufeinanderfolgende Zwischenabgangszeiten sind miteinander korreliert, da die Abgangszeit eines Kunden von dem Systemzustand abhängt, den der vorherige Kunde bei dessen Abgang zurückgelassen hat. Die Autokorrelation ist ursächlich für den Dekompositionsfehler, da die Ankunftszeiten am stromabwärts liegenden Bediensystem nicht unabhängig identisch verteilt sind.

Im dritten Teil der Arbeit wird ein neuer Dekompositionsansatz vorgestellt, der die Abhängigkeit im Abgangsstroms des M/G/1-Systems mittels eines semi-Markov Prozesses modelliert. Um eine explosionsartige Zunahme des Zustandsraums zu verhindern, wird ein Verfahren eingeführt, das den Zustandsraum der eingebetteten Markov-Kette beschränkt. Numerischen Auswertungen zeigen, dass die mit stark limitierten Zustandsraum erzielten Ergebnisse eine bessere Approximation bieten als der bisherige Dekompositionsansatz. Mit zunehmender Größe des Zustandsraums konvergieren die Leistungskennzahlen beliebig genau.

During draft planning of interconnected logistics and production systems, decision makers are often interested in determining a satisfactory approximation of the system's key performance indicators with little computational effort. Employing discrete-time queueing models offers an advantage over continuous-time modelling in that the entire probability distribution of the performance parameters can be calculated. Since production and logistics systems are typically designed to guarantee performance not on average, but with a given probability (e.g. 95%), discrete-time queueing models can provide more detailed information about the system's performance, such as waiting or throughput time.
... mehr

When it comes to analysing open queueing networks, decomposition methods often are the only feasible and computationally efficient approach to calculate steady-state performance measures in the individual discrete-time queues. The method decomposes the network into individual nodes, which are analysed in isolation. The approach is based on the assumption that a renewal process can approximate the point process of the departure stream of upstream stations, and thus an independent analysis of the queueing systems is possible. Although the assumption of independence is computationally attractive, performance results obtained with the renewal decomposition approach might be subject to severe approximation errors.

In this thesis, we study discrete-time open tandem networks with external Poisson arrivals and generally distributed service times. The external Poisson arrival stream makes the upstream queue of type M/G/1 while the downstream queue is of type G/G/1. This thesis pursues three goals, (1) to reveal the deficits of the renewal decomposition approach and to determine its approximation quality by means of statistical estimation methods, (2) to model the auto-correlation of the departure point process of the M/G/1-queue in order to explain the cause of the approximation error, and (3) to develop a decomposition approach that takes into account the dependence of the departure flow and thus allows for a converging accurate calculation of the performance parameters.

In the first part of the thesis, we analyse the approximation quality of the renewal decomposition method at the downstream queue based on linear regression (point estimation) and quantile regression (interval estimation). The dependent variables of the regression models are the relative error of the expected value and 95% percentile of the waiting time compared to a simulation. Based on the ANOVA, we identify the system's utilisation and the arrival stream's variability as main drivers influencing the approximation quality.

The second part of the thesis focuses on the computation of the auto-correlation in the departure stream of the upstream M/G/1-queue. Consecutive inter-departure times are auto-correlated because the departure time of a customer depends on the system state left behind by the previous customer. Auto-correlation in the connecting stream is causal for the approximation error, as the arrival times at the downstream station are not independently identically distributed.

In the third part of the thesis, we present a novel decomposition approach that models the inter-dependency in the departure stream with a semi-Markov process. To prevent state-space explosion, we introduce a procedure to limit the state space of the embedded Markov chain. Our numerical results show that the performance measures obtained with a limited state space provide better approximations than the renewal decomposition approach. As the state space increases, the novel decomposition method converges arbitrarily accurate.