Chapter 5. Event-Based Simulation without Objects
When Event-Based Simulation (ES) was developed in the 1960's, pioneered by SIMSCRIPT, the software engineering paradigm of Object-Oriented (OO) modeling and programming was not yet available. Therefore, the real-world objects of a system under investigation have not been modeled as objects, but rather the relevant characteristics of the (objects of) the system have been modeled in the form of state variables.
5.1. The ES Formalism
We illustrate the formal semantics of ES with the help of an example. We model a system of one or more service desks, each of them having its own queue, as a discrete event system characterized by the following narrative:
- Customers arrive at a service desk at random times.
- If there is no other customer in front of them, and the service desk is available, they are served immediately, otherwise they have to queue up in a waiting line.
- The duration of services varies, depending on the individual case.
- When a service is completed, the customer departs and the next customer is served, if there is still any customer in the queue.
The base concepts of ES are:
- state variables for describing the state of a system,
- event types,
- event expressions,
- event routines,
- future events lists (FEL).
A state variable is declared with a name and a range, which is a datatype defining its possible values.
An event type is defined in the form of a class: with a name, a set of property declarations and a set of method definitions, which together define the signature of the event type.
An event expression is a term E(x)@t where
- E is an event type,
- t is a parameter for the occurrence time of events,
- x is a (possibly empty) list of event parameters x_{1}, x_{2}, …, x_{n} according to the signature of the event type E.
For instance, Arrival@t is an event expression for describing Arrival events where the signature of the event type Arrival is empty, so there are no event parameters, and the parameter t denotes the arrival time (more precisely, the occurrence time of the Arrival event). An individual event of type E is a ground event expression, e = E(v)@i, where the event parameter list x and the occurrence time parameter t have been instantiated with a corresponding value list v and a specific time instant i. For instance, Arrival@1 is a ground event expression representing an individual Arrival event.
An event routine is a procedure that essentially computes state changes and follow-up events, possibly based on conditions on the current state. In practice, state changes are often directly performed by immediately updating the state variables concerned, and follow-up events are immediately scheduled by adding them to the FEL. However, for defining the formal semantics of ES, we assume that an event routine is a pure function that computes state changes and follow-up events, but does not apply them, as in the rules described in Table 5-1.Event rule name | ON (event expression) | DO (event routine) |
r_{Arr} | Arrival @ t | E’ := { Arrival @ (t + recurrence()) } |
r_{Dep} | Departure @ t | E’ := {} |
An event rule associates an event expression with an event routine F:
ON E(x)@t DO F( t, x),
where the event expression E(x)@t specifies the type E of events that trigger the rule, and F( t, x) is a function call expression for computing a set of state changes and a set of follow-up events, based on the event parameter values x, the event's occurrence time t and the current system state, which is accessed in the event routine F for testing conditions expressed in terms of state variables.
A Future Events List (FEL) is a set of ground event expressions partially ordered by their occurrence times, which represent future time instants either from a discrete or a continuous model of time. The partial order implies the possibility of simultaneous events, as in the example { Departure@4, Arrival@4 }.
ES Models
An ES model is a triple ⟨ SV, ET, R ⟩ where
- SV is a set of state variable declarations defining the structure of possible system states,
- ET is a set of event type definitions,
- R is a set of event rules expressed in terms of SV and ET.
We show how to express the example model of a simple service desk system as an ES model. The set of state variables is a singleton:
SV = { queueLength: NonNegativeInteger}
There are two event types, both having an empty signature:
ET = { Arrival(), Departure()}
And there are two event rules:
R = { r_{Arr}, r_{Dep}}
which are defined as in Table 1 above.
Such a model, together with an initial state (specifying initial values for state variables and initial events), defines an ES system, which is a transition system where
- system states are defined by value assignments for the state variables,
- transitions are provided by event occurrences triggering event rules that change the simulation state through changing the system state (by changing the values of affected state variables) and the FEL (by adding follow-up events).
Whenever the transitions of an ES system involve computations based on random numbers (if the simulation model contains random variables), the transition system defined is non-deterministic.
For instance, assuming that the initial system state is S_{0} = {queueLength: 0}, and there is an initial event {Arrival@1}, then, as a consequence of applying r_{Arr}, there is a system state change {queueLength := 1} and, assuming a random service time of 2 time units (as a sample from the underlying probability distribution function), a follow-up event Departure@3, which has to be scheduled along with the next Arrival event, say Arrival@3 (with a random inter-arrival time of 2), because Arrival is an exogenous event type (with a random recurrence). Consequently, the next system state is S_{1} = {queueLength: 1}.
We need to distinguish between the system state, like S_{0} = {queueLength: 0}, which is the state of the simulated system, and the simulation state, which adds the FEL to the system state, like
S_{0} = ⟨ {queueLength: 0}, {Arrival@1} ⟩
S_{1} = ⟨ {queueLength: 1}, {Arrival@2, Departure@3} ⟩
Doing one more step, the next transition is given by the next event Arrival@2 again triggering r_{Arr}, which leads to
S_{2} = ⟨ {queueLength: 2}, {Departure@3, Arrival@4} ⟩
In this way, we get a succession of states S_{0} → S_{1} → S_{2} → … as a history of the transition system defined by the ES model.
Event Rules as Functions
An event rule r = ON E(x)@t DO F( t, x) can be considered as a 2-step function that, in the first step, maps an event e = E(v)@i to a parameter-free state change function r_{e} = F( i, v), which maps a system state to a pair ⟨ Δ, E' ⟩ of system state changes Δ and follow-up events E'. When the parameters t and x of F( t, x) are replaced by the values i and v provided by a ground event expression E(v)@i, we also simply write F_{i,v} instead of F( i, v) for the resulting parameter-free state change function.
We say that an event rule r is triggered by an event e when the event’s type is the same as the rule’s triggering event type. When r is triggered by e, we can form the state change function r_{e} = F_{i,v} and apply it to a system state S by mapping it to a set of system state changes Δ and a set of follow-up events E':
r_{e}(S) = F_{i,v}(S) = ⟨ Δ, E' ⟩
We can illustrate this with the help of our running example. Consider the rule r_{Arr} defined in Table 1 above triggered by the event Arrival@1 in state S_{0} = {queueLength: 0}. The resulting state change function F_{1} defined by the corresponding event routine from Table 1 maps S_{0} to the set of state changes Δ = { INCREMENT queueLength} and the set of follow-up events E' = {Departure@3}. We show how the pair ⟨ Δ, E' ⟩ amounts to a transition of the simulation state in the next section.
In ES, a system state change is an update of one or more state variables. Such an update is specified in the form of an assignment where the right-hand side is an expression that may involve state variables. For instance, the state change INCREMENT queueLength is equivalent to the assignment queueLength := queueLength + 1.
In general, there may be situations, where we have several concurrent events, that is, there may be two or more events occurring at the same (next-event) time. Therefore, we need to explain how to apply a set of rules R_{E} triggered by a set of events E, even if both sets are singletons in many cases.
The rule set R of an ES model can also be considered as a 2-step function that, in the first step, maps a set of events E to a state change function R_{E}, which maps a system state to a pair ⟨ Δ, E' ⟩ of state changes Δ and follow-up events E'.
For a given set of events E and a rule set R, we can form the set of state change functions obtained from rules triggered by events from E:
R_{E} = { r_{e} : r ∈ R & e ∈ E & e triggers r}
Notice that the elements C of R_{E} are parameter-free state change functions, which can be applied as a block, in parallel, to a system state S:
R_{E}(S) = ⟨ Δ, E' ⟩
with
Δ = ⋃ { Δ_{C} : C ∈ R_{E} & C(S) = ⟨ Δ_{C}, E'_{C} ⟩ }
E' = ⋃ { E'_{C} : C ∈ R_{E} & C(S) = ⟨ Δ_{C}, E'_{C} ⟩ }
Notice that when forming the union of all state changes brought about by applying rules from R_{E}, and likewise when forming the union of all follow-up events created by applying rules from R_{E}, the order of rule applications does not matter because they do not affect the applicability of each other, so any selection function for choosing rules from R_{E} and applying them sequentially will do, and they could also be applied simultaneously if such a parallel computation is supported.
However, computing a set of state changes Δ raises the question if this set is, in some sense, consistent. A simple, but too restrictive, notion of consistent state changes would require that if Δ contains two or more updates of the same state variable, all of them must be equivalent (effectively assigning the same value). A more liberal notion just requires that if Δ contains two or more updates of the same state variable, their collective application must result in the same value for it, no matter in which order they are applied.
If Δ contains inconsistent updates for a state variable, this may be a bug or a feature of the simulation model. If it is not a bug, a conflict resolution policy is needed. The simplest policy is ignoring, or discarding, all inconsistent updates. Another common conflict resolution policy is based on assigning priorities to event rules.
Consider again our running example with a system state S = {queueLength: 1} and the set of next events N = {Arrival@4, Departure@4}. Then, R_{N} consists of the two parameter-free change functions:
- F_{1}: function () {Δ := { INCREMENT queueLength}; IF queueLength = 0 THEN
E' := { Departure @ (4 + serviceDuration())}; RETURN ⟨ Δ, E' ⟩ } - F_{2}: function () {Δ := { DECREMENT queueLength}; IF queueLength > 1 THEN
E' := { Departure @ (4 + serviceDuration())}; RETURN ⟨ Δ, E' ⟩}
No matter in which order we apply F_{1} and F_{2}, forming the union of their state changes always results in Δ = {}, because the incrementation and decrementation of the variable queueLength neutralize each other, and forming the union of their follow-up events always results in E' = { Departure@(4+d)} where d is the random value returned by the serviceDuration function.
An Event Rule Set as a Simulation State Transition Function
We show that the event rule set R of an ES model ⟨ SV, ET, R ⟩ defines a transition function that maps a simulation state ⟨ S, FEL ⟩ to a successor state ⟨ S', FEL' ⟩ in 3 steps:
- R maps the set of next events N extracted from the FEL to a set R_{N} of state change functions of rules triggered by one of the next events from N.
- R_{N} maps the current system state S to a set of state changes Δ and a set of follow-up events E'.
- The pair ⟨ Δ, E' ⟩ amounts to a transition of the current simulation state ⟨ S, FEL ⟩ by applying the updates from Δ to S yielding S’ and by removing N from FEL and adding E'.
We have already explained how to obtain R_{N} from R and how to apply R_{N} to S for getting ⟨ Δ, E' ⟩ in the previous subsection, so we only need to provide more explanation for the last step: processing ⟨ Δ, E' ⟩ for obtaining the next simulation state ⟨ S', FEL' ⟩.
Let Upd denote an update operation that takes a system state S and a set of state changes Δ, and returns an updated system state Upd( S, Δ). When the system state consists of state variables, the update operation simply performs variable value assignments. Using this operation, we can define the third step of the simulation state transition function with two sub-steps in the following way:
- S' = Upd( S, Δ)
- FEL' = FEL − N ⋃ E'
This completes our definition of how the event rule set R of an ES model works as a transition function that computes the successor state of a simulation state:
R(⟨ S, FEL ⟩) = ⟨ S', FEL' ⟩
such that for a given initial simulation state S_{0} = ⟨ S_{0}, FEL_{0} ⟩, we obtain a succession of states
S_{0} → S_{1} → S_{2} → …
by iteratively applying R:
S_{i+1} = R( S_{i})
Consider again our running example. In simple cases we do not have more than one next event, so R_{N} is a singleton and we do not have to apply more than one rule at a time. For instance, when
S_{1} = ⟨{ queueLength: 1}, {Arrival@2, Departure@3}⟩
There is only one next event: Arrival@2, so we do not have to form a set of applicable rules, but can immediately apply the rule triggered by Arrival@2 for obtaining a set of system state changes and a set of follow-up events:
r_{Arr}_{ }( S_{1}) = ⟨{ queueLength := 2}, {Arrival@4}⟩
Now consider a simulation state where we have more than one next event, like the following one:
S_{3} = ⟨{ queueLength: 1}, {Arrival@4, Departure@4}⟩
We obtain
R( S_{3}) = ⟨{ queueLength: 1}, {Arrival@5, Departure@6}⟩
assuming a random inter-arrival time sample of 1 and a random service duration sample of 2.
5.2. Event Graphs
Event Graphs (EGs) have been proposed as a diagram language for making visual ES models by Schruben (1983). A node E in an EG is visually rendered as a circle annotated with state change statements in the form of state variable assignments and represents a typed event variable (such that the node name E is the name of the associated event type). An arrow (or directed edge) between two event circles (nodes) represents (a) the causation of a follow-up event in the case of a conceptual process model, or (b) the scheduling of a follow-up event according to the event scheduling paradigm in the case of a process simulation design model.
An Event Graph defining an ES model for a service desk system with one state variable (Q for queue length) and two event types (Arrival and Departure) is shown in the following diagram:
This model specifies three event rules, one for each event circle:
- On each initial event (the leftmost unnamed circle), the variable Q is initialized by setting it to 0, and then an Arrival event is scheduled to occur immediately.
- When an Arrival event occurs, the variable Q is incremented by 1 and, if Q is equal to 1, a Departure event is scheduled with a delay provided by invoking the function serviceTime (representing a random variable); in addition (since Arrival events are exogenous), a new Arrival event is scheduled with a delay provided by invoking the function recurrence (also representing a random variable).
- When a Departure event occurs, the variable Q is decremented by 1 and, if Q is greater than 0 (that is, if the queue is non-empty), another Departure event is scheduled with a delay provided by invoking the function serviceTime.
In Schruben's original notation for EGs used above:
There is an initial event (the left-most unnamed circle in the example EG above) creating the initial state with the help of one or more initial state variable assignments (here Q := 0) and triggering the real start event (here: Arrival). In our improved notation for EGs, we will drop this element in favor of getting simpler diagrams and assume that the initial state definition is taken care of separately and is not part of a process model diagram.
The recurrence of a start event (here: Arrival) is explicitly modeled with the help of a recursive arrow (going from the Arrival event circle to the Arrival event circle). In our improved notation for EGs, this recursive arrow is dropped assuming that the type definition of exogenous start events includes a recurrence function that is invoked by a simulator for automatically scheduling recurrent exogenous events (like Arrival).
Conditional event scheduling arrows are indicated by annotating the arrows with a condition in parenthesis, as shown above for the arrow between Arrival and Departure and the (reverse) arrow between Departure and Arrival. In our improved notation for EGs, we replace the parenthesis with brackets and use BPMN's notation for conditional "sequence flow" arrows with a mini-diamond at the arrow's start as shown below.
The same service desk model is shown in the following diagram using the improved notation resulting from these three simplifications/modifications:
Notice that in our improved notation for EGs, we use a + prefix for delay expressions, e.g., writing "+serviceTime()" instead of "serviceTime()" as an annotation of the event scheduling arrow between Arrival and Departure, for better indicating that the expression represents a scheduling delay. Notice also that, to a great extent, we use the visual notation of BPMN, but not its semantics (e.g., we do not use BPMN's visual distinction between "Start" and "Intermediate" events).
EGs provide a visual modeling language with a precise semantics that captures the fundamental event scheduling paradigm. However, Event Graphs are a rather low-level DES modeling language: they lack a visual notation for (conditional and parallel) branching, do not support object-oriented state structure modeling (with attributes of objects taking the role of state variables) and do not support the concept of activities.