Simulation diskreter Systeme

Standardbeispiele:

Kunden stellen sich an Kassenschlangen an
Zwischenprodukte werden vor einer Fertigungsmaschine zwischengelagert, bis sie weiterverarbeitet werden
Aufträge warten im Eingangskorb auf Bearbeitung
Datenpakete werden bis zur Weiterleitung im Router zwischengespeichert
abstrakt
- Entitäten (Entities) warten in Warteschlangen (Queues), bis sie von Bedienstationen (Server) verarbeitet werden

Bestandteile:

Bedienstation (Server)
- bearbeitet eine Entität
- auch mehrere parallel möglich (N-Server)
- Bearbeitungszeit fest oder stochastisch
Warteschlange (Queue)
- Wartebereich für Entitäten
- unbeschränkt oder feste Kapazität
- verschiedene Queuedisziplinen (FIFO, LIFO, Prio)
Ankunftsprozess (Generator)
- erzeugt ankommende Entitäten
- Zeitabstände fest oder stochastisch

Kendall-Notation:

übliches Klassifizierungs-Schema von Bediensystemen
enthält sechs Parameter A|B|s|c|n|Q

Bedeutung

Parameter	Bedeutung	wichtige Werte
A	Art des Ankunftsprozesses	D (deterministisch) M (Markov), G (allgemein)
B	Art des Bedienprozesses	D (deterministisch) M (Markov), G (allgemein)
s	Zahl der Bediener	1, 2, .., ∞
c	Größe des Warteraums	1, 2, .., ∞
n	max. Anzahl von Kunden	1, 2, .., ∞
Q	Queue-Politik	FIFO, LIFO, Prio, Random

häufig c = ∞, n = ∞, Q = FIFO
- werden in Notation weggelassen
- wichtigstes Beispiel: M|M|1

Basismodell singleserver1A:

einfaches Bediensystem mit festen Zeiten (D|D|1)
Parameter
- Ankunftsprozess (Generator) mit festem Zeitabstand t_G = 1
- unbeschränkte FIFO-Queue
- Server mit Bedienzeit t_S = 1.5
Modellierung mit SimEvents
- Zusatzpaket zu Matlab/Simulink für DES (Discrete event simulation)
- Leitungen transportieren Entitäten, keine Zahlen
Grundaufbau
Oscis zeigen durchlaufende Entitäten an

Anzeige statistischer Daten:

Übersicht über Entities auch durch Anzeige von Anzahlen
SimEvent-Blöcke enthalten Parameter-Seite Statistics
darunter diverse Anzahlen, z. B.
- d = Zahl der Entitäten, die einen Block verlassen haben
- n = Zahl der Entitäten innerhalb eines Blocks
- a = Zahl der Entitäten, die einen Block betreten haben
zur bequemen Anzeige in Viewer Umwandlung der Signale von event-driven in time-driven nötig
- Trick: automatisch durch Gain-Block mit Faktor 1
- zur Verschönerung: Gain-Block in Subsystem versteckt
Modell singleserver1B
Ergebnisse

Manuelles Bestimmen des Verhaltens:

Liste aller Ereignisse (Events) mit Zeiten erstellen
- für kurze Zeiten bzw. wenige Entities
- möglichst übersichtlich aufschreiben
- wichtig zur Fehlersuche in Modellen!
Vorgehensweise z. B.
- Tabelle mit Zeit und Belegung der Komponenten
- zunächst alle vorher schon bekannten Events aufschreiben
- dann oben anfangen und jeweils neue zukünftige Events einfügen
- Entitäten durchnummerieren E1, E2, ...

fertige Liste für singleserver1B (bis t = 10)

  t    Gen  Que        Srv  raus   Bemerkungen
 --------------------------------------------
  0.0       -          -           Startzeit
  1.0  E1   ->         E1          E1 läuft bis zum Server,
                                   fertig bei t=2.5 (eintragen!)
  2.0  E2   E2         E1
  2.5       -          E2   E1     fertig bei t=4
  3.0  E3   E3         E2
  4.0       E3         -    E2     *
  4.0       -          E3          *, fertig bei t=5.5
  4.0  E4   E4         E3          *
  5.0  E5   E5/E4      E3          Reihenfolge in Queue beachten!
  5.5       E5         E4   E3     fertig bei t=7
  6.0  E6   E6/E5      E4
  7.0       E6         E5   E4     fertig bei t=8.5
  7.0  E7   E7/E6      E5
  8.0  E8   E8/E7/E6   E5
  8.5       E8/E7      E6   E5     fertig bei t=10
  9.0  E9   E9/E8/E7   E6
 10.0       E9/E8      E7   E6     fertig bei t=11.5
 10.0  E10  E10/E9/E8  E7

Anmerkung *
- Reihenfolge (E2 verlässt Srv/E3 rückt nach/E4 verlässt Gen) unklar
- Wahl: erst raus aus Server, dann Nachrücken, dann Erzeugung
- andere Wahlen führen (hier!) zu gleichen Ergebnissen
Vergleich mit Ergebnissen von singleserver1B
- passt zu Generator out, Queue out, Terminator in
- passt auch zu in Queue und in Server

Kennzahlen eines Bediensystems:

für Generator
- mittlere Ankunftsrate λ
für Queue
- mittlere Länge der Warteschlange L_Q
für Server
- mittlere Bedienrate μ
- Auslastung A := Aktivzeit/Gesamtzeit
für Gesamtsystem
- mittlere Zahl von Entitäten im System L
für Entities
- mittlere Wartezeit in Queue W_Q
- mittlere Verweilzeit (Wartezeit + Bedienzeit) W
Satz von Little (im Gleichgewicht)
- L = λ W
- L_Q = λ W_Q

Manuelles Bestimmen der Kennzahlen:

mittlere Queuelänge L_Q aus momentaner Queuelänge q(t) durch

manuell durch Tabelle

Queuelänge q	Dauer Δt	q*Δt
0	2.5	0.0
1	3.0	3.0
2	3.0	6.0
3	1.5	4.5
gesamt		13.5

also L_Q = 1.35

Server-Auslastung A analog aus momentaner Serverbelegung s(t) durch
- hier einfach, Ergebnis A = 0.9

mittlere Wartezeit W_Q ist der Mittelwert der Wartezeiten t_i der Entitäten E_i, also (bis zu T = 10)

Entität i	1	2	3	4	5	6	7	8	9
Wartezeit t_i	0.0	0.5	1.0	1.5	2.0	2.5	3.0	2.0	1.0

zählt man nur Entitäten nach Verlassen der Queue → W_Q = 1.5
zählt man alle Entitäten → W_Q = 1.5 (zufällig identisch!)

Check: Satz von Little
- λ = 1 → W_Q = L_Q/λ = 1.35
- passt nicht, wir haben ja auch kein Gleichgewicht
- schlimmer noch: es gibt hier keins!

Kennzahlen aus Simulation (singleserver1C):

Daten direkt aus Statistics der Blöcke
Queue
- n = Queuelänge
- l = mittlere Queuelänge
- w = mittlere Wartezeit in der Queue
Server
- n = Zahl der bedienten Entitäten = Aktivität
- util = Auslastung
Ergebnisse
passt mit manueller Auswertung zusammen
Plot der mittleren Wartezeit → nur fertige Entitäten werden gezählt

Grundlagen