From Wikipedia, the free 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 ^[1]. For example, 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 variables 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.

Contents 1 Components of a Discrete-Event Simulation 1.1 Clock 1.2 Events List 1.3 Random Number Generators 1.4 Statistics 1.5 Ending Condition 2 Simulation Engine Logic 2.1 Start 2.2 “Do loop” or “While loop” 2.3 End 3 See also 3.1 System Modeling Approaches 3.2 Computational Techniques 4 External links 5 References 6 Further Reading

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:

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.

The simulation maintains at least one list of simulation events. An event must have a start time, some kind of code that constitutes the performance of the event itself, and possibly an end time. In some approaches, there are separate lists for current and future events. Events lists are sorted by event start time. Typically, events are “bootstrapped” – that is, they 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.

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 simulation typically keeps track of statistics about the system, which quantify the aspects of interest. In the bank example, it is of interest to track the mean service times.

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 “when statistical measure X reaches the value x”.

The main loop of a discrete-event simulation will be something like this:

• 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).

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.

• Generate statistical report.

• 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
• Petri net and the interactive stochastic Petri net software tool StpnPlay

• Computer simulation
• Monte Carlo method
• Variance reduction
• Random number generation

• SimPy an opensource general purpose DES.
• Simulation Frameworks list of simulation software development frameworks.

• ↑  Stewart Robinson (2004). Simulation - The practice of model development and use. Wiley. 
• Michael Pidd (1998). Computer simulation in management science - fourth edition. Wiley. 

• Jerry Banks, John Carson, Barry Nelson and David Nicol (2005). Discrete-event system simulation - fourth edition. Pearson. 
• Averill M. Law and W. David Kelton (2000). Simulation modeling and analysis - third edition. McGraw-Hill.