In the field of simulation, a discrete-event simulation, models the
operation of a system as a discrete sequence of events in time. Each event
occurs at a particular instant in time and marks a change of state in the
system. Between consecutive events, no change in the system is assumed to
occur; thus the simulation can directly jump in time from one event to the next.
This contrasts with continuous simulation in which the simulation
continuously tracks the system dynamics over time. Instead of being event-based,
this is called an activity-based simulation; time is broken up into small
time slices and the system state is updated according to the set of
activities happening in the time slice. Because discrete-event simulations do
not have to simulate every time slice, they can typically run much faster than
the corresponding continuous simulation. Another alternative to event-based
simulation is process-based simulation. In this approach, each activity in a
system corresponds to a separate process, where a process is typically
simulated by a thread in the simulation program. In this case, the discrete
events, which are generated by threads, would cause other threads to sleep,
wake, and update the system state. A more recent method is the three-phased
approach to discrete event simulation. In this approach, the first phase is to
jump to the next chronological event. The second phase is to execute all
events that unconditionally occur at that time. The third phase is to execute
all events that conditionally occur at that time. The three phase approach is a
refinement of the event-based approach in which simultaneous events are ordered
so as to make the most efficient use of computer resources. The three-phase
approach is used by a number of commercial simulation software packages,
but from the user's point of view, the specifics of the underlying simulation
method are generally hidden. Example
A common exercise in learning how to build discrete-event simulations is to
model a queue, such as customers arriving at a bank to be served by a
teller. In this example, the system entities are Customer-queue′ and
Tellers. The system events are Customer-Arrival and Customer-Departure.
The system states, which are changed by these events, are
Number-of-Customers-in-the-Queue and Teller-Status. The random variables that
need to be characterized to model this system stochastically are
Customer-Interarrival-Time and Teller-Service-Time. An agent-based
framework for performance modeling of an optimistic parallel discrete event
simulator is another example for a discrete event simulation.
Components of a discrete-event simulation
In addition to the logic of what happens when system events occur, discrete event
simulations include the following: = State=
A system state is a set of variables that captures the salient properties of
the system to be studied. The state trajectory overtime S(t) can be
mathematically represented by a step function whose values change in
correspondence of discrete events. = 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 parametrized, 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, calendar queues, and
ladder 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 pseudo-random numbers as opposed to true random
numbers is a benefit should a simulation need a rerun with exactly the same
behavior. 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.
= Statistics= The simulation typically keeps track of
the system's statistics, which quantify the aspects of interest. In the bank
example, it is of interest to track the mean waiting times. In a simulation
model, performance metrics are not analytically derived from probability
distributions, but rather as averages over replications, that is different
runs of the model. Confidence intervals are usually constructed to help assess
the quality of the output. = Ending condition=
Because events are bootstrapped, theoretically a discrete-event
simulation could run forever. So the simulation designer must decide when the
simulation will end. Typical choices are “at time t” or “after processing n
number of events” or, more generally, “when statistical measure X reaches the
value x”. Simulation engine logic
The main loop of a discrete-event simulation is something like this:
= Start= Initialize Ending Condition to FALSE.
Initialize system state variables. Initialize Clock.
Schedule an initial event. = “Do loop” or “while loop”=
While then do the following: Set clock to next event time.
Do next event and remove from the Events List.
Update statistics. = End=
Generate statistical report. Common uses
= Diagnosing process issues= Simulation approaches are particularly
well equipped to help users diagnose issues in complex environments. The Goal
illustrates the importance of understanding bottlenecks in a system.
Only process ‘improvements’ at the bottlenecks will actually improve the
overall system. In many organizations bottlenecks become hidden by excess
inventory, overproduction, variability in processes and variability in routing
or sequencing. By accurately documenting the system inside a simulation model it
is possible to gain a bird’s eye view of the entire system.
A working model of a system allows management to understand performance
drivers. A simulation can be built to include any number of performance
indicators such as worker utilization, on-time delivery rate, scrap rate, cash
cycles, and so on. Hospital applications
An operating theater is generally shared between several surgical disciplines.
Through better understanding the nature of these procedures it may be possible
to increase the patient throughput. Example: If a heart surgery takes on
average four hours, changing an operating room schedule from eight
available hours to nine will not increase patient throughput. On the
other hand, if a hernia procedure takes on average twenty minutes providing an
extra hour may also not yield any increased throughput if the capacity and
average time spent in the recovery room is not considered.
= Lab test performance improvement ideas=
Many systems improvement ideas are built on sound principles, proven
methodologies yet fail to improve the overall system. A simulation model
allows the user to understand and test a performance improvement idea in the
context of the overall system. = Evaluating capital investment
decisions= See also: Monte Carlo methods in
finance; Corporate finance #Capital investment decisions and #Quantifying
uncertainty. Simulation modeling is commonly used to
model potential investments. Through modeling investments decision-makers can
make informed decisions and evaluate potential alternatives.
= Network simulators= Discrete event simulation is used in
computer network to simulate new protocols for different network traffic
scenarios before deployment. See also
System modeling approaches: Finite-state machine and a special case,
Markov chain Stochastic process and a special case,
Markov process Queueing theory and in particular
birth-death process Discrete Event System Specification
Transaction-level modeling Computational techniques:
Computer experiment Computer simulation
Monte Carlo method Variance reduction
Pseudo random number generator Software:
List of computer simulation software List of discrete event simulation
software Disciplines:
Industrial engineering Network simulation
References Further reading
Myron H. MacDougall. Simulating Computer Systems: Techniques and Tools. MIT
Press. William Delaney, Erminia Vaccari.
Dynamic Models and Discrete Event Simulation. Dekker INC.
Roger W. McHaney. Computer Simulation: A Practical Perspective. Academic Press.
Michael Pidd. Computer simulation in management science – fourth edition.
Wiley. A, Alan Pritsker, Jean J. O'Reilly.
Simulation with Visual SLAM and AweSim. Wiley.
Averill M. Law and W. David Kelton. Simulation modeling and analysis – third
edition. McGraw–Hill. Bernard P. Zeigler, Herbert Praehofer
and Tag Gon Kim. Theory of modeling and simulation: Integrating discrete event
and continuous complex dynamic systems – second edition. Academic Press.
Jerry Banks, John Carson, Barry Nelson and David Nicol. Discrete-event system
simulation – fourth edition. Pearson. James J. Nutaro. Building software for
simulation: theory and algorithms, with applications in C++. Wiley.