Rotate the screen

Discrete event simulation

The principles of discrete event simulation (DES) can be represented by following concept.

As an example a traffic lights will be considered.

Process

By process in DES understood a sequence of actions that fully or partially describe the behavior of the object under study.

An action of traffic lights is light color switching: from red to yellow, from yellow to green, and so on. Light color switching is a DES process of traffic lights.

A process can be activated or suspended. Active process is suspended when another process is activated. Only one process can be active in the certain time.

A traffic lights process has to be suspended after green light switching for some other process activation. For example that can be a car simulation processes.

Therefore, it needs to somehow know at which time which process should be activated. In other words it has to plan some event.

Event

An event concept is a cornerstone of DES. The idea is that not every time quantum should be simulated, but only a certain time points when a process has to be activated or suspended.

For traffic lights example the time points of light switching should be simulated only. A time between switching is not of interest.

DES time points are presented in the simulation chain only when the state of the process changes. Such a state change that causes activation (or reactivation) of a process is understood in DES as an event.

If the state of the process does not change, then in terms of DES no event happens. If there is no event, no simulation actions should be performed. This important and reasonable DES concept saves much simulation runtime.

Event list concept

Event list

As DES operates with events the information about should be somewhere kept and ordered. For this job a special list is used. It is called an event list or main schedule, as well as a sequential set or pending event set.

Event list consists of items containing event information: the process to be activated and the value of model time at which this event should occur. Such item is called event notice. Creating such an item for a process is called event planning.

The items are ordered ascending in the list by the model time of event. The first item contains the earliest event, the last one contains the latest. The item of event notice is inserted at the appropriate position into event list. Every time a new event for some process should be planned, an event notice is created and inserted into event list at the position in accordance with the event time.

Simulation

The simulation looks like a loop where the number of repetitions is equal (generally) to the number of generated entities. It is as follows:

By activation of the first process (usually a generator), a new event notice is created and inserted into event list (yet empty).
  • Begin. If event list is not empty, a process contained in the first event notice is activated.
  • If this process has a time pause in behavior description (or activates another process), the process is suspended at this point and its next active phase is planned:
    • Current event notice (first item) is taken out from event list.
    • The item is updated with the new model time value (after pause or after another process suspending) and inserted into event list at a specific position.
    • If a new process is activated from the current one, a new event notice with the current model time value is created for this process and inserted first into event list.
    • And the simulation continues with begin.