5. Discrete Event Simulation

Part of CS:2820 Object Oriented Software Development Notes, Fall 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

The Discrete-Event Simulation Algorithm

The basic discrete-event simulation algorithm has been known since the mid 1960s, and the algorithm applies to just about any discrete event model. The central feature of the model is a data structure, the pending event set. This is, as its name suggests, a set of pending events, that is, events that have been caused by events in the past but have not yet occurred.

The basic operations on the pending event are:

schedule e
The event e is inserted into the pending event set. The event e.time is the time at which the event is scheduled to occur.

e = getNext
The event e is extracted from the pending event set; e.time is less than or equal to the times of all other events in the set, and if other events in the set are scheduled to occur at exactly the same time, the model may be nondeterministic.

Some discrete-event models allow previously scheduled events to be deleted. Some higher level models consider events that extend over time, but we will ignore these. (Events that take time can be modeled by a sequence of instantaneous events, for example, one that starts the high-level event and another that marks its end).

The basic algorithm can be stated in a Java-like language as:

// for all x from the set of initial events
eventSet.schedule( x )
repeat {
	e = eventSet.getNext
	// simulate event e at time e.time
	// this may involve scheduling new events
}

There are two ways to terminate such a simulation: Either one of the initially scheduled events is a "terminate" event marking the end of time, or the model runs until the event set is empty.

In either case, within any iteration of the loop, e.time is the current time, and time lurches forward from event to event in an irregular manner. This is quite different from simulation models in which time advances in uniform-sized ticks; that type of model is more commonly used to deal with systems that are described by differential equations.

Note however that within the simulation of any event, the model may use arbitrarily complex code to predict the times of future events. In extreme cases, this prediction might involve running other simulation models, for example, involving differential equations.

A Classic Example

Consider the problem of modelling a bank. We begin with an informal description of one customer's visit to the bank: You arrive at the bank, wait in line for an available teller, interact with that teller for a while, and then leave. Tellers may need to do some paperwork or computer work after a customer departs before they are ready for the next customer. From this description, we can determine that our model will have the following objects and classes:

A little more thought allows us to refine this by identifying events: