Discrete-event simulation
View on WikipediaA discrete-event simulation (DES) models the operation of a system as a (discrete) sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in the system.[1] 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 incremental 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.[2] Because not every time slice has to be simulated, a next-event time simulation can typically run faster than a corresponding incremental 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 equations defining the rates of change for 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 queue used in operating systems.
Example
[edit]A common exercise in learning how to build discrete-event simulations is to model a queueing system, such as customers arriving at a bank teller to be served by a clerk. In this example, the system objects are customer and teller, while the system events are customer-arrival, service-start and service-end. Each of these events comes with its own dynamics defined by the following event routines:
- 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.
- 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).
- 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".
The random variables that need to be characterized to model this system stochastically are the interarrival-time for recurrent customer-arrival events and the service-time for the delays of service-end events.
Components
[edit]State
[edit]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 step function whose value can change whenever an event occurs.
Clock
[edit]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.
Events list
[edit]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.[citation needed] The event list is also referred to as the future event list (FEL) or future event set (FES).[3][4][5][6]
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.[citation needed]
Single-threaded simulation engines based on instantaneous events have just one current event. In contrast, 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.[citation needed]
The pending event set is typically organized as a priority queue, sorted by event time.[7] 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;[8] alternatives studied have included splay trees, skip lists, calendar queues,[9] and ladder queues.[10][11] On massively-parallel machines, such as multi-core or many-core CPUs, the pending event set can be implemented by relying on non-blocking algorithms, in order to reduce the cost of synchronization among the concurrent threads.[12][13]
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.[citation needed]
Random-number generators
[edit]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 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.
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 bootstrapping 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 bootstrapping can be contrasted with its use in both statistics and computing).
Statistics
[edit]The simulation typically keeps track of the system's statistics, 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 probability distributions, but rather as averages over replications, that is different runs of the model. Confidence intervals are usually constructed to help assess the quality of the output.
Ending condition
[edit]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
[edit]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.
Common uses
[edit]Diagnosing process issues
[edit]Simulation approaches are particularly well equipped to help users diagnose issues in complex environments. The theory of constraints 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 indicators such as worker utilization, on-time delivery rate, scrap rate, cash cycles, and so on.
Hospital applications
[edit]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.[14] 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
[edit]Many systems improvement ideas are built on sound principles, proven methodologies (Lean, Six Sigma, TQM, 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.
Evaluating capital investment decisions
[edit]Simulation modeling is commonly used to model potential investments. Through modeling investments decision-makers can make informed decisions and evaluate potential alternatives.
Network simulators
[edit]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.
See also
[edit]System modeling approaches:
- Finite-state machines and Markov chains
- Stochastic process and a special case, Markov process
- Queueing theory and in particular birth–death process
- Discrete event system specification
- Transaction-level modeling (TLM)
Computational techniques:
- Computer experiment
- Computer simulation
- Monte Carlo method
- Variance reduction
- Pseudo-random number generator
Software:
Disciplines:
References
[edit]- ^ Stewart Robinson (2004). Simulation – The practice of model development and use. Wiley.
- ^ Matloff, Norm. "Introduction to Discrete-Event Simulation and the SimPy Language" (PDF). Retrieved 24 January 2013.
- ^ 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.
- ^ Dannenberg, Roger. "An Introduction to Discrete-Event Simulation". Carnegie Mellon School of Computer Science. Retrieved 2022-03-11.
- ^ Güneş, Mesut. "Chapter 3: General Principles" (PDF). Freie Universität Berlin. Retrieved 2022-03-11.
- ^ 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.
- ^ Douglas W. Jones, ed. Implementations of Time, Proceedings of the 18th Winter Simulation Conference, 1986.
- ^ Douglas W. Jones, Empirical Comparison of Priority Queue and Event Set Implementations, Communications of the ACM, 29, April 1986, pages 300–311.
- ^ Kah Leong Tan and Li-Jin Thng, SNOOPy Calendar Queue, Proceedings of the 32nd Winter Simulation Conference, 2000
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
Further reading
[edit]- Myron H. MacDougall (1987). Simulating Computer Systems: Techniques and Tools. MIT Press. ISBN 9780262132299.
- William Delaney; Erminia Vaccari (1988). Dynamic Models and Discrete Event Simulation. Dekker INC.
- Roger W. McHaney (1991). Computer Simulation: A Practical Perspective. Academic Press.
- Michael Pidd (1998). Computer simulation in management science – fourth edition. Wiley.
- A, Alan Pritsker, Jean J. O'Reilly (1999). Simulation with Visual SLAM and AweSim. Wiley.
{{cite book}}: CS1 maint: multiple names: authors list (link) - Averill M. Law; W. David Kelton (2000). Simulation modeling and analysis – third edition. McGraw–Hill.
- Bernard P. Zeigler; Herbert Praehofer; Tag Gon Kim (2000). Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems – second edition. Academic Press.
- Jerry Banks; John Carson; Barry Nelson; David Nicol (2005). Discrete-event system simulation – fourth edition. Pearson.
- James J. Nutaro (2010). Building software for simulation: theory and algorithms, with applications in C++. Wiley.
Discrete-event simulation
View on GrokipediaIllustrative Example
A simple example of DES is simulating a single-server queue, such as a bank teller line. Events include customer arrivals and service completions. Upon arrival, if the server is free, service begins immediately; otherwise, the customer joins the queue. The simulation clock jumps to the next event time (e.g., next arrival or service end), updating the queue length and server status accordingly. This models waiting times and queue buildup without simulating idle moments between events.[2]Introduction
Definition and Principles
Discrete-event simulation is a computational modeling technique used to represent the behavior of complex systems where the state variables change instantaneously only at discrete points in time, known as events, rather than evolving continuously.[5] This approach generates an artificial history of the system by advancing a simulation clock directly from one event to the next, capturing snapshots of the system state at these transition points to estimate performance measures such as throughput or queue lengths.[5] It is particularly suited for stochastic, dynamic systems like manufacturing lines or communication networks, where events (e.g., arrivals or service completions) drive all significant changes.[6] The core principles of discrete-event simulation revolve around event-driven dynamics, where the system's evolution is governed by a schedule of future events managed in chronological order. Upon processing an event, the system state updates instantaneously, and new events may be scheduled probabilistically to account for randomness, such as variable interarrival times.[5] The simulation clock does not increment in fixed steps but jumps to the time of the imminent event, emphasizing logical progression over physical time and enabling efficient modeling of sparse activity periods.[5] This paradigm handles stochastic elements through random number generation for event timing and outcomes, while focusing on discrete state transitions that reflect real-world discontinuities.[6] Unlike continuous simulation, which models systems with smoothly varying variables over time (e.g., fluid flow or population growth using differential equations), discrete-event simulation prioritizes abrupt, event-triggered changes and ignores intervals between events where no state alterations occur.[5] This distinction makes it more efficient for systems with infrequent but impactful events, such as queueing networks, compared to the time-stepped integration required in continuous models.[5] GPSS, developed by Geoffrey Gordon at IBM in the early 1960s and presented in 1961, was a pioneering simulation language that formalized the event-scheduling paradigm and laid the groundwork for modern simulation tools by enabling users to model complex interactions without low-level programming.[7][8]Illustrative Example
To illustrate the operation of discrete-event simulation, consider a single-server queue modeling customers arriving at a bank teller window, where the only events are customer arrivals and service completions.[9] The system state is defined by the number of customers in the system , the queue length , and the server status (1 if busy, 0 if idle), with the simulation clock advancing discretely to the next event time.[9] An event list maintains scheduled future events, such as the next arrival or departure, processed in chronological order using a first-in, first-out queue discipline.[9] The simulation starts at with an empty queue (), no customers in the system (), and the server idle ().[9] The initial event list schedules the first customer arrival at minutes. The clock jumps to this time, triggering the arrival event: customer 1 enters the system (), joins an empty queue (), and immediately starts service since the server is idle (), with a service time of 4 minutes, scheduling a departure event at (3 + 4). The updated event list now includes the next arrival at and the departure at .[9] The clock advances to for the departure event: customer 1 completes service and leaves (), the server becomes idle (), and the queue remains empty (). The next event is the arrival of customer 2 at : the customer enters (), service starts immediately (, ), with a 4-minute service time scheduling departure at . Subsequent events build the queue as arrivals cluster. For instance, at , customer 3 arrives while the server is busy serving customer 2, increasing the queue to and ; service for customer 3 is scheduled to start at upon customer 2's departure. At , customer 4 arrives, further lengthening the queue to and , with service start delayed to .[9] The simulation continues processing arrivals and departures, with the queue peaking at 3 customers around as a cluster of arrivals (customers 5–7) occurs while earlier customers are still being served. Departures then reduce the queue: for example, at , customer 4 departs after a 5-minute wait, allowing the server to remain busy. The run terminates after customer 7's departure at , having processed 7 customers (customer 8's arrival at 27 is queued but not fully served in this trace). State updates occur only at event times, avoiding unnecessary computation between events.[9] The following table summarizes the event sequence, state changes, and per-customer metrics for the first seven customers (arrival times: 3, 11, 13, 14, 17, 19, 21; service times: 4, 4, 4, 3, 2, 4, 3 minutes), where is arrival time, is service start time, is departure time, is wait time, and is time in system.[9]| Event Time | Event Type | Customer ID | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | Arrival | 1 | 3 | 3 | 7 | 0 | 4 | 1 | 0 | 1 |
| 7 | Departure | 1 | 3 | 3 | 7 | 0 | 4 | 0 | 0 | 0 |
| 11 | Arrival | 2 | 11 | 11 | 15 | 0 | 4 | 1 | 0 | 1 |
| 13 | Arrival | 3 | 13 | 15 | 19 | 2 | 6 | 2 | 1 | 1 |
| 14 | Arrival | 4 | 14 | 19 | 22 | 5 | 8 | 3 | 2 | 1 |
| 15 | Departure | 2 | 11 | 11 | 15 | 0 | 4 | 2 | 1 | 1 |
| 17 | Arrival | 5 | 17 | 22 | 24 | 5 | 7 | 3 | 2 | 1 |
| 19 | Departure | 3 | 13 | 15 | 19 | 2 | 6 | 2 | 1 | 1 |
| 19 | Arrival | 6 | 19 | 24 | 28 | 5 | 9 | 3 | 2 | 1 |
| 21 | Arrival | 7 | 21 | 28 | 31 | 7 | 10 | 4 | 3 | 1 |
| 22 | Departure | 4 | 14 | 19 | 22 | 5 | 8 | 3 | 2 | 1 |
| 24 | Departure | 5 | 17 | 22 | 24 | 5 | 7 | 2 | 1 | 1 |
| 27 | Arrival | 8 | 27 | - | - | 4* | - | 3 | 2 | 1 |
| 28 | Departure | 6 | 19 | 24 | 28 | 5 | 9 | 2 | 1 | 1 |
| 31 | Departure | 7 | 21 | 28 | 31 | 7 | 10 | 1 | 0 | 1 |
Key Components
System State
In discrete-event simulation (DES), the system state is defined as the collection of state variables necessary to describe the condition of the simulated system at any given time. These variables capture essential attributes such as the number of entities in queues, the status of resources, or the positions of objects within the model, providing a complete snapshot of the system's configuration without including time-dependent changes between events.[5][10] State updates in DES occur instantaneously and exclusively at the occurrence of discrete events, with no alterations to the state variables in the intervals between events. For instance, upon execution of an arrival event, the relevant state variable—such as a queue length counter—is incremented by one, while a departure event might decrement it or update a resource availability flag. This event-driven update mechanism ensures that the system state remains constant during inter-event periods, reflecting the piecewise-constant nature of DES models.[1][5] State variables in DES are typically classified into discrete types, which hold integer or categorical values like counts of entities or binary statuses (e.g., idle or busy), and auxiliary variables that serve temporary roles during event processing, such as flags to track ongoing operations or intermediate computations without persisting across events. Discrete variables form the core of the state, enabling efficient representation of countable system elements, whereas auxiliary ones facilitate modular event routines without cluttering the primary state description.[10][5] A representative example of a system state snapshot appears in a manufacturing simulation, where the state might include an array of machine statuses (e.g., {machine1: busy, machine2: idle}) and work-in-progress inventory levels (e.g., buffer1: 5 units, buffer2: 2 units), updated only when events like part arrivals or processing completions occur. This structure allows the state to interact seamlessly with the event list for sequential processing and supports subsequent computation of performance statistics.[1][5]Simulation Clock
In discrete-event simulation (DES), the simulation clock serves as the primary mechanism for tracking the passage of simulated time, which is advanced only at the instants when events occur, reflecting changes in the system's state. It is typically initialized to zero at the start of the simulation, corresponding to the beginning of the observation period, with the system set to its initial conditions such as an empty queue or idle resources. This clock value represents the current simulated time and is used to sequence events chronologically, ensuring that the simulation captures the logical progression of the modeled system without unnecessary computations during periods of inactivity.[5] The time advancement algorithm operates by setting the clock directly to the scheduled time of the next event, determined as the minimum time from the future event list, thereby leaping forward without interpolating or simulating continuous time flows between events. This next-event time advance mechanism processes the event, updates the system accordingly, and schedules any subsequent events before repeating the cycle. For example, if no events are pending, the clock jumps to the earliest future occurrence, skipping idle intervals efficiently. This approach contrasts with fixed-increment methods by aligning time progression strictly to event occurrences, optimizing computational resources for systems where changes are sporadic.[5] When multiple events are scheduled at the exact same simulated time—known as zero-time events—the clock remains stationary while these events are processed in sequence, often according to predefined priorities, first-in-first-out order, or system-specific rules to maintain logical consistency. This sequential handling ensures that all simultaneous changes, such as an arrival and a departure occurring concurrently, are resolved without advancing the clock until all are addressed, preventing errors in state dependencies.[5] In stochastic DES models, the clock's discontinuous jumps emphasize the logical ordering of events driven by probabilistic interarrival or service times, rather than uniform or incremental time steps, which distinguishes it from time-stepped simulations that advance in regular intervals regardless of activity. This event-oriented progression is particularly suited to modeling systems like queues or manufacturing lines, where time between changes varies and continuous tracking would be inefficient.[5]Event List
In discrete-event simulation, the event list, often referred to as the future event list (FEL), serves as the central data structure for organizing and accessing all scheduled future events. It maintains a collection of event notices, each specifying the event type (e.g., arrival or departure), the associated time of occurrence, and relevant attributes such as the involved entities or parameters. This structure ensures that the simulation progresses by processing events in chronological order, reflecting the non-continuous nature of the modeled system. Typically implemented as a priority queue, the FEL orders events by increasing simulation time to facilitate rapid identification of the imminent event.[11] Events are inserted into the FEL through scheduling mechanisms, which can be unconditional—such as routinely adding a future arrival event—or conditional, where insertion depends on the current system state, like scheduling a service completion only if a server becomes available. Upon insertion, the event notice is placed in its appropriate position within the priority queue to preserve the time-based ordering. Removal involves extracting the event with the earliest time, which is then executed to update the system; this operation is performed repeatedly to drive the simulation forward. For efficiency, common implementations use binary heaps, where insertion and removal both operate in O(log n) time complexity, with n being the number of events in the list, making them suitable for simulations with moderate to large event volumes.[11][12] The FEL also requires mechanisms for managing dynamic changes, such as cancellations of preempted or invalidated events; this might involve deleting specific notices by searching for matching attributes like entity identifiers, though such operations can be costly if not optimized. When multiple events share the same timestamp, the priority queue resolves ties using secondary criteria, such as event type priority or a first-in-first-out order, to determine the execution sequence. Advanced data structures further enhance management: for instance, the calendar queue organizes events into time-based buckets with linked lists, achieving amortized O(1) time for both insertions and removals by dynamically adjusting bucket widths to balance load, as demonstrated in benchmarks where it outperformed binary search trees by a factor of three for queues of 10,000 events. These efficiency considerations are crucial, as inefficient FEL management can increase overall simulation runtime by up to five times in complex models.[11][13][12]Random Number Generators
In discrete-event simulation (DES), random number generators are crucial for introducing stochasticity to model uncertainties such as variable arrival times, service durations, or decision outcomes. Uniformly distributed pseudorandom variates, typically in the interval [0,1), serve as the foundation, which are then transformed into random variates following specific probability distributions to simulate real-world variability.[5][14] Pseudorandom numbers are generated using deterministic algorithms that produce sequences indistinguishable from true randomness for practical purposes. A widely used method is the linear congruential generator (LCG), defined by the recursive formulaStatistics Collection
In discrete-event simulation, statistics collection involves gathering data on system performance metrics during the simulation run to evaluate key performance indicators such as throughput, utilization, and queue lengths. These metrics are typically categorized into point estimates, which provide single values like total throughput (the cumulative count of entities completing the system), and interval estimates, which offer averages with associated uncertainty, such as the average queue length computed via time-weighted averages. Time-weighted averages account for the duration each state persists between events, ensuring that longer periods contribute proportionally more to the overall estimate. For instance, queue length averages are derived by integrating the queue size over time, divided by the total simulation time. Collection methods rely on updating accumulators at event occurrences to track these metrics efficiently without continuous monitoring. For example, server busy time is accumulated by adding the time interval (delta time) between a server becoming busy and subsequently idle to a running total whenever a state change event occurs. Counts like throughput are simply incremented each time an entity exits the system. To obtain confidence intervals for these estimates, multiple independent replications of the simulation are performed, allowing computation of the sample mean and standard deviation across runs, which enables statistical inference on the true system parameters. For steady-state simulations, where interest lies in long-run behavior after initial transients fade, statistics collection must address initialization bias by detecting and discarding the warm-up period. Common techniques include discarding a fixed initial portion of the output or using batch means, where the simulation output is divided into non-overlapping batches treated as independent observations to handle positive autocorrelation in the data. The sample mean from batch means is calculated asTermination Conditions
In discrete-event simulation, termination conditions define the criteria for ending a simulation run, ensuring that sufficient data is collected to meet analytical objectives while avoiding excessive computational resources. These conditions are essential for both terminating simulations, which model systems with a natural end point, and non-terminating (steady-state) simulations, which approximate long-run behavior.[5][10] Common termination conditions rely on fixed thresholds to provide straightforward control. One prevalent approach is to run the simulation until the clock reaches a predetermined time, such as 1000 minutes or 120 months, often implemented by scheduling a dedicated end-simulation event.[5][10] Another is to halt after a specific number of events, for instance, processing 1000 customer arrivals or 3000 job completions, which ties the run length directly to system activity.[5][10] Entity-based conditions extend this by stopping when a target involving system entities is achieved, such as serving 1000 customers or shipping the last item in an inventory model.[5][10] These methods ensure reproducibility but may require preliminary testing to select appropriate thresholds that capture relevant system dynamics without under- or over-sampling. Statistical termination conditions offer a data-driven alternative, allowing runs to adapt based on the precision of output estimates. A simulation may continue until the half-width of a confidence interval for a key performance measure, such as average queue length, falls below a specified value ε (e.g., ε = 2 units at 95% confidence).[5][10] Sequential sampling plans further refine this by incrementally analyzing accumulating data and stopping when statistical criteria are met, such as requiring at least 19 replications for a desired error bound in mean throughput estimates.[5] These approaches, often using methods like the two-stage Bonferroni procedure, prioritize estimate reliability over fixed durations.[5] For steady-state simulations, where the goal is to ignore initial transients and focus on equilibrium behavior, termination requires careful handling to avoid biased results. Pilot runs are commonly used to estimate the necessary run length, identify a warmup period (e.g., discarding the first 2 hours or 10 days of data), and ensure the system reaches statistical steady-state before full data collection begins.[5][10] Techniques like the replication/deletion method involve multiple short runs with data deletion from the start, while batch means analysis divides a single long run (e.g., into 30 batches) to verify independence and steady-state attainment.[5] To prevent infinite loops in event scheduling, especially in steady-state cases, safeguards such as maximum allowable events or clock time are incorporated.[5] Practical implementations often combine multiple conditions for robustness, such as terminating at the minimum of a fixed time (e.g., 720 minutes) or a maximum number of events (e.g., 1000 customers), which mitigates risks like event list overflow in prolonged runs.[5][10] This hybrid strategy, supported by tools like Arena's output analyzer for real-time precision checks, ensures simulations remain efficient and reliable across diverse applications.[5]Simulation Methodologies
Event-Scheduling Approach
The event-scheduling approach, also known as the next-event protocol, is a core methodology in discrete-event simulation that advances the simulation by sequentially processing the earliest pending event from a future event list (FEL). This method models system dynamics through a sequence of instantaneous events that alter the system state at discrete points in time, without simulating the passage of time between events. Originating in early simulation efforts, it was formalized by K.D. Tocher as an event-oriented paradigm for representing complex systems like queuing networks.[19] The approach emphasizes a global event list to manage all anticipated changes, making it a foundational technique for implementing simulations in languages like GPSS and modern tools such as Arena. The core algorithm begins with initializing the system state variables, setting the simulation clock to zero, and scheduling initial events into the FEL. It then enters a loop where the event notice with the smallest timestamp is removed from the FEL, the clock is advanced to that event's time, and the associated event routine is executed. During execution, the routine updates the system state—such as incrementing counters or reallocating resources—and may schedule additional future events into the FEL based on the outcomes. This cycle repeats until a predefined termination condition, like reaching a maximum number of events or a specific clock time, is satisfied. The algorithm ensures logical consistency by processing events in strict chronological order, handling simultaneous events through tie-breaking rules if necessary.[5] Event execution typically proceeds in structured phases to maintain model integrity: first, pre-execution checks validate the event's applicability given the current state, preventing invalid actions; second, the state is updated to reflect the event's effects, such as a departure reducing queue length; and third, post-execution scheduling occurs, where new events are added unconditionally for predictable future occurrences (e.g., a fixed-interval arrival) or conditionally based on state-dependent logic (e.g., scheduling a service completion only if a server becomes free). These phases allow for modular event routines that encapsulate decision logic and updates. This approach is ideal for modeling systems featuring simple, asynchronous entities with infrequent interactions, accommodating both deterministic events (e.g., scheduled maintenance) and stochastic ones (e.g., random arrivals via probability distributions). It excels in scenarios like single-server queues or inventory systems where event interdependencies are minimal, providing efficient time advancement without unnecessary computations between events.[5] The following pseudocode outlines the basic event-scheduling algorithm:Initialize system state
Set clock = 0
Schedule initial events into FEL
While not termination condition:
next_event = extract minimum from FEL // earliest timestamp
If FEL is empty, terminate
clock = next_event.time
Execute event routine for next_event // update state, schedule new events
Dispose of next_event notice
[20]