Discrete-event simulation
The principles of discrete-event simulation (DES) can be explained with the following concepts.
A traffic light will be used as an example.
Contents:
Process
In DES, a process is a sequence of actions that describes the behavior of the object under study.
Traffic light actions are the sequential switching on of light of a specific color after a certain time interval.
This color switching is the DES process for the traffic light.
A process in DES can be active or suspended.
Only one process can be active at a time — the current process.
If the current process activates another, it becomes suspended.
If several processes need to run at the same time, they are activated sequentially at the specific model time.
For example, an active traffic light process can activate a vehicle moving process when green is turned on.
In this case, the traffic light process is suspended and the vehicle movement process becomes active.
Event
What determines when a process should be activated at a specific model time is called an event.
The event concept is the cornerstone of DES.
If a process's state does not change, no events occur for that process.
This means that there is no need to simulate the entire time of the process, but only the specific quantum of model time (the event) when the process should be activated.
If there is no event, no simulation action is performed.
This important DES concept significantly reduces model execution time in computer simulation.
For the traffic light example, only the events when the light color changes should be simulated.
Since nothing happens during the time between switches, this time should not be simulated.
Therefore, every event in discrete-event simulation is associated with the activation of a process,
and the simulation software must determine which process to activate and at what time.
To ensure this, events must be scheduled so that each process is activated at the correct simulation time.
Event list
Since discrete-event simulation operates on events, information about them must be stored and ordered.
For this purpose, a special list of events is created, called an event list (in Simula it is called a sequential set).
The event list consists of items that contain event information: the process to be activated and the simulation time at which the event should occur.
Such an item is called an event notice.
Placing an event notice into the event list is called event planning or event scheduling.
Event notices are sorted in the event list in ascending order of event time.
The first item corresponds to the earliest event, and the last one to the latest.
Whenever a new event is scheduled for a process, an event notice is created and inserted into the event list at the position corresponding to its event time.
Simulation
Discrete-event simulation executes as a
simulation loop that repeatedly processes scheduled events.
Initially, the event list is empty, and the model time is zero.
Then, the first process is activated.
An event notice for the process is created with the current modeling time and inserted into the event list before the process is activated.
The simulation loop proceeds as follows:
-
The event notice with the earliest event time is removed from the event list, and the corresponding process is activated.
-
The activated process executes its behavior until it either:
- reaches a time delay:
its event notice is updated with the new simulation time according to the time delay,
and the updated notice is moved across the event list at the appropriate position.
- activates another process:
- immediately:
the current process is suspended, and the other process is activated.
The event notice of the current process is removed from the event list,
and a new event notice for the other process with the current simulation time is inserted at the beginning of the event list.
- after the current process:
a new event notice for the other process with the specified future simulation time is inserted into the event list at the appropriate position,
and the current process continues execution.
- finishes its behavior execution:
The event notice of the current process is removed from the event list.
-
The simulation loop repeats by selecting the first event notice from the event list if it is not empty; otherwise, the simulation stops.
OpenSIMPLY
Free open source simulation software
