LaTeX-examples/documents/Warteschlangen/pantelis.tex

%-----------------------------------------------------------------------------
\chapter{Einleitung}
%-----------------------------------------------------------------------------
Wir betrachten folgendes grundlegendes Modell:  Kunden kommen zu
zufälligen Zeiten  $T_{1} < T_{2} < \dots <T_{n} < \dots$ im System an,
wobei $T_{n}$
die \index{Ankunftszeit}Ankunftszeit des $n$-ten Kunden bezeichnet.

Ein oder mehrere Bediener arbeiten die Schlange ab und für jeden Kunden
wird eine bestimmte \index{Bedienzeit}\enquote{Bedienzeit} benötigt. Es sei $x_{n}$ die Bedienzeit
des $n$-ten Kunden.
Die Reihenfolge der Bedienung der Kunden wird durch
die sogenannte \index{Disziplin}\enquote{Disziplin} der Warteschlange bestimmt.Wir nehmen meistens
FCFS (First Come First Serve) an. Andere Möglichkeiten wären LCFS (Last
Come First Serve) oder \enquote{Prioritäten}.

Folgende Annahmen werden getroffen:
\begin{enumerate}
\item Die $x_{n}$ sollen unabhängig und identisch verteilt sein.
\item $t_{n}$ ist die $n$-te \index{Zwischenankunftszeit}Zwischenankunftszeit also $t_{n}= T_{n} -
T_{n-1}$,  $T_{0}=0$ (Die Zeit zwischen der Ankunft des $n$-ten und des
$(n-1)$-ten Kunden). Die $t_{n}$ sind auch unabhängig und identisch
verteilt.
\end{enumerate}
Wir verwenden folgende \index{Warteschlangen!Kurznotation}Kurznotation für
Warteschlangen: $A/B/s$.

$A \dots$ Verteilung der Zwischenankuftszeiten $t_{n}$, wobei $a$ die Dichte
von $t_{n}$ ist. \\
$B \dots$ Verteilung der Bedienzeiten $x_{n}$ wobei $b$ die Dichte von
$x_{n}$ ist. \\
$s \dots$ Anzahl der Bediener \index{Server}(Server).

\begin{minipage}{\textwidth}
Kurznotationen für Verteilungen sind:\\
$M$ $\dots$ \index{Verteilung!Exponential-}Exponentialverteilung (\enquote{memoryless}). \\
\end{minipage}
Dichtefunktion:
\begin{displaymath}
f(x) = \lambda e^{-\lambda x} \qquad x\geq 0.
\end{displaymath}
$E_{n}$ $\dots$ \index{Verteilung!Erlang-}Erlangverteilung: Die Summe von $n$ unabhängigen
Exponentialverteilungen.\\
 Dichtefunktion:
\begin{displaymath}
f(x)=\frac{\lambda^{n}x^{n-1}}{(n-1)!}e^{-\lambda x} \qquad x\geq 0.
\end{displaymath}
$H$ $\dots$ \index{Verteilung!Hyperexponentelle}Hyperexponentielle Verteilung: Die Mischung von unabhängigen
Exponentialverteilungen. Wir haben $p_{1} \dots p_{n}$,  $p_{i} \geq 0$,
 und
$\sum_{i=1}^{n} p_{i} = 1$, $\lambda_{1} \dots \lambda_{n} \geq 0$. \\
Dichtefunktion:
\begin{displaymath}
f(x)=\sum_{i=1}^{n} p_{i} \lambda_{i} e^{-\lambda_{i}x}.
\end{displaymath}
$D$ $\dots$ \index{Verteilung!Deterministische}Deterministisch: Ein fixer Wert wird angenommen. \\
$G$ $\dots$ \index{Verteilung!Allgemeine}\enquote{General}: Allgemeine Verteilung (alles, was nicht vorher erwähnt
wurde).

Die Sonderstellung der Exponentialverteilung ist begründet durch ihre
Gedächtnislosigkeit. Falls nämlich etwa eine Wartezeit
exponentialverteilt ist, und wir schon t Zeiteinheiten gewartet haben, so
ist die Verteilung der restlichen Wartezeit gegeben durch
\begin{eqnarray*}
\PP(\mbox{restliche Wartezeit} \geq x \mid \mbox{schon $t$
gewartet}) = \\
= \PP(T \geq t+x \mid T \geq t) = \frac{\PP(T \geq t+x)}{\PP(T\geq t)} ~.
\end{eqnarray*}
Angenommen $T$  sei exponentialverteilt $\Rightarrow$ $\PP(T \geq t) =
e^{-\lambda t}$  $\Rightarrow$
\begin{displaymath}
\frac{\PP(T \geq t+x)}{\PP(T \geq t)} = \frac{e^{-\lambda
(t+x)}}{e^{-\lambda
t}}= e^{-\lambda x},
\end{displaymath}
also unabhängig davon, wie lange wir schon vorher gewartet haben.

Es gibt abgeleitete Größen, die das Verhalten der Warteschlange
beschreiben wie:
\begin{enumerate}
\item $w_{n}$ $\dots$ \index{Wartezeit}Wartezeit des $n$-ten Kunden.
\item $z_{n} = w_{n} + x_{n} \dots$ Zeit, die der $n$-te Kunde im System
verbringt.
\item $N_{t}$ $\dots$ Anzahl der Kunden, die zum Zeitpunkt $t$ im System
sind ($=$ wartende + eventuell die, die gerade bedient werden).
\end{enumerate}
Es gibt einige Fragen, die uns interessieren:
\begin{enumerate}
\item Die Verteilungen von $w_{n}$, $z_{n}$, $N_{t}$.
\item Gibt es Grenzverteilungen für $n \rightarrow \infty$ bzw. $t
\rightarrow \infty$ (d.h. pendelt sich das Verhalten der Schlange auf
einen stationären Zustand ein?) und Bestimmung der Grenzverteilungen.
\item Erwartungswerte der Grenzverteilungen in 2.
\item Abschätzungen für 3.
\end{enumerate}
Die Aufgaben sind hier in abnehmender Schwierigkeit geordnet. Leider sind
die genauen Verteilungen 1. nicht leicht zu bestimmen, also beschränken
wir uns meist auf 2. ; im ganz allgemeinen Fall wird es sogar notwendig
sein, nur Abschätzungen zu betrachten.
%-----------------------------------------------------------------------------
\chapter{Erste Resultate}
\section{Eine Rekursion für die Wartezeit}
%----------------------------------------------------------------------------
Wir wollen nun die Wartezeit des $(n+1)$-ten Kunden durch die des $n$-ten
Kunden ausdrucken. Dazu ist
\begin{enumerate}
\item $T_{n} \ldots $ die Ankunftszeit des $n$-ten Kunden.
\item $T_{n} + w_{n} \ldots$ die Zeit, wenn der $n$-te Kunde bedient wird.
\item $T_{n} + w_{n} + x_{n} \ldots$ die Zeit wenn der $n$-te Kunde geht.
Ab jetzt kann der $(n+1)$-te bedient werden.
\item $T_{n+1} = T_{n} + t_{n+1} \ldots$ Ankuftszeit des $(n+1)$-ten
Kunden.
\end{enumerate}
Falls $T_{n+1} < T_{n} + w_{n} + x_{n}$,
dann ist $w_{n+1} = T_{n+1} + w_{n} + x_{n} - T_{n+1} = w_{n} + x_{n} -
t_{n+1}$. Falls  $T_{n+1} \geq T_{n} + w_{n} + x_{n}$ ist $w_{n+1} = 0$.
Also
\begin{displaymath}
w_{n+1}= \max (w_{n}+x_{n}-t_{n+1}, 0) =: (w_{n} + x_{n} - t_{n+1})_{+} ~.
\end{displaymath}
Sei  $u_{n} = x_{n} - t_{n+1}.$ Die $u_{i}$ sind unabhängig und
identisch verteilt.
\begin{eqnarray*}
\Rightarrow w_{n} &=& \max (w_{n-1}+ u_{n-1}, 0) = 0 \\
\Rightarrow w_{n} &=& \max (0, u_{n-1} + \max (w_{n-2} + u_{n-2}, 0)) = \\
 &=& \max (0, u_{n-1}, u_{n-1} + u_{n-2} + w_{n-2}) = \dots\\
 &=& \max (0, u_{n-1}, u_{n-1} + u_{n-2}, \cdots ,  u_{n-1} + u_{n-2} +
\cdots + u_{1}) ~.
\end{eqnarray*}
Also ist die Verteilung von $w_{n}$ dieselbe wie die  von  $\tilde w_{n}$ mit
\begin{displaymath}
\tilde w_{n} = \max (0, u_{1}, u_{1} + u_{2}, \cdots, u_{n-1}+ u_{n-2} +
\cdots + u_{1}) ~.
\end{displaymath}
Offensichtlich ist $\tilde w_{n}$ eine monoton nichtfallende Folge, also
existiert
\[ \tilde w = \lim_{n \rightarrow \infty} w_{n}. \]
Falls $\E u > 0$, dann geht $u_{1}+ \cdots + u_{n-1}$ $\rightarrow
\infty$, also auch  $\tilde w$. Falls $\E u < 0$, dann geht $u_{1}+ \cdots
+ u_{n-1}$ $\rightarrow -\infty$, also ist für $n>n_{0}$ $u_{1}+ \cdots +
u_{n-1} <0 $, was bedeutet daß nur die ersten Glieder in der Definition
von  $\tilde w_{n}$ wichtig sind; also ist $\tilde w$ endlich. Falls $\E
u = 0$, ist können wir den einfachen Fall $D/D/1$ betrachten. In diesem
Fall ist $w_{n}=0$, also ist das Verhalten stationär. Leider ist das der
einzige Fall; sobald $A$ oder $B$ nicht degenerierte Verteilungen haben,
kann $\tilde w_{n}$ nicht gegen eine endliche Zufallsvariable
konvergieren, weil etwa nach dem zentralen Grenzwertsatz für $n$ groß
genug
\begin{displaymath}
\PP(\tilde w_{n} > a \sqrt{n.{\bf Var}(u)}) \geq 1- \Phi(a)- \epsilon > 0 ~.
\end{displaymath}
Somit ist für jedes $n$
\begin{displaymath}
\PP(\tilde w > a \sqrt{n.{\bf Var}(u)}) \geq 1- \Phi(a)- \epsilon ~,
\end{displaymath}
also
\begin{displaymath}
\PP(\tilde w = \infty)  \geq  1- \Phi(a)- \epsilon ~.
\end{displaymath}
Es bleibt uns also für stationäres Verhalten (außer im Trivialfall \\
$D/D/1$) die Bedingung
\begin{displaymath}
\E (u) < 0 \Leftrightarrow \E (x) < \E (t) \Leftrightarrow \rho=
\frac{\E (x)}{\E (t)} < 1 ~.
\end{displaymath}
Wir bezeichnen den Kehrwert von $\E (t)$ als die \index{Ankunftsrate}\enquote{Ankunftsrate} $\lambda =
\frac{1}{\E (t)}$ und $\mu = \frac{1}{\E (x)}$ als die \index{Bedienrate}\enquote{Bedienrate}. Es
sind dies die Anzahl von Kunden, die in einem langen Zeitraum
durchschnittlich pro Zeiteinheit ankommen bzw. bedient werden, falls
ununterbrochen
bedient wird. Mit diesen Bezeichnungen ist $\rho = \frac{\lambda}{\mu}$ \index{Auslastung}(Auslastung)
und die Bedingung für stationäres Verhalten wird zu $ \lambda < \mu$ bzw.\
$\rho<1$.
%--------------------------------------------------------------------------
\section{Der Satz von Little}
%---------------------------------------------------------------------------
Wir nehmen jetzt an, daß in unserer Schlange stationäres Verhalten
herrscht; wir wollen eine Beziehung zwischen der Ankuftsrate, der mittleren
Anzahl der Kunden im System und der mittleren Aufenthaltsdauer finden.
Dazu nehmen wir an, daß wir jeden Kunden für die Zeit, die er im System
verbringt, bezahlen müssen. Die Summe, die insgesamt zu bezahlen ist,
berechnet sich als $T \E (N)$, da zu jedem Zeitpunkt durchschnittlich $\E
(N)$
Kunden anwesend sind. Andererseits bekommt jeder Kunde durchschnittlich
$\E (z)$ bezahlt. In der Zeit $T$ kommen $\lambda T$ Kunden an, also ist
die
zu bezahlende Summe auch gleich $\lambda T \E (z)$.

Beide Gleichungen sind nicht vollständig exakt, weil in beiden Fällen
noch zufällige Schwankungen dazukommen, und weil bei der zweiten
Gleichung auch nicht berücksichtigt wurde, daß einige Kunden noch nach
$T$ bleiben. Diese Fehler sind aber von kleineren Ordnung als $T$. Wir
haben also
\begin{displaymath}
T \E (N) = \lambda T \E (z) + o(T) ~.
\end{displaymath}
Dividieren wir durch $T$ und $T \rightarrow \infty$ gibt
\begin{displaymath}
\E (N) = \lambda  \E (z) ~,
\end{displaymath}
d.h. Mittlere Anzahl = Ankuftsrate $*$ Mittlere Aufenthaltsdauer. Wendet
man dieses Ergebnis auf den Server allein an, ergibt sich, daß die
Mittlere Anzahl der Kunden, die gerade bedient werden =
\begin{displaymath}
\lambda  \E (x) = \frac{\lambda}{\mu} = \rho ~.
\end{displaymath}
Da aber höchstens 1 Kunde bedient wird, ist das gleich der
Wahrscheinlichkeit, daß der Server besetzt ist, oder der Auslastung des
Servers.
%---------------------------------------------------------------------------
\chapter{Warteschlangensysteme}
\section{Die Schlange $M/M/1$}
%---------------------------------------------------------------------------
Im Folgenden gehen wir von der \enquote{FCFS}-Disziplin aus.
Um die zukünftige Entwicklung einer Warteschlange bestimmen zu können,
benötigen wir 3 Angaben zur Zeit $t$.
\begin{enumerate}
\item Die Anzahl $N_{t}$ der anwesenden Kunden.
\item Die Zeit, die seit der letzten Ankunft vergangen ist.
\item Die Zeit, die seit dem Beginn des letzten Bedienvorgangs vergangen
ist (falls dieser noch andauert).
\end{enumerate}
Die letzten beiden Angaben sind notwendig, damit wir die Verteilung der
verbleibenden Zeit bis zur nächsten Ankunft bzw. bis zum Ende des
Bedienvorganges bestimmen können. Für den Fall $M/M/1$ sind diese
Angaben nicht notwendig, weil diese Verteilungen wegen der
Gedächtnislosigkeit der Exponentialverteilung nicht von der schon
verstrichenen Zeit abhängen. Deshalb genügt uns $N_{t}$ zur Beschreibung
des Systems.

Wir betrachten jetzt die Anzahl der Kunden zur Zeit $t+ \Delta t$, wenn
die Anzahl zur Zeit t bekannt ist. Die Anzahl kann sich in folgender Weise
ändern:
\begin{enumerate}
\item Es kann gar nichts geschehen.
\item Es kann genau ein Kunde aufkommen.
\item Es kann genau ein Kunde fertig werden.
\item Es kann mehr als ein Ereignis (Ankunft, gehen) auftreten.
\end{enumerate}
Die Wahrscheinlichkeit, daß mindestens ein Kunde im Intervall $(t, t+ \Delta t)$
ankommt, ist $1-e^{-\lambda \Delta t} = \lambda \Delta t + o (\Delta t)$.
Ebenso ist die Wahrscheinlichkeit, daß ein Kunde fertig wird $\mu \Delta
t + o(\Delta t)$. Die Wahrscheinlichkeit für 4. ist, wie man leicht
einsieht, $o(\Delta t)$. Das gibt für 1. die Wahrscheinlichkeit $1 -
(\lambda + \mu) \Delta t + o(\Delta t)$. Falls die Schlange leer ist,
fallen natürlich die Summanden mit $\mu$ weg (es kann ja niemand gehen).
Somit gilt für
\begin{eqnarray*}
p_{n}(t) &=& \PP (N_{t} = n) \\
p_{n}(t+ \Delta t) &=& \mu \Delta t . p_{n+1}(t) + (1 - (\lambda +
\mu) \Delta t) p_{n}(t) + \\
 & &+ \lambda \Delta t p_{n-1}(t) + o(\Delta t)
\qquad [n \geq 1] \\
p_{0}(t + \Delta t) &=& \mu \Delta t . p_{1}(t) + (1 - \lambda \Delta t)
p_{0}(t) + o(\Delta t) ~.
\end{eqnarray*}
Wenn man $p_{n}(t)$ auf die linke Seite bringt und durch $\Delta t$
dividiert und $\Delta t \rightarrow 0$ läßt, ergibt sich
\begin{eqnarray*}
p'_{n}(t) &=& \mu p_{n+1}(t)-(\lambda + \mu) p_{n}(t)+ \lambda p_{n-1}(t)
\\
p'_{0}(t) &=& \mu p_{1}(t)- \lambda p_{0}(t) ~.
\end{eqnarray*}
Diese Gleichungen lassen sich etwa mit Hilfe von Transformationen lösen,
aber das Ergebnis ist nicht besonders schön. Wir beschränken uns daher
jetzt und in der Folge auf die Bestimmung der stationären Lösung. Diese
ist natürlich dadurch gekennzeichnet, daß $p_{n}(t)$ nicht von der Zeit
$t$ abhängt, also $p'_{n}(t)=0$. Das ergibt die Gleichungen
\begin{eqnarray*}
\mu p_{n+1}-(\lambda +\mu) p_{n} + \lambda p_{n-1} &=& 0 \\
\mu p_{1} - \lambda p_{0} &=& 0 ~.
\end{eqnarray*}
Durch Induktion erhalten wir daraus
\begin{displaymath}
\mu p_{n+1} - \lambda p_{n} = 0 ~,
\end{displaymath}
oder
\begin{displaymath}
p_{n+1} = \frac{\lambda}{\mu} p_{n} = \rho p_{n} ~.
\end{displaymath}
Also ist
\begin{displaymath}
p_{n} = \rho^{n}p_{0}
\end{displaymath}
und wegen $\sum_{n=0}^{\infty} p_{n} = 1$
\begin{displaymath}
p_{0} = 1- \rho
\end{displaymath}
und
\begin{displaymath}
p_{n} = \rho^{n} (1- \rho) ~.
\end{displaymath}
Die Anzahl der Kunden im System ist also geometrisch verteilt. Aus dieser
Verteilung können wir jetzt die Verteilungen von $w$ und $z$ bestimmen.
Die Zeit im System $z$, falls bei der Ankunft $n$ Personen anwesend sind,
ist die Summe von $(n+1)$ exponentialverteilten Zufallsvariablen (die
Bedienzeiten der $n$ anwesenden + die der neu hinzugekommenen), hat also
die Dichte
\begin{displaymath}
f_{z}(u|N_{t}=n) = \frac{u^{n}}{n!} \mu^{n+1} e^{- \mu u} \qquad [u>0] ~.
\end{displaymath}
Die unbedingte Dichte ergibt sich also zu
\begin{eqnarray*}
f_{z}(u) &=& \sum_{n}^{} \PP(N_{t}=n).f_{z}(u|N_{t}=n) = \\
 &=& \sum_{n}^{} (1- \rho) \rho^{n}. \frac{u^{n}}{n!} \mu^{n+1} e^{- \mu
u} = \\
 &=& (1- \rho) e^{- \mu(1- \rho)u} \qquad [u>0] ~.
\end{eqnarray*}
$z$ ist also exponentialverteilt mit Parameter
\begin{displaymath}
\mu (1- \rho) = \mu - \lambda ~.
\end{displaymath}
Die Verteilung von $w$ ist gemischt: $\PP (w=0) = 1- \rho$, und die
bedingte Verteilung von $w$ unter der Bedingung $[w>0]$ ist wieder eine
Exponentialverteilung mit Parameter $\mu - \lambda$.
%----------------------------------------------------------------------------
\section{Das System $M/G/1$}
%------------------------------------------------------------------------------
Jetzt benötigen wir zusätzlich zu $N_{t}$ die Information über die
schon verbrauchte Bedienzeit. Die einfachste Methode besteht darin, das
System nur in solchen Zeitpunkten zu betrachten, an denen die verbrauchte
Bedienzeit bekannt ist (und zwar = 0), nämlich die Zeitpunkte $T_{n}$, in
denen der n-te Kunde das System verläßt. Es sei $N_{n}$ die Anzahl der
Kunden, die dann im System verbleiben. Es gilt: Falls $N_{n}=0$, so muß
zuerst gewartet werden, bis ein neuer Kunde ankommt; wenn dieser Kunde
geht, sind noch genau die Kunden da, die während seiner Bedienzeit
angekommen sind; bezeichnet man $M_{n}$ als die Anzahl der Kunden, die
während der Bedienzeit des $n$-ten Kunden ankommen, so gilt
\begin{displaymath}
N_{n+1} = M_{n} ~.
\end{displaymath}
Falls $N_{n} \not= 0$ ist
\begin{displaymath}
N_{n+1} = N_{n} - 1 + M_{n} ~.
\end{displaymath}
Zusammengefaßt ergibt sich:
\begin{displaymath}
N_{n+1} = (N_{n} - 1)_{+} + M_{n} ~.
\end{displaymath}
Wir suchen eine stationäre Lösung; es sei also $\PP (N_{n}=k)=p_{k}$
unabhängig von $n$. Die erzeugende Funktion von $N_{n}$ ist
\begin{displaymath}
P^{*}(z) = \sum_{}^{}p_{k}z^{k} ~.
\end{displaymath}
Die erzeugende Funktion von $(N_{n}-1)_{+}=$
\begin{eqnarray*}
= p_{0} + \sum_{k=1}^{\infty} p_{k} z^{k-1} &=& p_{0}+ \frac{\hat P
(z) - p_{0}}{z} = \\
 &=& \frac{\hat P(z) - p_{0}(1-z)}{z} ~.
\end{eqnarray*}
Mithilfe der Transformationen (Anhang A) ergibt sich die erzeugende Funktion von $M_{n}$
(die Ankünfte bilden ja einen Poisson - Prozeß) als
\begin{displaymath}
\tilde B (\lambda(1 - z)) ~,
\end{displaymath}
wobei $B$ die Verteilung der Bedienzeit (mit Dichte $\beta$) ist. Wir
erhalten also
\begin{displaymath}
P^{*}(z) = \frac{(P^{*}(z) - p_{0}(1-z))}{z}  \tilde B (\lambda(1-z)) ~,
\end{displaymath}
also
\begin{displaymath}
P^{*}(z) = \frac{p_{0}(1-z) \tilde B ( \lambda (1-z))}{ \tilde B (
\lambda(1-z)) - z} ~.
\end{displaymath}
Hier ist noch $p_{0}$ zu bestimmen, und zwar aus der Bedingung $P^{*}(1) =
1$. Es ergibt sich $p_{0} = 1 - \rho$ und
\begin{displaymath}
P^{*}(z) = \frac{(1- \rho)(1-z) \tilde B ( \lambda (1-z))}{ \tilde B (
\lambda(1-z)) - z} ~,
\end{displaymath}
eine sogenannte \index{Pollaczek - Khinchin Formel}Pollaczek - Khinchin Formel. Die Anzahl der Kunden, die der $n$-te
Kunde zurückläßt, ist genau die Anzahl der Kunden, die ankommen
während er im System ist (d.h. während $z_{n}$), d.h. für die
$L$-Transformierte $ \tilde Z (t)$ der Verteilung von $z$ gilt:
\begin{displaymath}
\tilde Z (\lambda(1-z)) = P^{*}(z) ~,
\end{displaymath}
also
\begin{displaymath}
\tilde Z (t) = \frac{(1- \rho)t \tilde B (t)}{t + \lambda \tilde B (t) -
\lambda} ~.
\end{displaymath}
Auch das nennt man eine Pollaczek - Khinchin Formel. Für die Wartezeit
gilt
(wegen $z_{n} = w_{n} + x_{n}$)
\begin{displaymath}
\tilde Z (t) = \tilde W (t) \tilde B(t) ~,
\end{displaymath}
also
\begin{displaymath}
\tilde W (t) = \frac{(1- \rho)t}{t + \lambda \tilde B (t) - \lambda} ~.
\end{displaymath}
Für die Erwartungswerte ergibt sich:
\begin{eqnarray*}
\E (N) &=& \rho + \frac{\lambda^{2} \E x^{2}}{2(1- \rho)} \\
\E (Z) &=& \frac{1}{\mu} + \frac{\lambda \E x^{2}}{2(1 - \rho)} \\
\E (W) &=& \frac{\lambda \E x^{2}}{2(1 - \rho)} ~.
\end{eqnarray*}
%------------------------------------------------------------------------------
\section{Das System $G/M/1$}
%------------------------------------------------------------------------------
Jetzt betrachten wir analog zum vorigen Kapitel das System zu den Zeiten
$T_{n}$, wo der $n$-te Kunde ankommt. $N_{n}$ sei die Anzahl der
anwesenden Kunden, die der $n$-te Kunde vorfindet.
\begin{displaymath}
N_{n+1} = N_{n}+1-\mbox{Anzahl der Kunden, die während $t_{n+1}$ gehen.}
\end{displaymath}
Für $n>0$ gilt, wenn wir $p_{k}= \PP (N_{n}=k)$ (stationär!) setzen:
\begin{displaymath}
p_{k} = \sum_{j=k-1}^{\infty} p_{j} q_{j+1-k} \qquad [k \geq 1] ~,
\end{displaymath}
wobei
\begin{displaymath}
q_{s} = \PP (\mbox{ $s$ Kunden gehen während
$t_{n+1}$)} =
\end{displaymath}
\begin{eqnarray*}
= \PP (\mbox{während $t_{n+1}$ treten genau $s$ Ereignisse eines Poissons
-} \\
\mbox{Prozesses mit Rate $\mu$ auf)} ~. & &
\end{eqnarray*}
Die Gleichung für $k=0$ ist überflüssig, da sie aus den Gleichungen
für $k>0$ und der Beziehung $\sum_{}^{} p_{k}=1$ gefolgert werden kann.
Man kann zeigen, daß diese Gleichung eine eindeutige Lösung besitzt.
Falls nun $(p_{k})$ eine Lösung ist, ist auch
\begin{displaymath}
\tilde p_{k} = \frac{p_{k+1}}{1-p_{0}}
\end{displaymath}
eine Lösung. Es muß also
\begin{displaymath}
\tilde p_{k} = p_{k} ~,
\end{displaymath}
somit
\begin{displaymath}
p_{k+1} = p_{k}(1-p_{0})
\end{displaymath}
und
\begin{displaymath}
p_{k} = p_{0}(1-p_{0})^{k} =
\sigma^{k}(1- \sigma) \qquad [ \sigma := 1 - p_{0}] ~.
\end{displaymath}
Setzt man das in die Gleichung für $k=1$ ein, ergibt sich
\begin{displaymath}
\sigma = \sum_{j=0}^{\infty} \sigma^{j} q_{j} = \tilde A (\mu(1-\sigma))
~.
\end{displaymath}
Falls $\rho < 1$, gibt es genau eine Lösung $\sigma \in (0,1)$. Dann ist
$N$ geometrisch verteilt mit Parameter $\sigma$. Wie für die Schlange
$M/M/1$ ergibt sich die Verteilung der Zeit $z$ im System als
Exponentialverteilt mit Parameter $\mu(1- \sigma)$; die Wartezeit $w$ hat
$\PP (w=0)= 1 - \sigma$ und die bedingte Verteilung von $w$ unter $[w>0]$
ist wieder dieselbe Exponentialverteilung wie die von $z$.
%---------------------------------------------------------------------------
\section{Das System $G/G/1$}
%---------------------------------------------------------------------------
Hier sind beide Verteilungen - die der Zwischenankunftszeiten und die der
Bedienzeiten - allgemeine Verteilungen. Der Trick der vorigen beiden
Kapitel funktioniert jetzt nicht mehr gut. Um beide Zeiten zu
kontrollieren, müßten wir das System nun zu den Zeitpunkten betrachten,
in denen ein Kunde das leere System betritt; diese Zeitpunkte sind aber zu
selten, um vernüftig damit zu arbeiten. Statt dessen gehen wir von der
Rekursion für die Wartezeiten aus:
\begin{displaymath}
w_{n+1} = (w_{n} + u_{n})_{+} ~.
\end{displaymath}
Das bedeutet für die Verteilungsfunktion $W(.)$ von $w$
\begin{displaymath}
W(x) = \PP (w_{n+1} \leq x) = \left\{
\begin{array}{lc}
\PP (w_{n} + u_{n} \leq x) & x \geq 0 \\
0 & x < 0
\end{array} \right. ~.
\end{displaymath}
Die Wahrscheinlichkeit $\PP (w_{n}+ u_{n} \leq x)$ berechnet sich als
\begin{displaymath}
\PP (w_{n} + u_{n} \leq x) = \int_{- \infty}^{\infty} W(x-u) c(u) du ~,
\end{displaymath}
wobei $c(u)$ die Dichte von $u_{n} = x_{n} - t_{n+1}$ ist. Falls in der
Gleichung für $W(x)$ die Fallunterscheidung nicht auftreten würde, wäre
sie leicht durch Transformationen zu lösen. Wir erreichen dies durch
einen Kunstgriff: Wir setzen
\begin{displaymath}
Y(x) = \left\{
\begin{array}{lc}
\int_{- \infty}^{\infty} W(x-u)c(u) du &  x< 0 \\
0 &  x \geq 0
\end{array} \right. ~.
\end{displaymath}
Dann ist
\begin{displaymath}
W(x) + Y(x) = \int_{-\infty}^{\infty} W(x-u) c(u) du ~.
\end{displaymath}
Wir bezeichnen jetzt die Laplace - Transformierte von $W$ mit $\Phi (t)$,
und die von $Y$ mit $\Phi^{-}(t)$. Durch partielle Integration zeigt man,
daß
\begin{displaymath}
\Phi (t) = \frac{1}{t} \tilde W(t)
\end{displaymath}
gilt. Für die Transformationen ergeben sich die Formeln
\begin{displaymath}
\Phi (t) + \Phi^{-}(t) = \Phi (t) \tilde C (t) = \Phi (t) \tilde A (-t)
\tilde B (t) ~,
\end{displaymath}
oder
\begin{displaymath}
\frac{\Phi^{-}(t)}{\Phi (t)} = \tilde A (-t)  \tilde B (t) -1 ~.
\end{displaymath}
Wir nehmen an, daß $\tilde A(t)$ für $t \geq -D$ existiert. (Das ist
gleichbedeutend damit, daß $\PP (t_{n} \geq x)$ wie $e^{-Dx}$ fällt).
Dann existiert $\tilde A (-t) \tilde B (t) - 1$ für $0 \leq t \leq D$;
Ferner existiert $\Phi (t)$ für $t >0$ und $t \Phi (t)$ ist in $\Re (t)
\geq 0$ regulär und beschränkt; $\Phi^{-}(t)$ existiert für $t \leq D$
und in $\Re (t) < D$ ist $t\Phi^{-}(t)$ regulär und beschränkt. Wir
versuchen 2 Funktionen $\Psi^{+}$ und $\Psi^{-}$ zu finden, die folgendes
erfüllen:
\begin{enumerate}
\item $\frac{\Psi^{+}(t)}{\Psi^{-}(t)} = \tilde A(-t) \tilde B(t) -1$ ~ ~\index{Spektralzerlegung}(Spektralzerlegung).
\item $\frac{\Psi^{+}(t)}{t}$ ist für $\Re(t)>0$ regulär und beschränkt
und hat dort keine Nullstellen.
\item $\frac{\Psi^{-}(t)}{t}$ ist für $\Re (t) < D$ regulär und
beschränkt und hat dort keine Nullstellen.
\end{enumerate}
Dann gilt
\begin{displaymath}
\frac{\Phi^{-}(t)}{\Phi (t)} = \frac{\Psi^{+}(t)}{\Psi^{-}(t)} \qquad
0< \Re (t) < D ~,
\end{displaymath}
oder
\begin{displaymath}
\Phi^{-}(t) \Psi^{-}(t) = \Psi^{+}(t) \Phi (t) \qquad 0< \Re (t) < D ~.
\end{displaymath}
Die linke Seite ist für $\Re (t) < D$ regulär und beschränkt, die
rechte Seite für $\Re (t) > 0$. Es ist dadurch also eine Funktion
bestimmt, die in der ganzen Ebene regulär und beschränkt ist. Nach dem
Satz von \index{Satz!LIOUVILLE}LIOUVILLE muß eine solche Funktion konstant sein. Es gilt also
\begin{displaymath}
\Phi (t) = \frac{K}{\Psi^{+}(t)} ~,
\end{displaymath}
und
\begin{displaymath}
\tilde W (t) =  \frac{Kt}{\Psi^{+}(t)} ~.
\end{displaymath}
Es bleibt die Konstante $K$ zu bestimmen. Sie folgt wieder aus
\begin{displaymath}
\tilde W (0) = 1 \qquad \mbox{zu} \qquad
K = \frac{\Phi^{+}(t)}{t} \Bigg \bracevert_{t=0} = (\Phi^{+})^{'}(0) ~.
\end{displaymath}
{\bf Beispiel: $M/M/1$}
\begin{displaymath}
A = M_{\lambda}: \quad \tilde A(t) = \frac{\lambda}{\lambda + t}, \quad
B = M_{\mu}: \quad \tilde B(t) =\frac{\mu}{\mu +t}
\end{displaymath}
\begin{eqnarray*}
\frac{\Psi^{+}(t)}{\Psi^{-}(t)} &=& \tilde A(-t) \tilde B(t)-1 =
\frac{\lambda \mu}{(\lambda - t)(\mu + t)} - 1 = \\
 &=& \frac{t(\mu - \lambda + t)}{(\lambda - t)(\mu + t)}. \\
\Psi^{+}(t) &=& \frac{t(\mu -\lambda + t)}{(t + \mu} \\
\Psi^{-}(t) &=& (\lambda - t) \\
\Phi (z) &=& \frac{\Psi^{+'}(0)}{\Psi^{+}(z)} =
\frac{(\mu - \lambda)(\mu +t)}{\mu t(\mu - \lambda + t)} =
\frac{1}{t} - \frac{\lambda}{\mu(\mu - \lambda + t)} \\
\Psi^{+'}(0) &=& \frac{\Psi^{+}(t)}{t} \Bigg \bracevert_{t=0} =\frac{\mu -
\lambda}{\mu} \\
F(x) &=& 1 - \rho e^{-(\mu - \lambda)x} \quad \mbox{für} \quad x \geq 0
\end{eqnarray*}
also die Verteilung der Wartezeit aus dem ersten Kapitel.