408:
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.
349:
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
65:, 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. Because not every time slice has to be simulated, a next-event time simulation can typically run faster than a corresponding incremental time simulation.
79:
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,
328:
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,
407:
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
241:
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
445:
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
502:
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
348:
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
398:
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
353:
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
261:
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
446:
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.
296:
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. Various priority queue implementations have been studied in the context of discrete event simulation; alternatives studied have included
425:
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,
273:
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.
284:
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.
430:, 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.
378:, 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
54:
in the system. 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
488:
Simulation modeling is commonly used to model potential investments. Through modeling investments decision-makers can make informed decisions and evaluate potential alternatives.
229:
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
952:
Marotta, Romolo; Ianni, Mauro; Pellegrini, Alessandro; Quaglia, Francesco (2017). "A Conflict-Resilient Lock-Free
Calendar Queue for Scalable Share-Everything PDES Platforms".
466:, 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.
745:
1146:
345:. 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.
262:
parametrized, in which case, the event description also contains parameters to the event code. The event list is also referred to as the
723:
593:
433:
A working model of a system allows management to understand performance drivers. A simulation can be built to include any number of
17:
588:
146:
follow-up event is scheduled to happen without any delay, such that the newly arrived customer will be served immediately.
542:
870:
Dickman, Tom; Gupta, Sounak; Wilsey, Philip A. (2013). "Event pool structures for PDES on many-core
Beowulf clusters".
310:
1165:
Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems – second edition
1094:
1018:
1001:
Lindén, Jonatan; Jonsson, Bengt (2013). "A Skiplist-Based
Concurrent Priority Queue with Minimal Memory Contention".
977:
928:
887:
479:
421:
Simulation approaches are particularly well equipped to help users diagnose issues in complex environments. The
96:, such as customers arriving at a bank teller to be served by a clerk. In this example, the system objects are
1199:
475:
954:
Proceedings of the 2017 ACM SIGSIM Conference on
Principles of Advanced Discrete Simulation - SIGSIM-PADS '17
913:
Proceedings of the 2018 ACM SIGSIM Conference on
Principles of Advanced Discrete Simulation - SIGSIM-PADS '18
872:
Proceedings of the 2013 ACM SIGSIM conference on
Principles of advanced discrete simulation - SIGSIM-PADS '13
718:
578:
483:
342:
1204:
753:
547:
359:
379:
363:
463:
383:
51:
537:
251:
646:
603:
322:
257:
The simulation maintains at least one list of simulation events. This is sometimes called the
81:
515:
434:
422:
126:. Each of these events comes with its own dynamics defined by the following event routines:
73:
69:
280:
simulation engines based on instantaneous events have just one current event. In contrast,
671:
314:
61:
In addition to next-event time progression, there is also an alternative approach, called
8:
563:
558:
387:
184:
follow-up event is scheduled to happen without any delay. Otherwise, the state variable
1140:
1047:
983:
934:
893:
803:
699:
608:
573:
568:
524:
497:
455:
437:
such as worker utilization, on-time delivery rate, scrap rate, cash cycles, and so on.
318:
281:
47:
857:
824:
1090:
1083:
1014:
1003:
Proceedings of the 2013 Conference on
Principles of Distributed Systems - OPODIS 2013
973:
924:
883:
795:
691:
341:
of various kinds, depending on the system model. This is accomplished by one or more
72:
in which the system state is changed continuously over time on the basis of a set of
987:
938:
897:
454:
Many systems improvement ideas are built on sound principles, proven methodologies (
92:
A common exercise in learning how to build discrete-event simulations is to model a
1057:
1006:
965:
957:
916:
875:
836:
820:
787:
703:
683:
338:
176:
is decremented by 1 (representing the customer's departure). If the state variable
1183:
Building software for simulation: theory and algorithms, with applications in C++
1010:
533:
277:
193:
93:
50:
in time. Each event occurs at a particular instant in time and marks a change of
528:
427:
325:, in order to reduce the cost of synchronization among the concurrent threads.
306:
289:
1162:
1193:
1171:
1062:
1035:
799:
695:
687:
672:"A GPU-Based Application Framework Supporting Fast Discrete-Event Simulation"
519:
230:
43:
961:
920:
879:
791:
969:
840:
807:
775:
298:
197:
1130:
776:"Limit Theory for Performance Modeling of Future Event Set Algorithms"
459:
375:
302:
841:
Empirical
Comparison of Priority Queue and Event Set Implementations
250:"Future event list" redirects here. For lists of future events, see
161:
follow-up event is scheduled with a delay (obtained from sampling a
1052:
911:
Furfaro, Angelo; Sacco, Ludovica (2018). "Adaptive Ladder Queue".
647:"Introduction to Discrete-Event Simulation and the SimPy Language"
390:
are usually constructed to help assess the quality of the output.
329:
where s is a number generated from the SERVICE-TIME distribution.
293:
39:
1103:
1153:
1033:
951:
827:, Proceedings of the 18th Winter Simulation Conference, 1986.
321:
CPUs, the pending event set can be implemented by relying on
1172:
Jerry Banks; John Carson; Barry Nelson; David Nicol (2005).
1036:"Discrete-Event Simulation in Healthcare Settings: A Review"
860:, Proceedings of the 32nd Winter Simulation Conference, 2000
1163:
Bernard P. Zeigler; Herbert
Praehofer; Tag Gon Kim (2000).
1124:
Computer simulation in management science – fourth edition
469:
449:
631:
Simulation – The practice of model development and use
480:
Corporate finance § Capital investment decisions
374:
The simulation typically keeps track of the system's
1080:
196:that need to be characterized to model this system
1082:
869:
288:The pending event set is typically organized as a
76:defining the rates of change for state variables.
1174:Discrete-event system simulation – fourth edition
1085:Simulating Computer Systems: Techniques and Tools
233:whose value can change whenever an event occurs.
1191:
1156:Simulation modeling and analysis – third edition
1112:
627:
484:Corporate finance § Quantifying uncertainty
1180:
138:is incremented by 1, and if the state variable
719:"An Introduction to Discrete-Event Simulation"
1000:
773:
1145:: CS1 maint: multiple names: authors list (
1121:
1115:Computer Simulation: A Practical Perspective
1106:Dynamic Models and Discrete Event Simulation
910:
669:
416:
1131:A, Alan Pritsker, Jean J. O'Reilly (1999).
670:Park, Hyungwook; Fishwick, Paul A. (2010).
332:
724:Carnegie Mellon School of Computer Science
594:List of discrete event simulation software
1104:William Delaney; Erminia Vaccari (1988).
1061:
1051:
774:Damerdji, Halim; Glynn, Peter W. (1998).
1154:Averill M. Law; W. David Kelton (2000).
1034:John J. Forbus; Daniel Berleant (2022).
440:
402:
470:Evaluating capital investment decisions
386:, that is different runs of the model.
358:can be contrasted with its use in both
14:
1192:
1133:Simulation with Visual SLAM and AweSim
716:
638:
450:Lab test performance improvement ideas
491:
589:List of computer simulation software
644:
543:Discrete Event System Specification
393:
24:
1074:
25:
1216:
743:
337:The simulation needs to generate
172:event occurs, the state variable
153:event occurs, the state variable
134:event occurs, the state variable
68:Both forms of DES contrast with
1027:
994:
945:
904:
863:
856:Kah Leong Tan and Li-Jin Thng,
746:"Chapter 3: General Principles"
850:
845:Communications of the ACM, 29,
830:
814:
767:
737:
710:
663:
621:
579:Pseudo-random number generator
476:Monte Carlo methods in finance
411:
382:, but rather as averages over
343:Pseudorandom number generators
245:
180:is still greater than zero, a
108:, while the system events are
13:
1:
614:
369:
219:
142:has the value "available", a
1081:Myron H. MacDougall (1987).
1011:10.1007/978-3-319-03850-6_15
511:System modeling approaches:
63:incremental time progression
38:) models the operation of a
7:
506:
311:massively-parallel machines
84:used in operating systems.
56:next-event time progression
10:
1221:
847:April 1986, pages 300–311.
554:Computational techniques:
548:Transaction-level modeling
495:
473:
249:
87:
1113:Roger W. McHaney (1991).
628:Stewart Robinson (2004).
417:Diagnosing process issues
380:probability distributions
242:the simulation proceeds.
32:discrete-event simulation
18:Discrete event simulation
1181:James J. Nutaro (2010).
1063:10.3390/modelling3040027
754:Freie Universität Berlin
688:10.1177/0037549709340781
503:consumption, and so on.
333:Random-number generators
309:, and ladder queues. On
236:
224:
962:10.1145/3064911.3064926
921:10.1145/3200921.3200925
880:10.1145/2486092.2486106
825:Implementations of Time
792:10.1287/mnsc.44.12.1709
323:non-blocking algorithms
252:Timelines of the future
157:is set to "busy" and a
604:Industrial engineering
435:performance indicators
188:is set to "available".
74:differential equations
1200:Stochastic simulation
1122:Michael Pidd (1998).
858:SNOOPy Calendar Queue
516:Finite-state machines
441:Hospital applications
423:theory of constraints
403:Three-Phased Approach
70:continuous simulation
1005:. pp. 206–220.
915:. pp. 101–104.
527:and a special case,
388:Confidence intervals
717:Dannenberg, Roger.
564:Computer simulation
559:Computer experiment
538:birth–death process
1205:Events (computing)
956:. pp. 15–26.
780:Management Science
609:Network simulation
574:Variance reduction
569:Monte Carlo method
536:and in particular
525:Stochastic process
498:Network simulation
492:Network simulators
212:for the delays of
48:sequence of events
27:Type of simulation
1167:. Academic Press.
1117:. Academic Press.
786:(12): 1709–1722.
264:future event list
259:pending event set
202:interarrival-time
165:random variable).
16:(Redirected from
1212:
1186:
1177:
1168:
1159:
1150:
1144:
1136:
1127:
1118:
1109:
1100:
1088:
1068:
1067:
1065:
1055:
1031:
1025:
1024:
998:
992:
991:
949:
943:
942:
908:
902:
901:
867:
861:
854:
848:
837:Douglas W. Jones
834:
828:
821:Douglas W. Jones
818:
812:
811:
771:
765:
764:
762:
761:
750:
741:
735:
734:
732:
731:
714:
708:
707:
667:
661:
660:
658:
656:
651:
642:
636:
635:
625:
394:Ending condition
339:random variables
268:future event set
206:Customer-Arrival
194:random variables
132:Customer-Arrival
111:Customer-Arrival
82:scheduling queue
21:
1220:
1219:
1215:
1214:
1213:
1211:
1210:
1209:
1190:
1189:
1138:
1137:
1097:
1077:
1075:Further reading
1072:
1071:
1032:
1028:
1021:
999:
995:
980:
950:
946:
931:
909:
905:
890:
874:. p. 103.
868:
864:
855:
851:
835:
831:
819:
815:
772:
768:
759:
757:
748:
742:
738:
729:
727:
715:
711:
682:(10): 613–628.
668:
664:
654:
652:
649:
645:Matloff, Norm.
643:
639:
626:
622:
617:
534:Queueing theory
509:
500:
494:
486:
472:
452:
443:
419:
414:
405:
396:
372:
335:
307:calendar queues
278:Single-threaded
255:
248:
239:
227:
222:
208:events and the
94:queueing system
90:
28:
23:
22:
15:
12:
11:
5:
1218:
1208:
1207:
1202:
1188:
1187:
1178:
1169:
1160:
1158:. McGraw–Hill.
1151:
1128:
1119:
1110:
1101:
1095:
1076:
1073:
1070:
1069:
1046:(4): 417–433.
1026:
1019:
993:
978:
944:
929:
903:
888:
862:
849:
829:
813:
766:
744:GĂĽneĹź, Mesut.
736:
709:
662:
637:
619:
618:
616:
613:
612:
611:
606:
597:
596:
591:
582:
581:
576:
571:
566:
561:
552:
551:
545:
540:
531:
529:Markov process
522:
508:
505:
496:Main article:
493:
490:
471:
468:
451:
448:
442:
439:
428:overproduction
418:
415:
413:
410:
404:
401:
395:
392:
371:
368:
334:
331:
290:priority queue
282:multi-threaded
247:
244:
238:
235:
226:
223:
221:
218:
204:for recurrent
198:stochastically
190:
189:
166:
147:
89:
86:
26:
9:
6:
4:
3:
2:
1217:
1206:
1203:
1201:
1198:
1197:
1195:
1184:
1179:
1175:
1170:
1166:
1161:
1157:
1152:
1148:
1142:
1134:
1129:
1125:
1120:
1116:
1111:
1108:. Dekker INC.
1107:
1102:
1098:
1096:9780262132299
1092:
1089:. MIT Press.
1087:
1086:
1079:
1078:
1064:
1059:
1054:
1049:
1045:
1041:
1037:
1030:
1022:
1020:9783319038490
1016:
1012:
1008:
1004:
997:
989:
985:
981:
979:9781450344890
975:
971:
967:
963:
959:
955:
948:
940:
936:
932:
930:9781450350921
926:
922:
918:
914:
907:
899:
895:
891:
889:9781450319201
885:
881:
877:
873:
866:
859:
853:
846:
842:
838:
833:
826:
822:
817:
809:
805:
801:
797:
793:
789:
785:
781:
777:
770:
756:
755:
747:
740:
726:
725:
720:
713:
705:
701:
697:
693:
689:
685:
681:
677:
673:
666:
648:
641:
633:
630:
624:
620:
610:
607:
605:
602:
601:
600:
599:Disciplines:
595:
592:
590:
587:
586:
585:
580:
577:
575:
572:
570:
567:
565:
562:
560:
557:
556:
555:
549:
546:
544:
541:
539:
535:
532:
530:
526:
523:
521:
520:Markov chains
517:
514:
513:
512:
504:
499:
489:
485:
481:
477:
467:
465:
461:
457:
447:
438:
436:
431:
429:
424:
409:
400:
391:
389:
385:
381:
377:
367:
365:
361:
357:
356:bootstrapping
352:
351:bootstrapping
346:
344:
340:
330:
326:
324:
320:
316:
312:
308:
304:
300:
295:
291:
286:
283:
279:
275:
271:
269:
265:
260:
253:
243:
234:
232:
231:step function
217:
215:
211:
207:
203:
199:
195:
187:
186:teller-status
183:
182:Service-Start
179:
175:
171:
167:
164:
160:
156:
155:teller-status
152:
151:Service-Start
148:
145:
144:Service-Start
141:
140:teller-status
137:
133:
129:
128:
127:
125:
124:
119:
118:
117:Service-Start
113:
112:
107:
106:
101:
100:
95:
85:
83:
77:
75:
71:
66:
64:
59:
57:
53:
49:
45:
41:
37:
33:
19:
1182:
1173:
1164:
1155:
1132:
1123:
1114:
1105:
1084:
1043:
1039:
1029:
1002:
996:
970:11573/974295
953:
947:
912:
906:
871:
865:
852:
844:
832:
816:
783:
779:
769:
758:. Retrieved
752:
739:
728:. Retrieved
722:
712:
679:
675:
665:
653:. Retrieved
640:
632:
629:
623:
598:
583:
553:
510:
501:
487:
453:
444:
432:
420:
406:
397:
384:replications
373:
355:
350:
347:
336:
327:
287:
276:
272:
267:
263:
258:
256:
240:
228:
213:
210:service-time
209:
205:
201:
191:
185:
181:
178:queue-length
177:
174:queue-length
173:
169:
163:service-time
162:
158:
154:
150:
143:
139:
136:queue-length
135:
131:
122:
121:
116:
115:
110:
109:
104:
103:
98:
97:
91:
78:
67:
62:
60:
55:
35:
31:
29:
412:Common uses
299:splay trees
246:Events list
214:Service-End
170:Service-End
159:Service-End
123:Service-End
1194:Categories
1176:. Pearson.
1053:2211.00061
760:2022-03-11
730:2022-03-11
676:Simulation
655:24 January
615:References
584:Software:
474:See also:
399:value x".
376:statistics
370:Statistics
360:statistics
315:multi-core
313:, such as
303:skip lists
220:Components
1141:cite book
1040:Modelling
800:0025-1909
696:0037-5497
460:Six Sigma
364:computing
319:many-core
266:(FEL) or
216:events.
1185:. Wiley.
1135:. Wiley.
1126:. Wiley.
988:30460497
939:21699926
898:17572839
634:. Wiley.
507:See also
200:are the
99:Customer
80:and the
44:discrete
823:, ed.
808:2634704
704:9731021
270:(FES).
168:When a
149:When a
130:When a
88:Example
1093:
1017:
986:
976:
937:
927:
896:
886:
806:
798:
702:
694:
482:, and
294:sorted
105:Teller
42:as a (
40:system
1048:arXiv
984:S2CID
935:S2CID
894:S2CID
804:JSTOR
749:(PDF)
700:S2CID
650:(PDF)
550:(TLM)
237:Clock
225:State
52:state
1147:link
1091:ISBN
1015:ISBN
974:ISBN
925:ISBN
884:ISBN
796:ISSN
692:ISSN
657:2013
518:and
456:Lean
362:and
192:The
120:and
102:and
1058:doi
1007:doi
966:hdl
958:doi
917:doi
876:doi
788:doi
684:doi
464:TQM
366:).
317:or
36:DES
1196::
1143:}}
1139:{{
1056:.
1042:.
1038:.
1013:.
982:.
972:.
964:.
933:.
923:.
892:.
882:.
843:,
839:,
802:.
794:.
784:44
782:.
778:.
751:.
721:.
698:.
690:.
680:86
678:.
674:.
478:,
462:,
458:,
305:,
301:,
292:,
114:,
58:.
46:)
30:A
1149:)
1099:.
1066:.
1060::
1050::
1044:3
1023:.
1009::
990:.
968::
960::
941:.
919::
900:.
878::
810:.
790::
763:.
733:.
706:.
686::
659:.
254:.
34:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.