An Introduction to Discrete-Event Simulation

Note: This material is based on the web page discreteEventSim.html, Copyright © 2000, H. Conrad Cunningham, who in turn credits "Chapter 3 of the book Practical Process Simulation: Using Object-Oriented Techniques and C++ by Jose' M. Garrido (Artech House, 1999)." I make no claims of any substantial change or additions to Cunningham's or Garrido's works, but my purpose in changing the earlier documents is to tailor the material to a particular syllabus. If there is anything you question here, please blame me and not the original authors, or refer back to the original works. -Roger Dannenberg

Modeling of Dynamic Systems

Assumption for our study:
Our models will execute on sequential computers in a single process.

The techniques used on parallel computers may differ.

dynamic stochastic systems:
systems whose behavior changes with time and have some uncertainty.

can be expressed as a function of time

an instantaneous occurrence that changes the state of the system

an event initiates a corresponding operation ...

a sequence of activities that changes the state of the system

the smallest unit of work

activities have finite durations

observable state changes are assumed to happen at the beginning or ending of activities

a sequence of events, operationsm, and activities in chronological order corresponding to the behavior of an entity in the real system

Structure of Simulation Software

model program:
a computer program that implements a simulation model of a system

Model programs consist of three levels of software:

  1. simulation executive

  2. model program

  3. utility routines

Time in Simulation

In a simulation we deal with two notions of time:

We require run times small enough to get a result within the resources available.

However, the simulation time is more important in terms of the result and how the simulation is organized.

event time:
the simulation time at which an event occurs

Techniques for changing the time on the simulation clock:

Synchronous Simulation Executives

General algorithm:

    while simulation time not at end
       increment time by predetermined unit
       if events occurred during time interval
           simulate those events 


Event-Scanning Executives

General algorithm:

    while event list not empty and simulation time not at end
        get unsimulated event with earliest time
        advance simulation clock to time of event
        simulate the event

Both synchronous and event-scanning techniques simulate parallelism of the processes.

Implementation of Discrete Event Simulation

Operationally, a discrete-event simulation is a chronologically nondecreasing sequence of event occurrences.

event record:
a pairing of an event with its event time
future event list (FEL) (or just event list):
a list ordered by nondecreasing simulation time (e.g., in a priority queue)
event (list) driven simulation:
simulation where time is advanced to the time given by the first event record from the event list

Requirements for support of discrete-event simulation:

Approaches to Discrete Event Simulation

Three general approaches:

  1. activity scanning
  2. event scheduling
  3. process interaction

Activity Scanning

Event Scheduling

Process Interaction

Implementing Process Simulation

Object-Oriented Modeling and Process Simulation

Discrete Event Simulation Languages

Discrete event simulation packages and languages must provide at least the following facilities:

  1. Generation of random numbers from various probability distributions
  2. A timing executive or time flow mechanism to provide an explicit representation of time
  3. List processing mechanisms to create, delete, and manipulate objects as sets or members of sets
  4. Statistical analysis routines to provide a descriptive summary of model behavior

simulation package:
a set of routines written in a conventional programming language that can be called by a model program to request services in the above list
simulation language:
a special purpose language that provides high-level language abstractions and operations to support convenient expression of simulation model programs

Processes, Coroutines, Objects, and Events

A simulation can use different implementation techniques (+ indicates advantages, − indicates drawbacks in the following lists):