Die Warteschlangentheorie, auch Bedienungstheorie genannt, ist ein Teilgebiet der Wahrscheinlichkeitsrechnung, welches sich mit der Modellierung und Analyse von sogenannten Bedienungssystemen beschäftigt. Beispiele für Bedienungssysteme sind Telefonzentralen, Fertigungsprozesse, Reparaturwerkstätten, Läden, Krankenhäuser, Häfen, u.v.a.m..

Ein solches System besteht aus einer gewissen Zahl von Bedienungseinheiten, auch Server genannt, (Apparate, Leitungen, Maschinen, Geräte, Kassen, Ärzte, Ankerplätze usw.), und sogenannten Forderungen (Aufträge, Fertigungslose, Kunden, Patienten, Schiffe usw.), die, bedient’ werden wollen, bzw. in der, Warteschlange’ stehen.

Die Forderungen treffen nacheinander oder in Gruppen zu gewissen zufälligen Zeitpunkten ein und bilden den sogenannten Forderungsstrom. Die zufälligen Zeitabstände zwischen zwei Forderungen heißen Zwischenankunfts- bzw. Pausenzeiten. Die Bedienung einer Forderung dauert ebenfalls eine zufällige Bedienzeit. Danach wird der Bedienapparat wieder frei zur Bedienung einer anderen Forderung.

Die Bedienungssysteme werden wesentlich durch die für Pausen- und Bedienzeiten verwendeten Verteilungen charakterisiert. Jedes Bedienungssystem hat darüber hinaus eine bestimmte Bedienorganisation, die die Behandlung der Forderung durch das System charakterisiert. Solche Charakteristika von Bedienungssystemen sind u. a.:

1. Die Verlustart: Man unterscheidet reine Warte-, reine Verlust-, und gemischte Warteverlustsysteme. (Eine Telefonzentrale beispielsweise ist dann ein reines Verlustsystem, wenn eintreffende Anrufer das Besetztzeichen hören, wenn die Leitung besetzt ist).
2. Die Aufnahmekapazität der Warteschlange: In reinen Wartesystemen ist diese unendlich groß; bei Warte-Verlustsystemen ist sie beschränkt.
3. Die Warteschlangendisziplin, d. h. Regeln, nach welchen ein Kunde aus der Warteschlange ausgewählt wird. Man unterscheidet zum Beispiel zwischen FIFO (first-in-first-out, d. h. wer zuerst kommt, wird zuerst bedient), LIFO (last-in- first-out, d. h. wer zuletzt kommt, wird zuerst bedient), und verschiedenen Prioritätsregeln.
4. Die Zugänglichkeit der Apparate: Es wird festgelegt, wieviele Aparate den Kunden bedienen, und ob die Apparate unabhängig voneinander arbeiten oder nicht.

Zur Kennzeichnung wesentlicher Charakteristika von Bedienungssystemen wird i. allg. die Kendall- Symbolik verwendet.

Da die Zwischenankunfts- und Bedienzeiten zufällig sind, sind es auch die interessierenden Kenngrößen eines Systems, wie der sich in jedem Zeitpunkt ergebende Systemzustand und Größen zur Charakterisierung des Schicksals der Forderungen, wie Warte- und Verweilzeiten.

Grundaufgabe der Warteschlangentheorie ist es, für ein Bedienungssystem aus den gegebenen Charakteristika, insbesondere den Pausen- und Bedienzeitverteilungen, verschiedene wichtige Kenngrößen des Systems und der Forderungen zu berechnen oder zu schätzen.

Im einzelnen werden zum Beispiel Kenngrößen der folgenden Art bestimmt:

1. Die Wahrscheinlichkeit, daß eine eintreffende Forderung verloren geht, (z. B. weil die Warteschlange voll ist).
2. Die Wahrscheinlichkeit, daß eine eintreffende Forderung warten muß.
3. Die Verteilungsfunktion bzw. der Erwartungswert der zufälligen Wartezeit.
4. Die Wahrscheinlichkeitsverteilung bzw. der Erwartungswert der Warteschlangenlänge.
5. Die Wahrscheinlichkeitsverteilung für die Anzahl belegter Bedienungsgeräte im System.
6. Die Wahrscheinlichkeit dafür, daß ein Bedienungsgerät belegt ist (Auslastung des Gerätes).
7. Die Wahrscheinlichkeitsverteilung für die Gesamtzahl der Forderungen im System.

Die mathematischen Methoden zur Berechnung der Kenngrößen hängen vom Typ des Bedienungssystems ab. Sind sämtliche Pausenzeiten unabhängig und exponentialverteilt mit konstantem Parameter, und gilt das gleiche für die Bedienzeiten, so ist der zufällige Prozeß der Anzahl der Forderungen im System zur Zeit t eine homogene Markow-Kette. Solche Bedienungssysteme werden auch Markowsche Systeme genannt. Diese sind sehr gut untersucht worden. Die Bestimmung der zeitabhängigen Kenngrößen bzw. Zustandswahr- scheinlichkeiten führt zur Aufstellung und Lösung von Systemen von Differentialgleichungen.

Meist wird das Bedienungssystem im sogenannten eingeschwungenen, stationären Zustand (auch Gleichgewichtszustand genannt) betrachtet, in dem man annimmt, daß sich die Charakteri- stika des Bedienungssystems im Ablauf der Zeit nicht mehr ändern. Dann sind auch die o.g. Wahrscheinlichkeiten für die Zustände des Bedienungs- sytems nicht mehr zeitabhängig. Diese bilden die stationären Zustandswahrscheinlichkeiten. Das System von Differentialgleichungen zu ihrer Bestimmung geht dann über in ein System linearer algebraischer Gleichungen, das relativ leicht lösbar ist.

Andererseits werden die Kenngrößen des Systems nicht für jeden beliebigen Zeitpunkt, sondern für den Grenzfall t → ∞ bestimmt. Antwort auf die Frage nach der Existenz entsprechender Grenzwerte geben die sogenannten statistischen Ergo- densätze.

Besitzen nicht sämtliche Pausen- und Bedienzeiten eine Exponentialverteilung, sondern auch Erlang- oder Hypererlangverteilungen, können auf der Basis der Erlangschen Phasenmethode ebenfalls Markow-Ketten zur Analyse des Systems herangezogen werden. Bei beliebigen Verteilungen lassen sich auf der Basis dieser Methode noch approximative Aussagen für die Kenngrößen gewinnen.

Betrachtet man Systeme mit anderen Systemzuständen, z. B. mit Ausfall- und Reparaturzeiten, so erfordert das die Einführung anderer Prozesse, wie z. B. Erneuerungs- oder Punktprozesse. Aus dieser Aufgabenstellung heraus hat sich die Erneuerungstheorie gebildet.

Schließlich ist es oft wichtig, Kenngrößen von Bedienungssystemen nicht in beliebigen Zeitpunkten, sondern in besonders interessierenden, sogenannten eingebetteten Zeitpunkten, zu bestimmen. Man hat es dann mit den eingebetteten stochasti- schen Prozessen zu tun. Eine interessante Aufgabe der Warteschlangentheorie besteht dann darin, Methoden zur Herleitung von Beziehungen zwischen stationären Charakteristika bzw. Kenngrößen in eingebetteten und beliebigen Zeitpunkten zu entwickeln.

Sehr komplexe Systeme lassen sich nur unzureichend durch Bedienungsmodelle beschreiben. Mit der Entwicklung der Computer- und Softwaretechnik geht man dazu über, parallel zur Beschreibung durch bedienungstheoretische Modelle das Verhalten der Forderungen in solchen Systeme zu simulieren und die o.g. Kenngrößen auf der Basis mehrerer Simulationsläufe zu schätzen. Statistische Fragestellungen sind dann wieder die nach der Güte solcher Schätzungen. In den letzten Jahren sind komfortable Simulationssprachen zur Simulation paralleler Abläufe in Bedienungssystemen entwickelt worden.

Die Hauptanwendung von Methoden der Warteschlangentheorie und der Simulation von Bedienungssystemen ist die Optimierung von Fertigungsabläufen. Hier geht es zum Beispiel um folgende Fragen:

1. Wieviele Maschinen eines bestimmten Typs werden benötigt, um eine unverzügliche Bearbeitung der Teile zu gewährleisten? Sind es zu wenige, bilden sich Warteschlangen, und damit Zeitverzögerungen, die zu finanziellen Verlusten führen können. Sind es zu viele, so kommt es zu einer übermäßigen Ausweitung von Stillstandszeiten und damit ebenfalls zu finanziellen Verlusten.
2. Wieviele lokale und zentrale Lagerplätze muß man in der Fertigungshalle höchstens einrichten, um die wartenden Aufträge zwischenzulagern?
3. Welche Mischung von Produkten ist in das Fertigungssystem einzuschleusen, so daß die Auslastung der Maschinen gleichmäßig hoch ist?
4. Welche Warteschlangendisziplin wirkt sich am günstigsten auf die Verweilzeit der Lose im System aus? Ist beispielsweise die Regel, aus der Warteschlange das Los mit der kürzesten Bearbeitungszeit (KOZ-Kürzeste Operationszeitregel) zuerst zu entnehmen besser als die sogenannte Lieferterminregel (LT), die besagt, dasjenige Los zu entnehmen, das die kürzeste noch verbleibende Zeit bis zur Auslieferung hat?

Literatur

[1] Gnedenko, B.W.; König, D.: Handbuch der Bedienungstheorie Bd. 1 und 2. Akademie-Verlag Berlin, 1983/84.

[2] Gnedenko, B. V.; Kovalenko, I. N.: Introduction to queu- eing theory (2nd ed.). Birkhäuser-Verlag Boston, 1989.

[3] Kleinrock, L.: Queuing Systems, Theory, Vol.I & II. John Wiley New York, 1975.

[4] König, D.; Stoyan D.: Methoden der Bedienungstheorie. Vieweg-Verlag Braunschweig, 1976.