Discrete-event simulation: Difference between revisions

Revision as of 14:52, 24 May 2019

Revision as of 07:07, 8 July 2019

Line 32:

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{{Cite Dickman,book Sounak|doi Gupta= and Philip A. Wilsey, [https://doi.org/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}}</ref><ref>Angelo{{Cite Furfarobook and|doi Ludovica= Sacco, [https://doi.org/10.1145/3200921.3200925|chapter = Adaptive Ladder Queue:|title Achieving O(1) Amortized Access Time in Practice],= Proceedings of the 2018 ACM SIGSIM conferenceConference on Principles of advancedAdvanced discreteDiscrete simulationSimulation - SIGSIM-PADS '18|pages = 101–104|year = 2018|last1 = Furfaro|first1 = Angelo|last2 = Sacco|first2 = Ludovica|isbn = 9781450350921}}</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.