Stochastische Bediensysteme

Stochastische Modelle:
- Zeiten (Ankunft, Bedienung) häufig stochastisch
- typische Verteilungen für Zeitabstand beim Ankunftsprozess
  - Exponential, Erlang, empirisch
- typische Verteilungen für Bedienzeiten
  - Exponential, Weibull, Normal, empirisch
Einfaches stochastisches Modell:
- Ankunftszeiten und Bedienzeiten jeweils 1s oder 2s mit gleicher Wahrscheinlichkeit
- Modell singleserver2A
  - Generator/Entity generation/Time source: Matlab action
  - Intergeneration time action: dt = randi(2);
  - Server/Main/Service time source: Matlab action
  - Service time action: dt = randi(2);
- Ergebnis
- Analyse
  - wirkt auf den ersten Blick ok: Zeiten zwischen Events wechseln zufällig
  - seltsam: Server load = 1 konstant, bei Zufall müsste Server auch mal warten
  - genauer hinsehen: Zeitintervalle bei Generator Out und Server Out gleich!
- Ausgabe der Zufallszeiten mit fprintf (landet im Warnungs-Fenster)
  - Ergebnis: Werte in Generator und Server sind identisch
  - Ursache: Event actions werden nach C übersetzt, bekommen jeweils eigenen rand-Aufruf
- Abhilfe: jeweils mit verschiedenen Seeds initialisieren
  - ```
  seed = 12;
  persistent isSeedSet;
  if isempty(isSeedSet)
    rng(seed);
    isSeedSet = true;
  end
  dt = randi(2);
```
- Ergebnis für längere Zeit
Standardmodell M|M|1 (singleserver3A):
- Zeit zwischen zwei ankommenden Entitäten ~ Ex(λ)
- Bedienzeit ~ Ex(μ)
- zur Erinnerung
  - Ankunftsprozess hat die Markov-Eigenschaft
  - ⇔ Zeitintervalle zwischen zwei Ankünften sind exponentiell verteilt
- Modell in SimEvents analog singleserver2B
  - Berechnung der Intergeneration time
  - dt = -(1/lambda)*log(rand());
  - Berechnung der Service time
  - dt = -(1/mu)*log(rand());
- Ergebnisse für λ = 1, μ = 1.2
Ergebnisse der Warteschlangentheorie:
- M|M|1 mit λ ≥ μ haben keine Gleichgewichtsverteilung
- M|M|1 mit λ < μ haben eine Gleichgewichtsverteilung, es gilt
- M|G|1 mit i.i.d-verteilten Servicezeiten mit Erwartungswert 1/μ (mit μ > λ) und Varianz σ²
  - Beweis in [L3]

Auswertung der Simulationsergebnisse (singleserver3B):

theoretische Ergebnisse bei λ = 1, μ = 1.2
- L_Q = 4.1667
- W_Q = 4.1667
- A = 0.8333
am einfachsten Endergebnisse im Modell direkt anzeigen
Ergebniswerte sind viel zu klein!

bessere Ergebnisse durch längere Laufzeit

T	L_Q	W_Q	A
100	1.426	1.561	0.7164
1000	3.879	3.948	0.8286
10000	4.921	4.941	0.8471
1e5	4.207	4.228	0.8312
1e6	4.291	4.289	0.8359
1e7	4.185	4.186	0.8333

zur Beschleunigung: kein Osci und Decimation=1e5 bei Displays

Analyse
- Konvergenz sehr langsam
- Ursache: große Schwankungen, z. B. für T = 10000
- Queuelänge wächst bis 33, ist aber auch immer wieder 0

Queue mit beschränkter Kapazität:
- wie viel Platz braucht man für die Warteschlange?
- konkret
  - Bei gegebener Kapazität K der Warteschlange treten Blockaden auf
  - Wie groß muss K sein, damit die Zahl B der Blockaden/Zeitintervall kleiner ist als 1e-3?
- Untersuchung im M|M|1|c-Modell queuecapacity1A mit K = 15
  - bei Blockade bleibt neue Entity im Generator (pending)
  - Erzeugungsprozess wird gestoppt, bis Generator wieder frei
- Trick zum Zählen der Blockaden
  - Hit Crossing-Block erzeugt Message (einfache Entität)
  - Terminate-Block zählt und vernichtet sie
- Ergebnis
  - Blockaden treten gehäuft auf (nämlich bei voller Queue)
Verbessertes Modell queuecapacity1B:
- Problem: Ankunftsprozess wird verändert
- Alternative: geblockte Entities umleiten
  - Verhalten im Detail anders, da Generator ungestört durch Blocking
- Bestimmung von K
  - K setzen und für große Zeit (T = 10⁵) simulieren
  - B ablesen
  - K ändern und iterieren
- halb-automatisiert mit Matlabskript computeQueueCapacity
  - Ergebnis ist zufällig, Variable ist ganzzahlig
  - quick and dirty mit fzero, Abbrechen nach einigen Ausgaben →
  - ```
  computeQueueCapacity(1)
  run: K =  15,  B = 0.008090
  run: K =  35,  B = 0.000180
  run: K =  33,  B = 0.000240
  run: K =  24,  B = 0.001490
  run: K =  27,  B = 0.001010
  run: K =  28,  B = 0.000790
  run: K =  27,  B = 0.001010
```
- prüfen mit langer Simulation
- ```
computeQueueCapacity(2, 26)
run: K =  26,  B = 0.001194
run: K =  27,  B = 0.000986
run: K =  28,  B = 0.000839
```
- Ergebnis: 27 Plätze in der Queue sollten genügen - bei L_Q = 4.1667!
Aufgaben:
- Aufgabe 11
- Aufgabe 12