Discrete Event Simulation
Encyclopedia
In discrete
-event 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 . 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 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 event of TELLER-BEGINS-SERVICE can be part of the logic of the arrival and departure events.) The system states, which are changed by these events, are NUMBER-OF-CUSTOMERS-IN-THE-QUEUE (an integer from 0 to n) and TELLER-STATUS (busy or idle). The random variable
s that need to be characterized to model this system stochastically are CUSTOMER-INTERARRIVAL-TIME and TELLER-SERVICE-TIME.
A number of mechanisms have been proposed for carrying out discrete-event simulation, among them are the event-based, activity-based, process-based and three-phase approaches (Pidd, 1998). 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.
, time ‘hops’ because events are instantaneous – the clock skips to the next event start time as the simulation proceeds.
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 list
s 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.
s. 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. (This use of the term bootstrapping can be contrasted with its use in both statistics
and computing.)
s, which quantify the aspects of interest. In the bank example, it is of interest to track the mean waiting times.
(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, on-time delivery rate, scrap rate, cash cycles, and so on.
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.
, 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.
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 stress-tested 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.
Computational techniques:
Software:
Disciplines:
Discrete time
Discrete time is the discontinuity of a function's time domain that results from sampling a variable at a finite interval. For example, consider a newspaper that reports the price of crude oil once every day at 6:00AM. The newspaper is described as sampling the cost at a frequency of once per 24...
-event simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
, the operation of a system
System
System is a set of interacting or interdependent components forming an integrated whole....
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 . 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 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 event of TELLER-BEGINS-SERVICE can be part of the logic of the arrival and departure events.) The system states, which are changed by these events, are NUMBER-OF-CUSTOMERS-IN-THE-QUEUE (an integer from 0 to n) and TELLER-STATUS (busy or idle). The random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s that need to be characterized to model this system stochastically are CUSTOMER-INTERARRIVAL-TIME and TELLER-SERVICE-TIME.
A number of mechanisms have been proposed for carrying out discrete-event simulation, among them are the event-based, activity-based, process-based and three-phase approaches (Pidd, 1998). 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.
Components of a Discrete-Event 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 discrete-event simulations, as opposed to real time simulationsReal-time Simulation
Real-time Simulation refers to a computer model of a physical system that can execute at the same rate as actual "wall clock" time. In other words, the computer model runs at the same rate as the actual physical system...
, 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 setbecause 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
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
, 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
Splay tree
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
. More recent alternatives include skip list
Skip list
A skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items...
s 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 generatorPseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
s. 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. (This use of the term bootstrapping can be contrasted with its use in both statistics
Bootstrapping (statistics)
In statistics, bootstrapping is a computer-based method for assigning measures of accuracy to sample estimates . This technique allows estimation of the sample distribution of almost any statistic using only very simple methods...
and computing.)
Statistics
The simulation typically keeps track of the system's statisticStatistic
A statistic is a single measure of some attribute of a sample . It is calculated by applying a function to the values of the items comprising the sample which are known together as a set of data.More formally, statistical theory defines a statistic as a function of a sample where the function...
s, 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 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”.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.
Diagnosing process issues
Simulation approaches are particularly well equipped to help users diagnose issues in complex environments. The GoalThe Goal
The Goal is a management-oriented novel by Dr. Eliyahu M. Goldratt, a business consultant whose Theory of Constraints has become a model for systems management. It was originally published in 1984 and has since been revised and republished every few years, once in 1992 and again in 2004...
(Theory of Constraints
Theory of Constraints
The theory of constraints adopts the common idiom "A chain is no stronger than its weakest link" as a new management paradigm. This means that processes, organizations, etc., are vulnerable because the weakest person or part can always damage or break them or at least adversely affect the...
) 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.
Custom order environments
Many systems show very different characteristics from day to day depending on the order mix. Many small orders may cause bottle-necks 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 return-on-investment.Lab test performance improvement ideas
Many systems improvement ideas are built on sound principles, proven methodologies (LeanLean
-In business:* Lean Startup, how to start a company in a lean way* Lean manufacturing, process improvement discipline* Lean construction is a translation and adaption of lean manufacturing principles and practices to the end-to-end design and construction process...
, Six Sigma
Six Sigma
Six Sigma is a business management strategy originally developed by Motorola, USA in 1986. , it is widely used in many sectors of industry.Six Sigma seeks to improve the quality of process outputs by identifying and removing the causes of defects and minimizing variability in manufacturing and...
, TQM
Total Quality Management
Total quality management or TQM is an integrative philosophy of management for continuously improving the quality of products and processes....
, 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 decision-makers 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 stress-tested to ensure the alterations perform as desired.
Occasionally, organizations take on entirely new operations processes. These could be new Lean
Lean
-In business:* Lean Startup, how to start a company in a lean way* Lean manufacturing, process improvement discipline* Lean construction is a translation and adaption of lean manufacturing principles and practices to the end-to-end design and construction process...
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:- Finite-state machine and a special case, Markov chainMarkov chainA Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
- Stochastic processStochastic processIn probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
and a special case, Markov processMarkov processIn probability theory and statistics, a Markov process, named after the Russian mathematician Andrey Markov, is a time-varying random phenomenon for which a specific property holds... - Queueing theoryQueueing theoryQueueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the queue, waiting in the queue , and being served at the front of the queue...
and in particular Birth-death processBirth-death processThe birth–death process is a special case of continuous-time Markov process where the states represent the current size of a population and where the transitions are limited to births and deaths... - Discrete Event System Specification
Computational techniques:
- Computer simulationComputer simulationA computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...
- Monte Carlo methodMonte Carlo methodMonte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
- Variance reductionVariance reductionIn mathematics, more specifically in the theory of Monte Carlo methods, variance reduction is a procedure used to increase the precision of the estimates that can be obtained for a given number of iterations. Every output random variable from the simulation is associated with a variance which...
- Pseudo random number generator
Software:
Disciplines:
- Industrial engineeringIndustrial engineeringIndustrial engineering is a branch of engineering dealing with the optimization of complex processes or systems. It is concerned with the development, improvement, implementation and evaluation of integrated systems of people, money, knowledge, information, equipment, energy, materials, analysis...
- Network simulationNetwork simulationIn communication and computer network research, network simulation is a technique where a program models the behavior of a network either by calculating the interaction between the different network entities using mathematical formulas, or actually capturing and playing back observations from a...
External links
- Simulation tools list of simulation tools
- The Use of Simulation Software based on an example of a bank’s customer service department