Page 247 - DCAP601_SIMULATION_AND_MODELING

Unit 13: Simulation Languages (I)

Components of a Discrete-event Simulation Notes

In addition to the representation of system state variables and the logic of what happens when
system events occur, discrete event simulations include the following:
Clock: The simulation must keep track of the current simulation time, in whatever measurement
units are suitable for the system being modeled. In discrete-event simulations, as opposed to
real time simulations, time ‘hops’ because events are instantaneous – the clock skips to the next
event start time as the simulation proceeds.
Events List: The simulation maintains at least one list of simulation events. This is sometimes
called the pending event set because it lists events that are pending as a result of previously
simulated event but have yet to be simulated themselves. An event is described by the time at
which it occurs and a type, indicating the code that will be used to simulate that event. It is
common for the event code to be parameterised, in which case, the event description also
contains parameters to the event code.
When events are instantaneous, activities that extend over time are modeled as sequences of
events. Some simulation frameworks allow the time of an event to be specified as an interval,
giving the start time and the end time of each event.
Single-threaded simulation engines based on instantaneous events have just one current event.
In contrast, multi-threaded simulation engines and simulation engines supporting an interval-
based event model may have multiple current events. In both cases, there are significant problems
with synchronization between current events.
The pending event set is typically organized as a priority queue, sorted by event time. That is,
regardless of the order in which events are added to the event set, they are removed in strictly
chronological order. Several general-purpose priority queue algorithms have proven effective
for discrete-event simulation, most notably, the splay tree. More recent alternatives include
skip lists and calendar queues.
Typically, events are scheduled dynamically as the simulation proceeds. For example, in the
bank example noted above, the event CUSTOMER-ARRIVAL at time t would, if the
CUSTOMER_QUEUE was empty and TELLER was idle, include the creation of the subsequent
event CUSTOMER-DEPARTURE to occur at time t+s, where s is a number generated from the
SERVICE-TIME distribution.

Random-number Generators

The simulation needs to generate random variables of various kinds, depending on the system
model. This is accomplished by one or more pseudorandom number generators. The use of
pseudorandom numbers as opposed to true random numbers is a benefit should a simulation
need a rerun with exactly the same behaviour.

One of the problems with the random number distributions used in discrete-event simulation is
that the steady-state distributions of event times may not be known in advance. As a result, the
initial set of events placed into the pending event set will not have arrival times representative
of the steady-state distribution. This problem is typically solved by bootstrapping the simulation
model. Only a limited effort is made to assign realistic times to the initial set of pending events.
These events, however, schedule additional events, and with time, the distribution of event
times approaches its steady state. This is called bootstrapping the simulation model. In gathering
statistics from the running model, it is important to either disregard events that occur before the
steady state is reached or to run the simulation for long enough that the bootstrapping behavior
is overwhelmed by steady-state behavior.

LOVELY PROFESSIONAL UNIVERSITY 241