Ereignisdiskrete Simulation

• Prinzip der ereignisdiskreten Simulation (DES = Discrete Event Simulation):
  • Events haben Typ und Zeitpunkt
  • alle Events stehen zeitlich geordnet in einer Liste
    • Zeitsteuerung springt jeweils zum nächsten Zeitpunkt in der Eventliste
  • zu jedem Typ von Events gibt es eine entsprechende Ereignisroutine
    • ändert Zustand des Systems
    • erzeugt in der Regel neue Events und fügt sie in die Liste ein
    • kann die Simulation beenden
  • prinzipielle Ausführung

    • setInitialState()
      setInitialEvents()
      t = 0
      while true          % beenden durch Eventroutine
        nextEvent = getNextEvent(liste)
        t = nextEvent.t
        runRoutine(nextEvent)
      end

  • bei gleichzeitigen Events
    • haben Reihenfolge in der Liste
    • häufig durch Kausalität gegeben ("verlasse Queue", "betrete Server")
    • sonst durch Prioritäten ("verlasse Server" vor "verlasse Generator")
    • oft nur implizit geregelt - wenn überhaupt!
• Ereignisroutinen beim D/D/1-Beispiel:
  • Initialisierung

    • tG = 1, tS = 1.5, tEnd = 10, serverFree = true

  • Eventtypen
    • Entry (neue Entität wird erzeugt)
    • Leave (Entität verlässt Server)
    • Stop (Zeit ist um)
  • Routine für Entry

    • scheduleEntry()        % setze nächstes Entry-Event in Liste
      if serverFree
        serverFree = false
        scheduleLeave()      % setze nächstes Leave-Event in Liste
      else
        addToQueue(entity)
      end

  • Routine für Leave

    • destroy(entity)
      if isQueueEmpty()
        serverFree = true
      else
        removeFromQueue(entity)
        serverFree = false
        scheduleLeave()
      end

  • Routine für Stop

    • if t == tEnd
        exit
      end

• Ablauf im Beispiel D/D/1:
  • per Hand durchführen
  • Ergebnis (Event-Tabelle)

    •   t  nQ SFree list
       0.0  0   1   1.0E/10.0S/
       1.0  0   0   2.0E/2.5L/10.0S/
       2.0  1   0   2.5L/3.0E/10.0S/
       2.5  0   0   3.0E/4.0L/10.0S/
       3.0  1   0   4.0L/4.0E/10.0S/
       4.0  0   0   4.0E/5.5L/10.0S/
       4.0  1   0   5.0E/5.5L/10.0S/
       5.0  2   0   5.5L/6.0E/10.0S/
       5.5  1   0   6.0E/7.0L/10.0S/
       6.0  2   0   7.0L/7.0E/10.0S/
       7.0  1   0   7.0E/8.5L/10.0S/
       7.0  2   0   8.0E/8.5L/10.0S/
       8.0  3   0   8.5L/9.0E/10.0S/
       8.5  2   0   9.0E/10.0S/10.0L/
       9.0  3   0   10.0S/10.0L/10.0E/
      10.0  3   0   10.0L/10.0E/

  • Vergleich mit Tabelle von oben
    • grundsätzlich identisch
    • Entities haben keine Identität, nur Anzahl in Queue
    • gleichzeitige Events bei 4.0 wie oben
    • gleichzeitige Events bei 10.0 anders: STOP kommt zuerst
• Problem bei DES:
  • globale Sicht (von außen auf das ganze Modell)
    • globale Ereignisliste
    • global agierende Eventroutinen
  • bei komplexen Systemen schwierig zu erstellen bzw. nachzuvollziehen
  • andere Modellierungsverfahren
    • aus der Sicht der Akteure  (prozess-orientiert)
    • aus der Sicht der Entitäten (transaktions-orientiert)
    • aus der Sicht der Komponenten (komponenten-orientiert)
  • basieren intern auf DES
• Prozess-orientierte Simulation:
  • Ereignisse werden Akteuren (abstrahiert als Prozesse) zugeordnet
  • Aktivität = Menge von Operationen eines Akteurs während eines Zeitintervalls
    • z.B. "Kunde wartet" (in der Queue) oder "Kunde zahlt" (an der Kasse)
    • z.B. "Kasse bedient" oder "Kasse wartet"
    • hat jeweils Start- und End-Event
  • Prozess = Folge von Aktivitäten eines Akteurs
    • End-Event einer Aktivität ist Start-Event der folgenden Aktivität
  • z. B. Prozess Kunde mit Aktivitäten
    • Kunde kommt - Kunde wartet - Kunde bezahlt - Kunde geht
  • z. B. Prozess Kasse mit Aktivitäten
    • Kasse wartet - Kasse bedient - Kasse wartet - ... (bis Simulationsende)
  • mögliche Zustände eines Prozesses
    • aktiv: eine seiner Aktivitäten wird ausgeführt
    • wartend: zukünftige Aktivitäten sind geplant
    • passiv: keine zukünftigen Aktivitäten sind geplant
  • Prozess kann anderen passiven Prozess aktivieren
    • z.B. bei Ende von "Kasse bedient" wird nächster Kunde aktiv
  • Vorteile
    • besser nachvollziehbar als direktes DES
    • graphische Unterstützung vorhanden
  • Nachteile
    • komplexe Simulationsroutine muss zwischen Prozessen umschalten
    • Prozess-Routinen komplexer als Event-Routinen
    • häufig deutlich größere Zahl von Ereignissen
• Spezielle Sichtweisen der prozess-orientierten Simulation:
  • transaktions-orientiert
    • Akteure sind die Entitäten
    • sie laufen von Komponente zu Komponente
    • haben oft zusätzliche Eigenschaften (u.a. eine Id)
    • Ablauf des D/D/1-Modells mit Entitäten in der Entitäten-Tabelle (s.o.)
  • komponenten-orientiert
    • Akteure sind die Komponenten
    • sie verarbeiten einlaufende Entitäten und reichen sie weiter
    • Akteure neben Queues oder Servern auch Verzweigungen, Schalter etc.
  • oft eher eine Frage der Sichtweise als des Programmablaufs
  • Uneindeutigkeiten bei gleichzeitigen Events
    • transaktions-orientiert: welche Entity läuft zuerst weiter?
    • komponenten-orientiert: welche Komponente arbeitet zuerst?
    • in konkreten Simulationsprogrammen oft schwierig aufzulösen bzw. überhaupt zu sehen
• Aufgaben
  • Aufgabe 13
  • Aufgabe 14