 Discrete event simulation

In discreteevent simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system ^{[1]}. For example, if an elevator is simulated, an event could be "level 6 button pressed", with the resulting system state of "lift moving" and eventually (unless one chooses to simulate the failure of the lift) "lift at level 6".
A common exercise in learning how to build discreteevent 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 CUSTOMERQUEUE and TELLERS. The system events are CUSTOMERARRIVAL and CUSTOMERDEPARTURE. (The event of TELLERBEGINSSERVICE can be part of the logic of the arrival and departure events.) The system states, which are changed by these events, are NUMBEROFCUSTOMERSINTHEQUEUE (an integer from 0 to n) and TELLERSTATUS (busy or idle). The random variables that need to be characterized to model this system stochastically are CUSTOMERINTERARRIVALTIME and TELLERSERVICETIME.
A number of mechanisms have been proposed for carrying out discreteevent simulation, among them are the eventbased, activitybased, processbased and threephase approaches (Pidd, 1998). The threephase 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.
Contents
Components of a DiscreteEvent Simulation
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 discreteevent 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.
Singlethreaded simulation engines based on instantaneous events have just one current event. In contrast, multithreaded simulation engines and simulation engines supporting an intervalbased 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.^{[2]} That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Several generalpurpose priority queue algorithms have proven effective for discreteevent simulation,^{[3]} most notably, the splay tree. More recent alternatives include skip lists and calendar queues.^{[4]}
Typically, events are scheduled dynamically as the simulation proceeds. For example, in the bank example noted above, the event CUSTOMERARRIVAL at time t would, if the CUSTOMER_QUEUE was empty and TELLER was idle, include the creation of the subsequent event CUSTOMERDEPARTURE to occur at time t+s, where s is a number generated from the SERVICETIME distribution.
RandomNumber 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 discreteevent simulation is that the steadystate 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 steadystate 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 steadystate behavior. (This use of the term bootstrapping can be contrasted with its use in both statistics and computing.)
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.
Ending Condition
Because events are bootstrapped, theoretically a discreteevent 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 discreteevent simulation is something like this:
Start
 Initialize Ending Condition to FALSE.
 Initialize system state variables.
 Initialize Clock (usually starts at simulation time zero).
 Schedule an initial event (i.e., put some initial event into the Events List).
“Do loop” or “While loop”
While (Ending Condition is FALSE) 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 (Theory of Constraints) 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, ontime 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.
Custom order environments
Many systems show very different characteristics from day to day depending on the order mix. Many small orders may cause bottlenecks due to excess changeovers. Large custom orders may require extra processing at a point where the system has particularly low capacity. Simulation modeling allows management to understand what changes ‘on average’ would have the largest impact and greatest returnoninvestment.
Lab test performance improvement ideas
Many systems improvement ideas are built on sound principles, proven methodologies (Lean, Six Sigma, TQM, etc.) 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
Simulation modeling is commonly used to model potential investments. Through modeling investments decisionmakers can make informed decisions and evaluate potential alternatives.
Often these decisions look at altering existing operations. Typically, a model of the current state is constructed. This ‘current state’ model is tested and validated against historical data. Once the model is operating correctly, the simulation is altered to reflect the proposed capital investments. This 'future state' model is then stresstested to ensure the alterations perform as desired.
Occasionally, organizations take on entirely new operations processes. These could be new Lean facilities, designed around new products or using new technology. In these cases only a ‘future state’ model is constructed. The testing and validation may require more analysis. There are companies and experts that specialize in simulation building who may be brought in to help.
Stress test a system
Models can be used to understand how a system will be able to weather extraordinary conditions. A simulation can help management understand: large increases in orders, significant swings in product mix, new client delivery demands (e.g. 1 week lead times), and economic events (e.g. a multinational with operations in South America and Asia sees significant swings in currencies).
See also
System Modeling approaches:
 Finitestate machine and a special case, Markov chain
 Stochastic process and a special case, Markov process
 Queueing theory and in particular Birthdeath process
 Discrete Event System Specification
Computational techniques:
 Computer simulation
 Monte Carlo method
 Variance reduction
 Pseudo random number generator
Software:
Disciplines:
References
 ^ Stewart Robinson (2004). Simulation  The practice of model development and use. Wiley.
 ^ Douglas W. Jones, ed. Implementations of Time, Proceedings of the 18th Winter Simulation Conference, 1986.
 ^ Douglas W. Jones, Empirical Comparison of Priority Queue and Event Set Implementations, Communications of the ACM, 29, April 1986, pages 300311.
 ^ Kah Leong Tan and LiJin Thng, SNOOPy Calendar Queue, Proceedings of the 32nd Winter Simulation Conference, 2000
Further reading
 Michael Pidd (1998). Computer simulation in management science  fourth edition. Wiley.
 Jerry Banks, John Carson, Barry Nelson and David Nicol (2005). Discreteevent system simulation  fourth edition. Pearson.
 Averill M. Law and W. David Kelton (2000). Simulation modeling and analysis  third edition. McGrawHill.
 Bernard P. Zeigler, Herbert Praehofer and Tag Gon Kim (2000). Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems  second edition. Academic Press.
 Roger W. McHaney (1991). Computer Simulation: A Practical Perspective. Academic Press.
 William Delaney, Erminia Vaccari (1988). Dynamic Models and Discrete Event Simulation. Dekker INC.
 A, Alan Pritsker, Jean J. O'Reilly (1999). Simulation with Visual SLAM and AweSim. Wiley.
 James J. Nutaro (2010). Building software for simulation: theory and algorithms, with applications in C++. Wiley.
External links
 Simulation tools list of simulation tools
 The Use of Simulation Software based on an example of a bank’s customer service department
Categories: Simulation
 Scientific modeling
 Events (computing)
Wikimedia Foundation. 2010.
Look at other dictionaries:
List of discrete event simulation software — This is a list of discrete event simulation software.* AnyLogic is a graphical general purpose simulation tool which supports discrete event (process centric), system dynamics and agent based modeling approaches. In discrete event simulation it… … Wikipedia
Discrete Event System Specification — DEVS (de l anglais Discrete Event System Specification) est un formalisme modulaire et hiérarchique pour la modélisation, la simulation et l analyse de systèmes complexes qui peuvent être des systèmes à événements discrets décrits par des… … Wikipédia en Français
Discrete event dynamic system — In control engineering, a discrete event dynamic system (DEDS) is a discrete state, event driven system of which the state evolution depends entirely on the occurrence of asynchronous discrete events over time. Although similar to continuous… … Wikipedia
Software choice for discrete event simulations — Tools for discrete event simulationsDiscrete event simulations may be written in any general purpose computer language such as C++ but to construct an industry grade project in reasonable time with a general computing language consumes too much… … Wikipedia
Finite & Deterministic Discrete Event System Specification — FD DEVS (Finite Deterministic Discrete Event System Specification) is a formalism for modeling and analyzing discrete event dynamic systems in both simulation and verification ways. FD DEVS also provides modular and hierarchical modeling features … Wikipedia
Simulation software — is based on the process of imitating a real phenomenon with a set of mathematical formulas. It is, essentially, a program that allows the user to observe an operation through simulation without actually running the program. Simulation software is … Wikipedia
Simulation — Simulator redirects here. For other uses, see Simulator (disambiguation). For other uses, see Simulation (disambiguation). Not to be confused with Stimulation. Wooden mechanical horse simulator during WWI. Simulation is the imitation of some real … Wikipedia
Simulation language — A computer simulation language describes the operation of a simulation on a computer. There are two major types of simulation: continuous and discrete event though more modern languages can handle combinations. Most languages also have a… … Wikipedia
Event symmetry — The term Event symmetry describes invariance principles that have been used in some discrete approaches to quantum gravity where the diffeomorphism invariance of general relativity can be extended to a covariance under any permutation of… … Wikipedia
Simulation informatique — Simulation numérique du tsunami dû au tremblement de terre du 26 décembre 2004. La simulation numérique est l’un des outils permettant de simuler des phénomènes réels. Appelée aussi simulation informatique, elle désigne un procédé selon lequel on … Wikipédia en Français