Queueing Systems in a Random Environment

Abstract

Queueing networks with product-form steady-state distribution have found many fields of applications, e.g. production systems, telecommunications, and computer system modeling. The success of this class of models and its relatives stems from the simple structure of the steady-state distribution which provides access to easy performance evaluation procedures. Starting from the work of Jackson [Jac57] various generalizations have been developed.

In real world queueing systems are not isolated and interact with their environment. Adding a random environment to a model usually makes the model more realistic but also more complex to analyze. Nevertheless, under some conditions it is still possible to obtain analytical results. A branch of research which recently has found interest are queueing networks in a random environment with product form steady-state distributions.

The main theoretical contributions of this thesis are twofold: (i) We develope a general theory that comprise models with stationary product-form distribution in inventory theory in [Sch04] and Jackson networks with unreliable nodes with stationary product-form distribution in [Sau06]. An important property of the resulting general model is that the queueing system and the environment interact in both directions: the queues can influence the environment and the environment can influences the queues. (ii) With respect to applications we show how different models known from literature can be interpreted in terms of the general theory, construct new models in various applications, and develope an approximation method.

In Part I we analyze single-queue systems. In Section 1 we introduce a loss system. In Section 2 we generalize product form lost-sales inventory models from [Sch04] and several other published papers with related models as a loss system with exponential service time. The term loss means that customers get lost when the environment stays in some special states -- the blocking states. In Section 2.1.4 we develop an approximation method for system without loss of customers based on loss systems. In Section 2.2 we apply our loss system results in fields different from inventory management: we analyze in detail an unreliable server with preventive maintenance in Section 2.2.4, a node of a wireless sensor network in Section 2.2.5, and a crusher station in open-pit mining in Section 2.2.6.

In Section 3 we analyze the Markov chain embedded at departure instants of the loss system. The embedded Markov chains are an important tool for analyzing queueing system with general service times -- the M/G/1/infinity queues. The famous and frequently used result in classical M/G/1/infinity theory is that the steady-state distribution of an M/G/1/infinity system as continuous time process and as embedded Markov chain, observed at departure times, are the same. We show that this is in general not true for the steady-state distribution of loss systems. We use an embedded Markov chain analysis to extend our results from Section 2 to some loss systems with general service times.

In Part II we extend our results for a single-queue loss system to Jackson networks in a random environment. We replace the concept of loss of customers by special rerouting regimes. We establish a connection between these rerouting regimes and randomized random walks. In Section 8 we consider systems where the interaction between environment and queuing system depend on the number of customers in the system. This extension finally allows us to include results about Jackson networks with unreliable nodes from [Sau06] as special cases.

Warteschlangennetze, deren stationäre Verteilung eine Produktform hat, sind in unterschiedlichen Bereichen angewendet worden, zum Beispiel: Produktionssysteme, Telekommunikation und Modellierung von Rechnersystemen. Ihren Erfolg haben sie ihrer einfachen Struktur der stationärer Verteilung zu verdanken. Sie vereinfacht die Analyse von Leistungskenngrößen der zu modellierenden Systeme. Aufbauend auf der grundlegenden Arbeit von Jackson [Jac57] wurden weitere Verallgemeinerungen entwickelt.

In der realen Welt sind Warteschlangensysteme nie isoliert. Sie befinden sich in einer Umgebung, mit der sie interagieren. Das Hinzufügen einer Umgebung zu einem reinen Warteschlangenmodell führt häufig zu einem besseren Gesamtmodell. Gleichzeitig wird die mathematische Analyse dieses Modells schwieriger und komplexer. Unter speziellen Bedingungen ist es dennoch möglich, für derartige Systeme analytische Lösungen zu erhalten. Viele solche Systeme, gehören zu Warteschlangennetzwerken in einer zufälligen Umgebung, deren stationäre Verteilung eine Produktform hat.

Die Hauptbeiträge dieser Dissertation liegen in zwei Bereichen: (i) Wir entwickeln eine allgemeine Theorie, die Modelle mit stationärer Produktformverteilung aus den Lagerhaltungsmodellen aus [Sch04] und Jackson-Netzwerke mit unzuverlässigen Knoten mit stationärer Produktformverteilung aus [Sau06] gleichzeitig umfaßt. Eine wichtige Eigenschaft dieses allgemeinen Modells ist, dass die Warteschlangensysteme und die Umgebung sich gegenseitig beeinflussen: die Warteschlangen können die Umgebung beeinflussen und die Umgebung die Warteschlangen. (ii) Auf Anwendungen bezogen, zeigen wir, dass viele aus der Literatur bereits bekannte Modelle sich mit Hilfe dieser allgemeinen Theorie darstellen lassen. Wir stellen neue Modelle für unterschiedliche Bereiche vor und entwickeln ein Näherungsverfahren.

In Teil I untersuchen wir Systeme mit einer einzigen Warteschlange. In Abschnitt 2 stellen wir ein Verlustsystem (loss system) vor . In Abschnitt 2verallgemeinern wir Lagerhaltungsmodelle mit Kundenverlust aus [Sch04] und mehrere ähnliche publizierte Modelle. Diese Verallgemeinerung bezeichnen wir als Verlustsystem. Der Bergriff Verlust (loss) bezieht sich auf die Modellannahme, dass Kunden verlorengehen, solange die Umgebung in sogenannten blockierenden Zuständen ist. In Abschnitt 2.1.4 entwickeln wir ein Näherungsverfahren für Systeme ohne Kundenverlust, das auf Systemen mit Kundenverlust basiert. In Abschnitt 2.2 nutzen wir Ergebnisse für Verlustsysteme in anderen Bereichen außerhalb der Lagerhaltung: wir untersuchen detailliert ein Warteschlangensystem mit einem unzuverlässigen Bediener mit präventiver Wartung in Abschnitt 2.2.4, einen Knoten in einem drahtlosen Sensornetzwerk in Abschnitt 2.2.5 und eine Zerkleinerungsanlage im Bergbau in Abschnitt 2.2.6.

In Abschnitt 3 untersuchen wir eingebettete, zu Kundenabgangszeiten beobachtete, Markov-Ketten von Verlustsystemen. Eingebetteten Markov-Ketten sind ein wichtiges Werkzeug für die Untersuchung der Warteschlangensysteme mit allgemeinen Bedienzeitverteilungen, das heißt Warteschlangensysteme vom Typ M/G/1/Unendlich. Ein bekanntes und häufig benutztes Ergebnis in der klassischen M/G/1/Unendlich Theorie ist, dass für ein M/G/1/Unendlich System die stationären Verteilungen des Prozesses in stetiger Zeit und dijenige der eingebetteten Markov-Kette, betrachtet zu Kundenabgangszeiten, übereinstimmen. Wir zeigen, dass dies für die stationären Verteilungen eines Verlustsystems im Allgemeinen nicht gilt. Wir benutzen Markov-Ketten-Methoden um unsere Ergebnisse für exponentielle Bedienzeiten aus Abschnitt 2 in einigen Fällen auf Systeme mit allgemeiner Bedienzeit zu erweitern.

In Teil II erweitern wir unsere Ergebnisse für Verlustsysteme mit einer Warteschlange zu Jackson-Netzwerken in zufälliger Umgebung. Wir ersetzen das Konzept des Kundenverlustes durch spezielle Reroutingregeln. Wir stellen einen Zusammenhang her zwischen unterschiedlichen Reroutingregeln und randomisierten Irrfahrten. Zum Schluss, in Abschnitt 8, erlauben wir zusätzlich, dass die Wechselwirkung zwischen der Umgebung und dem Warteschlangennetz von der Kundenzahl im Gesamtsystem abhängen kann. Diese Erweiterung ermöglicht es, die Ergebnisse über Jackson-Netzwerke mit unzuverlässigen Knoten aus [Sau06] als Spezialfälle der gemeinsamen Theorie zu erfassen.