Discrete-event simulation: Difference between revisions

Revision as of 14:47, 24 May 2019

Latest revision as of 02:30, 25 May 2025

(48 intermediate revisions by 31 users not shown)

Line 1:

{{Short description|Type of simulation}}

A '''discrete-event simulation''' ('''DES''') models the operation of a [[system]] as a ([[discrete time|discrete]]) [[sequence of events]] in time. Each event occurs at a particular instant in time and marks a change of [[State (computer science)|state]] in the system.<ref>{{cite book|title=''Simulation – The practice of model development and use''|author=Stewart Robinson|publisher=Wiley|year=2004}}</ref> Between consecutive events, no change in the system is assumed to occur; thus the simulation time can directly jump to the occurrence time of the next event, which is called '''next-event time progression'''.

In addition to next-event time progression, there is also an alternative approach, called '''fixed-incrementincremental time progression''', where time is broken up into small time slices and the system state is updated according to the set of events/activities happening in the time slice.<ref name="matloff">{{cite web|last=Matloff|first=Norm|title=Introduction to Discrete-Event Simulation and the SimPy Language|url=http://heather.cs.ucdavis.edu/~matloff/156/PLN/DESimIntro.pdf|accessdateaccess-date=24 January 2013}}</ref> Because not every time slice has to be simulated, a next-event time simulation can typically run much faster than a corresponding fixed-incrementincremental time simulation.

Both forms of DES contrast with [[continuous simulation]] in which the system state is changed continuously over time on the basis of a set of [[Differential equation|differential equations]] defining the rates of change offor state variables.

In the past, these three types of simulation have also been referred to, respectively, as: event scheduling simulation, activity scanning simulation, and process interaction simulation. It can also be noted that there are similarities between the implementation of the event queue in event scheduling, and the [[Scheduling (computing)|scheduling queue]] used in operating systems.

A more recent method is the three-phased approach to discrete event simulation (Pidd, 1998). 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.

== Example ==

A common exercise in learning how to build discrete-event simulations is to model a [[Queueing theory|queuequeueing system]], such as customers arriving at a bank teller to be served by a tellerclerk. In this example, the system entitiesobjects are '''Customer-queue''Customer' and '''Tellers'''. The system events are '''Customer-Arrival''' and '''Customer-Departure''Teller'. (The event of '''Teller-Begins-Service''', can be part ofwhile the logic of the arrival and departure events.) The system states, which are changed by these events, are '''Number-of-Customers-in-the-Queue''Customer-Arrival' (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 [[stochastic]]ally are '''CustomerService-Interarrival-TimeStart''''' and '''Teller-''Service-TimeEnd'''''. An agent-based framework for performance modelingEach of anthese optimisticevents parallelcomes discretewith eventits simulatorown isdynamics anotherdefined exampleby forthe a discretefollowing event simulation.<ref>{{cite journal |author1=Aditya Kurve |author2=Khashayar Kotobi |author3=George Kesidis |title=An agent-based framework for performance modeling of an optimistic parallel discrete event simulator | doi=10.1186/2194-3206-1-12 |volume=1 |journal=Complex Adaptive Systems Modeling |pages=12|year=2013routines: }}</ref>

# When a ''Customer-Arrival'' event occurs, the state variable ''queue-length'' is incremented by 1, and if the state variable ''teller-status'' has the value "available", a ''Service-Start'' follow-up event is scheduled to happen without any delay, such that the newly arrived customer will be served immediately.

==Components==

# When a ''Service-Start'' event occurs, the state variable ''teller-status'' is set to "busy" and a ''Service-End'' follow-up event is scheduled with a delay (obtained from sampling a ''service-time'' random variable).

In addition to the logic of what happens when system events occur, discrete event simulations include the following:

# When a ''Service-End'' event occurs, the state variable ''queue-length'' is decremented by 1 (representing the customer's departure). If the state variable ''queue-length'' is still greater than zero, a ''Service-Start'' follow-up event is scheduled to happen without any delay. Otherwise, the state variable ''teller-status'' is set to "available".

Priority queue, Animation event handler, and Time re-normalization handler (as simulation runs, time variables lose precision. After a while all time variables should be re-normalized by subtracting the last processed event time).

The [[random variable]]s that need to be characterized to model this system [[stochastic]]ally are the ''interarrival-time'' for recurrent ''Customer-Arrival'' events and the ''service-time'' for the delays of ''Service-End'' events.

==Components==

===State===

Line 23 ⟶ 27:

===Events list===

{{redirect|Future event list|lists of future events|Timelines of the future}}

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.{{cn|date=March 2022}} The event list is also referred to as the ''future event list'' (FEL) or ''future event set'' (FES).<ref>{{Cite journal |last1=Park |first1=Hyungwook |last2=Fishwick |first2=Paul A. |date=2010|title=A GPU-Based Application Framework Supporting Fast Discrete-Event Simulation |url=http://journals.sagepub.com/doi/10.1177/0037549709340781 |journal=Simulation |language=en |volume=86 |issue=10 |pages=613–628 |doi=10.1177/0037549709340781 |s2cid=9731021 |issn=0037-5497|url-access=subscription }}</ref><ref>{{Cite web |last=Dannenberg |first=Roger |title=An Introduction to Discrete-Event Simulation |url=https://www.cs.cmu.edu/~music/cmsip/readings/intro-discrete-event-sim.html |access-date=2022-03-11 |website=[[Carnegie Mellon School of Computer Science]]}}</ref><ref>{{Cite web |last=Güneş |first=Mesut |title=Chapter 3: General Principles |url=https://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/2012_SS/L_19540_Modeling_and_Performance_Analysis_with_Simulation/03.pdf |access-date=2022-03-11 |website=[[Freie Universität Berlin]]}}</ref><ref>{{Cite journal |last1=Damerdji |first1=Halim |last2=Glynn |first2=Peter W. |date=1998 |title=Limit Theory for Performance Modeling of Future Event Set Algorithms |url=https://www.jstor.org/stable/2634704 |journal=Management Science |volume=44 |issue=12 |pages=1709–1722 |doi=10.1287/mnsc.44.12.1709 |jstor=2634704 |issn=0025-1909|url-access=subscription }}</ref>

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.{{cn|date=March 2022}}

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.

[[Single-threaded]] simulation engines based on instantaneous events have just one current event. In contrast, [[Thread (computing)|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.{{cn|date=March 2022}}

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.

The pending event set is typically organized as a [[priority queue]], [[Sorting|sorted]] by event time.<ref>[[Douglas W. Jones]], ed. [http://portal.acm.org/citation.cfm?id=318242.318467 Implementations of Time], Proceedings of the 18th Winter Simulation Conference, 1986.</ref> 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;<ref>[[Douglas W. Jones]], [http://doi.acm.org/10.1145/5684.5686 Empirical Comparison of Priority Queue and Event Set Implementations], ''Communications of the ACM, 29,'' April 1986, pages 300–311.</ref>; alternatives studied have included [[splay tree]]s, [[skip list]]s, [[calendar queue]]s,<ref>Kah Leong Tan and Li-Jin Thng, [http://portal.acm.org/citation.cfm?id=510378.510453 SNOOPy Calendar Queue], Proceedings of the 32nd Winter Simulation Conference, 2000</ref> and ladder queues.<ref>{{Cite book |doi = 10.1145/2486092.2486106|chapter = Event pool structures for PDES on many-core Beowulf clusters|title = Proceedings of the 2013 ACM SIGSIM conference on Principles of advanced discrete simulation - SIGSIM-PADS '13|pages = 103|year = 2013|last1 = Dickman|first1 = Tom|last2 = Gupta|first2 = Sounak|last3 = Wilsey|first3 = Philip A.|isbn = 9781450319201|s2cid = 17572839}}</ref><ref>{{Cite book |doi = 10.1145/3200921.3200925|chapter = Adaptive Ladder Queue|title = Proceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '18|pages = 101–104|year = 2018|last1 = Furfaro|first1 = Angelo|last2 = Sacco|first2 = Ludovica|isbn = 9781450350921|s2cid = 21699926}}</ref>

[[Single-threaded]] simulation engines based on instantaneous events have just one current event. In contrast, [[Thread (computing)|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.

On [[Massively parallel processor array|massively-parallel machines]], such as [[Multi-core processor|multi-core]] or [[Manycore processor|many-core]] CPUs, the pending event set can be implemented by relying on [[Non-blocking algorithm|non-blocking algorithms]], in order to reduce the cost of synchronization among the concurrent threads.<ref>{{Cite book |doi = 10.1145/3064911.3064926|chapter = A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms|title = Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '17|pages = 15–26|year = 2017|last1 = Marotta|first1 = Romolo|last2 = Ianni|first2 = Mauro|last3 = Pellegrini|first3 = Alessandro|last4 = Quaglia|first4 = Francesco|hdl = 11573/974295|isbn = 9781450344890|s2cid = 30460497}}</ref><ref>{{Cite book |doi = 10.1007/978-3-319-03850-6_15|chapter = A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention|title = Proceedings of the 2013 Conference on Principles of Distributed Systems - OPODIS 2013|pages = 206–220|year = 2013|last1 = Lindén|first1 = Jonatan|last2 = Jonsson|first2 = Bengt|isbn = 9783319038490}}</ref>

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.{{cn|date=March 2022}}

The pending event set is typically organized as a [[priority queue]], [[Sorting|sorted]] by event time.<ref>[[Douglas W. Jones]], ed. [http://portal.acm.org/citation.cfm?id=318242.318467 Implementations of Time], Proceedings of the 18th Winter Simulation Conference, 1986.</ref> 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<ref>[[Douglas W. Jones]], [http://doi.acm.org/10.1145/5684.5686 Empirical Comparison of Priority Queue and Event Set Implementations], ''Communications of the ACM, 29,'' April 1986, pages 300–311.</ref>; alternatives studied have included [[splay tree]]s, [[skip list]]s, [[calendar queue]]s,<ref>Kah Leong Tan and Li-Jin Thng, [http://portal.acm.org/citation.cfm?id=510378.510453 SNOOPy Calendar Queue], Proceedings of the 32nd Winter Simulation Conference, 2000</ref> and ladder queues.

<ref>Tom Dickman, Sounak Gupta and Philip A. Wilsey, [https://doi.org/10.1145/2486092.2486106 Event pool structures for PDES on many-core Beowulf clusters], Proceedings of the 2013 ACM SIGSIM conference on Principles of advanced discrete simulation</ref><ref>Angelo Furfaro and Ludovica Sacco, [https://doi.org/10.1145/3200921.3200925 Adaptive Ladder Queue: Achieving O(1) Amortized Access Time in Practice], Proceedings of the 2018 ACM SIGSIM conference on Principles of advanced discrete simulation</ref>

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===

Line 52 ⟶ 53:

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".

===Three-Phased Approach===

==Simulation engine logic==

APidd more(1998) recenthas method isproposed the three-phased approach to discrete event simulation (Pidd, 1998). 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.

== Common uses ==

The main loop of a discrete-event 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 [[Theorytheory of Constraintsconstraints]] 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, [[overproduction]], 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.

A working model of a system allows management to understand performance drivers. A simulation can be built to include any number of [[performance indicator]]s 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.<ref>{{cite journal |author1=John J. Forbus |author2=Daniel Berleant |title=Discrete-Event Simulation in Healthcare Settings: A Review | doi=10.3390/modelling3040027 |volume=3 |journal=Modelling |pages=417–433|year=2022 |issue=4 |doi-access=free |arxiv=2211.00061 }}</ref> 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.

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===

Line 86 ⟶ 70:

===Evaluating capital investment decisions===

:''{{See also: [[|Monte Carlo methods in finance]]; [[|Corporate finance#Capital investment decisions|Corporate finance #Capital investment decisions]] and [[Corporate finance#Quantifying uncertainty|#Quantifying uncertainty]].''}}

Simulation modeling is commonly used to model potential investments. Through modeling investments decision-makers can make informed decisions and evaluate potential alternatives.

Line 92 ⟶ 76:

===Network simulators===

{{Main|Network simulation}}

Discrete event simulation is used in computer network to simulate new protocols for, different networksystem trafficarchitectures scenarios(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.

{{#section:Network_simulation|transclusionLabelG20170307T1400GMT1}}

== See also ==

System modeling approaches:

* [[Finite-state machines]] and [[Markov chains]]

* [[Stochastic process]] and a special case, [[Markov process]]

* [[Queueing theory]] and in particular [[birth-deathbirth–death process]]

* [[DEVS|Discrete Event System Specification]]

* [[Transaction-level modeling]] (TLM)

Computational techniques:

Line 108 ⟶ 90:

* [[Monte Carlo method]]

* [[Variance reduction]]

* [[PseudoPseudorandom number generator|Pseudo-random number generator]]

Software:

* [[List of computer simulation software]]

Line 121 ⟶ 103:

==Further reading==

*{{cite book|title=Simulating Computer Systems: Techniques and Tools|url=https://archive.org/details/simulatingcomput00myro|url-access=registration|author=Myron H. MacDougall|publisher= MIT Press| year=1987|isbn=9780262132299 }}

*{{cite book|title=Dynamic Models and Discrete Event Simulation|author1=William Delaney |author2=Erminia Vaccari |publisher= Dekker INC| year=1988}}

*{{cite book|title=Computer Simulation: A Practical Perspective|author=Roger W. McHaney|publisher=Academic Press|year=1991}}

Line 131 ⟶ 113:

*{{cite book|title=Building software for simulation: theory and algorithms, with applications in C++|author=James J. Nutaro|publisher=Wiley|year=2010}}

[[Category:ScientificStochastic modelingsimulation]]

{{DEFAULTSORT:Discrete Event Simulation}}

[[Category:Simulation]]

[[Category:Scientific modeling]]

[[Category:Events (computing)]]