Warteschlangentheorie

Grundbegriffe Statistik

Zufallsgröße

$\underbar{x}$

Wahrscheinlichkeit

$Pr\left[\underbar{x}\le x\right]$ das $\underbar{x}$ kleiner oder gleich $x$

Verteilungsfunktion

$F\left(x\right)=Pr\left[\underbar{x}\le x\right]$

• $F\left(a\right)-F\left(b\right)=Pr\left[a<\underbar{x}\le b\right]$
• $F\left(-\infty\right)=0$
• $F\left(\infty\right)=1$

Stetige Verteilung

falls der Wertebereich von $\underbar{x}$ überabzählbar unendlich ist, z.B. Reell.

Wahrscheinlichkeitsdichte

$f\left(x\right)$

• ist nur für stetige Verteilung definiert
• $f\left(x\right)dx=Pr\left[x<\underbar{x}\le x+dx\right]$
• $F\left(x\right)=\int_{-\infty}^{x}f\left(s\right)ds$

Moment

das $n$-te Moment einer Verteilunsfunktion $E\left[\underbar{x}^{n}\right]=\int_{-\infty}^{\infty}s^{n}dF\left(s\right)$

Erwartungswert

$E\left[x\right]==\int_{-\infty}^{\infty}sdF\left(s\right)$

• Entspricht erstem Moment
• auch Mittelwert genannt

Varianz

$$\sigma^{2}=E\left[\left(\underbar{x}-E\left[\underbar{x}\right]\r... ...{-\infty}^{\infty}\left(s-E\left[\underbar{x}\right]\right)^{2}dF\left(s\right)$$

• Auch Streuungsquadrat
• $E\left[\left(\underbar{x}-a\right)^{2}\right]=\sigma^{2}\left(\underbar{x}\right)+\left(E\left[\underbar{x}\right]-a\right)^{2}$

Bedingte Wahrscheinlichkeit

$Pr\left[A\vert B\right]=\frac{Pr\left[A\wedge B\right]}{Pr\left[B\right]}$

• Wahrscheinlichkeit das $A$ eintritt wenn mann bereits weiss, das $B$ eintritt
• $Pr\left[A\wedge B\right]$ Wahrscheinlichkeit das $A$ und $B$ zusammen eintreten

Unabhängigkeit

zweier Ereignisse $A$ und $B$, wenn $Pr\left[A\vert B\right]=Pr\left[A\right]$

negativ exponentielle Verteilung

$F\left(x\right)=\begin{cases} 1-e^{-\mu x} & x\ge0\\ 0 & x<0\end{cases}$

• Wahrscheinlichkeitsdichte $f\left(x\right)=\begin{cases} \mu e^{-\mu x} & x\ge0\\ 0 & x<0\end{cases}$
• Varianz $\sigma^{2}\left(\underbar{x}\right)=\mu^{-2}$
• Dies ist die einzige Verteilungsfunktion die Gedächnislos ist. D.h. es gilt
  $$Pr\left[\underbar{x}\le a+x\vert\underbar{x}>a\right]=Pr\left[\underbar{x}\le x\right]$$

• Wenn im Mittel zwischen zwei Aufträgen $t$ Zeiteinheiten vergehen, dann muss man im Mittel trotzdem noch $t$ Zeiteinheiten warten, unabhängig davon, wieviel Zeit schon vergangen ist.

Warteschlange Allgemein

Anschauung

siehe Abbildung cap:WarteschlangeAnschaulich

Figure: Warteschlangenmodell - Anschaulich

Beschreibung

siehe Abbildung cap:WarteschlangeAbstrakt

Figure: Warteschlangenmodell - Abstrakt

Charakterisierung

$A/B/c/N/K$

Kundenpopulation

$K$

Ankunftszwischenzeitverteilung

$A$

Warteschlangenlänge

$N$

Bedienstationenanzahl

$c$

Bedienzeitverteilung

$B$

Abkürzungen

(typische)

• $M$ (negativ) exponentialverteilt
• $D$ deterministisch oder konstant verteilt
• $G$ beliebig verteilt
• z.B. $M/M/1=M/M/1/\infty/\infty$
  $M/G/1=M/G/1/\infty/\infty$

Ankunftsrate

(mittlere) $\lambda=E\left[A\right]$

Bedienrate

(mittlere) pro Station $\mu=E\left[B\right]$

Streuung Bedienrate

$\sigma^{2}=\textrm{Var}\left(B\right)$

Kunden im System

$L\left(t\right)$ zum Zeitpunkt $t$

Langzeitverhalten

$L\left(t\right)\rightarrow L\left(\infty\right)$ stationäre Verteilung

• Ziel der Warteschlangentheorie ist es diese Größe zu bestimmen
• $L$ Erwartungswert von $L\left(\infty\right)$
• $p$ Langzeitausnutzung der Server
• $w$ Langzeitaufenthaltzeit im System
• Gesetz von Little
  $L=\lambda\cdot w$

M/M/1

Bedingung

für die Stationarität $E\left[A\right]=\lambda<\mu=E\left[B\right]$

Langzeitausnutzung

des Servers $\rho=\frac{\lambda}{\mu}$

Kunden im System

$L=\frac{\rho}{1-\rho}$

Langzeitaufenthaltszeit

$w=\frac{1}{\mu-\lambda}$

Dichtefunktion

von $L\left(\infty\right)$

$$d_{L\left(\infty\right)}\left(\xi\right)=P\left(L\left(\infty\right)=\xi\right)=\left(1-\rho\right)\cdot\rho^{\xi}$$

• dies ist die geometrische Verteilung

Eigenschaften

 

• Warteschlangen werden länger, wenn bei konstanten Erwartungswert die Streuung der Bedienzeiten wächst
• Jede Pufferlänge tritt mit gewisser Wahrscheinlichkeit einmal auf, d.h. Puffer laufen stets gelegentlich voll
• $n$ Server mit einer gemeinsamen Warteschlange sind besser als $n$ Server mit $n$ Warteschlangen

M/G/1

• $\rho=\frac{\lambda}{\mu}$
• $L=\rho+\frac{\rho^{2}\left(1+\frac{\sigma^{2}}{\mu^{2}}\right)}{2\left(1-\rho\right)}$
• $w=\frac{1}{\mu}+\frac{\lambda\left(1+\frac{\sigma^{2}}{\mu^{2}}\right)}{2\mu^{2}\left(1-\rho\right)}$

M/D/1:$\sigma=0$

• $\rho=\frac{\lambda}{\mu}$
• $L=\rho+\frac{\rho^{2}}{2\left(1-\rho\right)}$
• $w=\frac{1}{\mu}+\frac{\rho}{2\mu\left(1-\rho\right)}$

M/M/c

• $\rho=\frac{\lambda}{c\mu}$
• $L=c\rho+\frac{\rho}{1-\rho}Pr\left[L\left(\infty\right)\ge c\right]$
• $w=\frac{L}{\lambda}$
• $P_{0}=\left(\frac{\left(c\rho\right)^{c}}{\left(1-\rho\right)\cdot c!}+\sum_{i=0}^{c-1}\frac{\left(c\rho\right)^{i}}{i!}\right)^{-1}$
• $Pr\left[L\left(\infty\right)\ge c\right]=\frac{\left(c\rho\right)^{c}}{\left(1-\rho\right)\cdot c!}P_{0}$