Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Discrete-event simulation
open-in-new
<h2 id="example">Example</h2> <p>A common exercise in learning how to build discrete-event simulations is to model a <a href="/facts/Queueing_theory/8NDl56EM">queueing system</a>, such as customers arriving at a bank teller to be served by a clerk. In this example, the system objects are <i>Customer</i> and <i>Teller</i>, while the system events are <i>Customer-Arrival</i>, <i>Service-Start</i> and <i>Service-End</i>. Each of these events comes with its own dynamics defined by the following event routines: </p> <ol><li>When a <i>Customer-Arrival</i> event occurs, the state variable <i>queue-length</i> is incremented by 1, and if the state variable <i>teller-status</i> has the value "available", a <i>Service-Start</i> follow-up event is scheduled to happen without any delay, such that the newly arrived customer will be served immediately.</li> <li>When a <i>Service-Start</i> event occurs, the state variable <i>teller-status</i> is set to "busy" and a <i>Service-End</i> follow-up event is scheduled with a delay (obtained from sampling a <i>service-time</i> random variable).</li> <li>When a <i>Service-End</i> event occurs, the state variable <i>queue-length</i> is decremented by 1 (representing the customer's departure). If the state variable <i>queue-length</i> is still greater than zero, a <i>Service-Start</i> follow-up event is scheduled to happen without any delay. Otherwise, the state variable <i>teller-status</i> is set to "available".</li></ol> <p>The <a href="/facts/Random_variable/TwTBXnLT">random variables</a> that need to be characterized to model this system <a href="/facts/Stochastic/uMbgL94r">stochastically</a> are the <i>interarrival-time</i> for recurrent <i>Customer-Arrival</i> events and the <i>service-time</i> for the delays of <i>Service-End</i> events. </p> <h2 id="components">Components</h2> <h3>State</h3> <p>A system state is a set of variables that captures the salient properties of the system to be studied. The state trajectory over time S(t) can be mathematically represented by a <a href="/facts/Step_function/VnrEjo4B">step function</a> whose value can change whenever an event occurs. </p> <h3>Clock</h3> <p>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 continuous simulations, time 'hops' because events are instantaneous – the clock skips to the next event start time as the simulation proceeds. </p> <h3>Events list</h3> <p class="note">"Future event list" redirects here. For lists of future events, see <a href="/facts/Timelines_of_the_future/baXFXaxQ">Timelines of the future</a>.</p> <p>The simulation maintains at least one list of simulation events. This is sometimes called the <i>pending event set</i> 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. The event list is also referred to as the <i>future event list</i> (FEL) or <i>future event set</i> (FES).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>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. </p><p><a href="/facts/Single-threaded/hh8WHyPd">Single-threaded</a> simulation engines based on instantaneous events have just one current event. In contrast, <a href="/facts/Thread_(computing)/hh8WHyPd">multi-threaded</a> 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. </p><p>The pending event set is typically organized as a <a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a>, <a href="/facts/Sorting/olGzsItY">sorted</a> by event time.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Various priority queue implementations have been studied in the context of discrete event simulation;<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> alternatives studied have included <a href="/facts/Splay_tree/DHKCdoST">splay trees</a>, <a href="/facts/Skip_list/fF200SJg">skip lists</a>, <a href="/facts/Calendar_queue/vN7qNRTp">calendar queues</a>,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> and ladder queues.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> On <a href="/facts/Massively_parallel_processor_array/GXJQ6fGS">massively-parallel machines</a>, such as <a href="/facts/Multi-core_processor/ABNb65hQ">multi-core</a> or <a href="/facts/Manycore_processor/ozoxeNzT">many-core</a> CPUs, the pending event set can be implemented by relying on <a href="/facts/Non-blocking_algorithm/KhLDma0v">non-blocking algorithms</a>, in order to reduce the cost of synchronization among the concurrent threads.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p><p>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. </p> <h3>Random-number generators</h3> <p>The simulation needs to generate <a href="/facts/Random_variables/TwTBXnLT">random variables</a> of various kinds, depending on the system model. This is accomplished by one or more <a href="/facts/Pseudorandom_number_generator/sIrCxIBq">Pseudorandom number generators</a>. 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. </p><p>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 <i>bootstrapping</i> 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 <i>bootstrapping</i> can be contrasted with its use in both <a href="/facts/Bootstrapping_(statistics)/zCHuBeIz">statistics</a> and <a href="/facts/Bootstrapping_(computing)/6dkM4EQv">computing</a>). </p> <h3>Statistics</h3> <p>The simulation typically keeps track of the system's <a href="/facts/Statistic/av21WaMK">statistics</a>, 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 <a href="/facts/Probability_distributions/EpsKKVRu">probability distributions</a>, but rather as averages over <a href="/facts/Replication_(statistics)/3tLkNNFk">replications</a>, that is different runs of the model. <a href="/facts/Confidence_interval/NS8mG5UE">Confidence intervals</a> are usually constructed to help assess the quality of the output. </p> <h3>Ending condition</h3> <p>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". </p> <h3>Three-Phased Approach</h3> <p>Pidd (1998) has proposed 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 (these are called B-events). The third phase is to execute all events that conditionally occur at that time (these are called C-events). 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. </p> <h2 id="common-uses">Common uses</h2> <h3>Diagnosing process issues</h3> <p>Simulation approaches are particularly well equipped to help users diagnose issues in complex environments. The <a href="/facts/Theory_of_constraints/Xz4qagTL">theory of constraints</a> illustrates the importance of understanding bottlenecks in a system. Identifying and removing bottlenecks allows improving processes and the overall system. For instance, in manufacturing enterprises bottlenecks may be created by excess inventory, <a href="/facts/Overproduction/ktdFQ4ps">overproduction</a>, variability in processes and variability in routing or sequencing. By accurately documenting the system with the help of a simulation model it is possible to gain a bird’s eye view of the entire system. </p><p>A working model of a system allows management to understand performance drivers. A simulation can be built to include any number of <a href="/facts/Performance_indicator/qVbntaF8">performance indicators</a> such as worker utilization, on-time delivery rate, scrap rate, cash cycles, and so on. </p> <h3>Hospital applications</h3> <p>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.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> 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. </p> <h3>Lab test performance improvement ideas</h3> <p>Many systems improvement ideas are built on sound principles, proven methodologies (<a href="/facts/Lean_manufacturing/XgQk595B">Lean</a>, <a href="/facts/Six_Sigma/ctasMp3w">Six Sigma</a>, <a href="/facts/Total_quality_management/JFSlCQ9B">TQM</a>, 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. </p> <h3>Evaluating capital investment decisions</h3> <p class="note">See also: <a href="/facts/Monte_Carlo_methods_in_finance/jDb9oq2G">Monte Carlo methods in finance</a>, <a href="/facts/Corporate_finance/ugQCsFBQ">Corporate finance § Capital investment decisions</a>, and <a href="/facts/Corporate_finance/ugQCsFBQ">Corporate finance § Quantifying uncertainty</a></p> <p>Simulation modeling is commonly used to model potential investments. Through modeling investments decision-makers can make informed decisions and evaluate potential alternatives. </p> <h3>Network simulators</h3> <p class="note">Main article: <a href="/facts/Network_simulation/BGzNoDAz">Network simulation</a></p> <p>Discrete event simulation is used in computer network to simulate new protocols, different system architectures (distributed, hierarchical, centralised, P2P) before actual deployment. It is possible to define different evaluation metrics, such as service time, bandwidth, dropped packets, resource consumption, and so on. </p> <h2 id="see-also">See also</h2> <p>System modeling approaches: </p> <ul><li><a href="/facts/Finite-state_machines/GMusWd0a">Finite-state machines</a> and <a href="/facts/Markov_chains/5oP5hntk">Markov chains</a></li> <li><a href="/facts/Stochastic_process/Ng1n1dnB">Stochastic process</a> and a special case, <a href="/facts/Markov_process/5oP5hntk">Markov process</a></li> <li><a href="/facts/Queueing_theory/8NDl56EM">Queueing theory</a> and in particular <a href="/facts/Birth%25E2%2580%2593death_process/ud6IWMxu">birth–death process</a></li> <li><a href="/facts/DEVS/PEfCslfa">Discrete Event System Specification</a></li> <li><a href="/facts/Transaction-level_modeling/hmmfh2zk">Transaction-level modeling</a> (TLM)</li></ul> <p>Computational techniques: </p> <ul><li><a href="/facts/Computer_experiment/7gConHHa">Computer experiment</a></li> <li><a href="/facts/Computer_simulation/Re6o8vzN">Computer simulation</a></li> <li><a href="/facts/Monte_Carlo_method/AkHjY7jc">Monte Carlo method</a></li> <li><a href="/facts/Variance_reduction/EFbuX0tD">Variance reduction</a></li> <li><a href="/facts/Pseudorandom_number_generator/sIrCxIBq">Pseudo-random number generator</a></li></ul> <p>Software: </p> <ul><li><a href="/facts/List_of_computer_simulation_software/EpBVsu7u">List of computer simulation software</a></li> <li><a href="/facts/List_of_discrete_event_simulation_software/asf7998x">List of discrete event simulation software</a></li></ul> <p>Disciplines: </p> <ul><li><a href="/facts/Industrial_engineering/TjInYQeC">Industrial engineering</a></li> <li><a href="/facts/Network_simulation/BGzNoDAz">Network simulation</a></li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Myron H. MacDougall (1987). <a href="https://archive.org/details/simulatingcomput00myro"><i>Simulating Computer Systems: Techniques and Tools</i></a>. MIT Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780262132299.</li> <li>William Delaney; Erminia Vaccari (1988). <i>Dynamic Models and Discrete Event Simulation</i>. Dekker INC.</li> <li>Roger W. McHaney (1991). <i>Computer Simulation: A Practical Perspective</i>. Academic Press.</li> <li>Michael Pidd (1998). <i>Computer simulation in management science – fourth edition</i>. Wiley.</li> <li>A, Alan Pritsker, Jean J. O'Reilly (1999). <i>Simulation with Visual SLAM and AweSim</i>. Wiley.{{cite book}}: CS1 maint: multiple names: authors list (link)</li> <li>Averill M. Law; W. David Kelton (2000). <i>Simulation modeling and analysis – third edition</i>. McGraw–Hill.</li> <li>Bernard P. Zeigler; Herbert Praehofer; Tag Gon Kim (2000). <i>Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems – second edition</i>. Academic Press.</li> <li>Jerry Banks; John Carson; Barry Nelson; David Nicol (2005). <i>Discrete-event system simulation – fourth edition</i>. Pearson.</li> <li>James J. Nutaro (2010). <i>Building software for simulation: theory and algorithms, with applications in C++</i>. Wiley.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Stewart Robinson (2004). Simulation – The practice of model development and use. Wiley. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Matloff, Norm. "Introduction to Discrete-Event Simulation and the SimPy Language" (PDF). Retrieved 24 January 2013. <a href="http://heather.cs.ucdavis.edu/~matloff/156/PLN/DESimIntro.pdf" target="_blank">http://heather.cs.ucdavis.edu/~matloff/156/PLN/DESimIntro.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Park, Hyungwook; Fishwick, Paul A. (2010). "A GPU-Based Application Framework Supporting Fast Discrete-Event Simulation". Simulation. 86 (10): 613–628. doi:10.1177/0037549709340781. ISSN 0037-5497. S2CID 9731021. <a href="http://journals.sagepub.com/doi/10.1177/0037549709340781" target="_blank">http://journals.sagepub.com/doi/10.1177/0037549709340781</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Dannenberg, Roger. "An Introduction to Discrete-Event Simulation". Carnegie Mellon School of Computer Science. Retrieved 2022-03-11. <a href="https://www.cs.cmu.edu/~music/cmsip/readings/intro-discrete-event-sim.html" target="_blank">https://www.cs.cmu.edu/~music/cmsip/readings/intro-discrete-event-sim.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Güneş, Mesut. "Chapter 3: General Principles" (PDF). Freie Universität Berlin. Retrieved 2022-03-11. <a href="https://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/2012_SS/L_19540_Modeling_and_Performance_Analysis_with_Simulation/03.pdf" target="_blank">https://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/2012_SS/L_19540_Modeling_and_Performance_Analysis_with_Simulation/03.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Damerdji, Halim; Glynn, Peter W. (1998). "Limit Theory for Performance Modeling of Future Event Set Algorithms". Management Science. 44 (12): 1709–1722. doi:10.1287/mnsc.44.12.1709. ISSN 0025-1909. JSTOR 2634704. <a href="https://www.jstor.org/stable/2634704" target="_blank">https://www.jstor.org/stable/2634704</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Douglas W. Jones, ed. Implementations of Time, Proceedings of the 18th Winter Simulation Conference, 1986. <a href="/wiki/Douglas_W._Jones" target="_blank">/wiki/Douglas_W._Jones</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Douglas W. Jones, Empirical Comparison of Priority Queue and Event Set Implementations, Communications of the ACM, 29, April 1986, pages 300–311. <a href="/wiki/Douglas_W._Jones" target="_blank">/wiki/Douglas_W._Jones</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Kah Leong Tan and Li-Jin Thng, SNOOPy Calendar Queue, Proceedings of the 32nd Winter Simulation Conference, 2000 <a href="http://portal.acm.org/citation.cfm?id=510378.510453" target="_blank">http://portal.acm.org/citation.cfm?id=510378.510453</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Dickman, Tom; Gupta, Sounak; Wilsey, Philip A. (2013). "Event pool structures for PDES on many-core Beowulf clusters". Proceedings of the 2013 ACM SIGSIM conference on Principles of advanced discrete simulation - SIGSIM-PADS '13. p. 103. doi:10.1145/2486092.2486106. ISBN 9781450319201. S2CID 17572839. <a href="9781450319201" target="_blank">9781450319201</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Furfaro, Angelo; Sacco, Ludovica (2018). "Adaptive Ladder Queue". Proceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '18. pp. 101–104. doi:10.1145/3200921.3200925. ISBN 9781450350921. S2CID 21699926. <a href="9781450350921" target="_blank">9781450350921</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Marotta, Romolo; Ianni, Mauro; Pellegrini, Alessandro; Quaglia, Francesco (2017). "A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms". Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '17. pp. 15–26. doi:10.1145/3064911.3064926. hdl:11573/974295. ISBN 9781450344890. S2CID 30460497. <a href="9781450344890" target="_blank">9781450344890</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Lindén, Jonatan; Jonsson, Bengt (2013). "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention". Proceedings of the 2013 Conference on Principles of Distributed Systems - OPODIS 2013. pp. 206–220. doi:10.1007/978-3-319-03850-6_15. ISBN 9783319038490. <a href="9783319038490" target="_blank">9783319038490</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>John J. Forbus; Daniel Berleant (2022). "Discrete-Event Simulation in Healthcare Settings: A Review". Modelling. 3 (4): 417–433. arXiv:2211.00061. doi:10.3390/modelling3040027. <a href="https://doi.org/10.3390%2Fmodelling3040027" target="_blank">https://doi.org/10.3390%2Fmodelling3040027</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> </ol>