Chapter 5. Event-Based Simulation with Objects

Classical Event-Based Simulation (ES) can be extended in a natural way by adding the modeling concept of objects, such that the characteristics of real-world objects can be captured by the attributes of model objects instead of using state variables. The resulting simulation paradigm is called Object Event Simulation (OES).

In this section, summarizing (Wagner 2020), we show how to extend Event Graphs by adding the modeling concept of objects, resulting in Object Event Graphs. The modeling concept of objects (as instances of classes) has been pioneered by Dahl and Nygaard (1967) in their simulation programming language Simula, which initiated the development of the Object-Oriented (OO) modeling and programming paradigm in Software Engineering.

5.1. Object Event Graphs

Object Event Graphs (OEGs) extend the Event Graph diagram language by adding object rectangles containing declarations of typed object variables and state change statements, as well as gateway diamonds for expressing conditional and parallel branching.

The following basic DPMN diagram shows an OEG defining a process pattern that is instantiated by the above discrete event process example.

Figure 5-1. A basic DPMN Process Diagram showing an OEG.

This process model is based on the following Object Event (OE) class model:

Figure 5-2. A basic OE class model defining an object type and three event types.

Notice that the multiplicity 1 (standing for "exactly one") at the association end touching the object class WorkStation expresses the constraint that exactly one workstation must participate in any event of one of the associated types (PartArrival, ProcessingStart, or ProcessingEnd), while the multiplicity 0..1 (standing for "at most one") at the other association ends (touching one of the three event classes) expresses the constraint that, at any moment, a workstation participates in at most one PartArrival event, in at most one ProcessingStart event, and in at most one ProcessingEnd event. Notice that a further constraint should be added: at any moment, a workstation must not participate in both a ProcessingStart and a ProcessingEnd event.

An OEG specifies a set of chained event rules, one rule for each event circle of the model. The above OEG specifies the following three event rules:

  1. On each PartArrival event, the inputBufferLength attribute of the associated WorkStation object is incremented and if the workstation's status attribute has the value AVAILABLE, then a new ProcessingStart event is scheduled to occur immediately.
  2. When a ProcessingStart event occurs, the associated WorkStation object's status attribute is changed to BUSY and a ProcessingEnd event is scheduled with a delay provided by invoking the processingTime function defined in the ProcessingStart event class.
  3. When a ProcessingEnd event occurs, the inputBufferLength attribute of the associated WorkStation object is decremented and if the inputBufferLength attribute has the value 0, the associated WorkStation object's status attribute is changed to AVAILABLE. If the inputBufferLength attribute has a value greater than 0, a new ProcessingStart event is scheduled to occur immediately.

The formal (transition system) semantics of OEGs, based on the semantics of event rules as transition functions, has been presented in (Wagner 2017a). It can be shown that the OEG diagram language is a conservative extension of the Event Graph diagram language by means of a homomorphic embedding of Event Graphs in OEGs.

Formally, an OEG is defined on the basis of a set of object types OT and a set of event types ET as a directed graph ⟨ N, D ⟩ with nodes N and directed edges DNN , such that

  1. each node nN is associated with

    1. an event type EET with event participation roles PE,
    2. an event variable e representing an event of type E,
    3. a (possibly empty) set of auxiliary (shortcut) object variables o defined with the help of event participation roles pPE by setting o := e.p,
    4. a (possibly empty) set of definitions of on-event object state transition functions { fp | pPE };
  2. each directed edge ⟨ n1, n2 ⟩ ∈ D may be associated with
    1. a numeric delay expression δ possibly expressed with the help of the variables associated with n1,
    2. a condition (or Boolean expression) C expressed with the help of the variables associated with n1.

5.2. The OES Formalism

The OEM&S paradigm is based on the OES formalism presented in (Wagner 2017a), which is summarized below.

Both object types and event types are defined in the form of classes: with a name, a set of properties and a set of operations, which together define their signature. A property is essentially defined by a name and a range, which is either a datatype (like Integer or String) or an object type.

A set of object types OT defines a predicate-logical signature as the basis of a logical expression language LOT: each object type defines a unary predicate, and its properties define binary predicates. A state change language COT based on OT defines state change statements expressed with the help of the object type names and property names defined by OT. In the simplest case, state change statements are property value assignments like o.p1 := 4 or o.p1 := o.p2 where o is an object variable and p1, p2 are property names.

A set of objects O = {o1, o2, ...on} where each of them has a state in the form of a set of slots (property-value pairs) represents a system state, that is a state of the real-world system being modeled and simulated. A system state O can be updated by a set of state changes (or, more precisely, state change statements) ΔCOT with the help of an update operation Upd. For instance, for a system state O1 = {o1} with o1 = { p1: 2, p2: 5} and a set of state changes Δ1 = { o1.p1 := o1.p2 } we obtain

Upd( O1, Δ1) = {{ p1: 5, p2: 5}}

An event expression is a term E(x)@t where

  1. E is an event type,
  2. x is a (possibly empty) list of event parameters x1, x2, …, xn according to the signature of the event type E,
  3. t is a parameter for the occurrence time of events.

For instance, PartArrival(ws)@t is an event expression for describing part arrival events where the event parameter ws is of type WorkStation, and t denotes the arrival time. 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, PartArrival(ws1)@1 is a ground event expression representing an individual PartArrival event occurring at workstation ws1 at time 1.

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 {ProcessingEnd(ws1)@4, PartArrival(ws1)@4}.

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 objects concerned, and follow-up events are immediately scheduled by adding them to the FEL. For the OES formalism, we assume that an event routine is a pure function that computes state changes and follow-up events, but does not apply them, as illustrated by the examples in the following table.

Event rule name / rule variables

ON (event expression)

DO (event routine)

rPA

a: PartArrival
ws
: WorkStation
ws := a.workStation

PartArrival(ws) @ t

Δ := { ws.waitingParts.push( a.part)}

IF ws.status = AVAILABLE
THEN FE := {ProcessingStart(ws)@t+1}
ELSE FE := {}

RETURN ⟨ Δ, FE

rPS

ps: ProcessingStart
ws
: WorkStation
ws := ps.workStation

ProcessingStart(ws) @ t

Δ := { ws.status := BUSY}

FE := {ProcessingEnd(ws)@t + ProcessingStart.processingTime()}

RETURN ⟨ Δ, FE

rPE

pe: ProcessingEnd
ws
: WorkStation
ws := pe.workStation

ProcessingEnd(ws) @ t

Δ := { ws.waitingParts.pop()}
IF ws.waitingParts.length = 0
THEN Δ := Δ ∪ {ws.status := AVAILABLE}

IF ws.waitingParts.length > 0
THEN FE := { ProcessingStart(ws)@t+1}
ELSE FE := {}

RETURN ⟨ Δ, FE

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.

An OE model based on a state change language COT and a corresponding update operation Upd is a triple ⟨OT, ET, R⟩, consisting of a set of object types OT, event types ET and event rules R.

An OE simulation (system) state based on an OE model ⟨OT, ET, R⟩ is a triple S = ⟨t, O, E⟩ with t being the current simulation time, O being a system state (a set of objects instantiating types from OT), and E being a set of imminent events to occur at times greater than t (and instantiating types from ET), also called Future Event List (FEL).

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 re = F( i, v), which maps a system state O to a pair ⟨ Δ, FE ⟩ of system state changes ΔCOT and follow-up events FE. 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 Fi,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 event type. When r is triggered by e, we can form the state change function re = Fi,v and apply it to a system state O by mapping it to a set of state changes and a set of follow-up events:

re(O) = Fi,v(O) = ⟨ Δ, FE

We can illustrate this with the help of our workstation example. Consider the rule rPA defined in the table above triggered by the event PartArrival(ws1)@1 in state O0 = {ws1.status: AVAILABLE, ws1.waitingParts: []}. We obtain

rPA( O0 ) = F1,ws1( O0 ) = ⟨ Δ1, FE1

with Δ1 = { ws1.waitingParts.push( a.part)} and FE1 = {ProcessingStart@2}.

An OE model defines a state transition system where

  1. A state is a simulation state S = ⟨t, O, E⟩.

  2. A transition of a simulation state S consists of

    1. advancing t to the occurrence time t' of the next events NEE, which is the set of all imminent events with minimal occurrence time;

    2. processing all next events eNE by applying the event rules rR triggered by them to the current system state O according to

      re( O ) = ⟨ Δe , FEe

      resulting in a set of state changes Δ = ∪ {Δe | eNE } and a set of follow-up events FE = ∪ {FEe | eNE }.

    such that the resulting successor simulation state is S' = ⟨ t', O', E' ⟩ with O' = Upd( O, Δ) and E' = ENEFE.

Notice that the OES formalism first collects all state changes brought about by all the simultaneous next events (from the set NE) of a simulation step before applying them. This prevents the state changes brought about by one event from NE to affect the application of event rules for other events from NE, thus avoiding the problem of non-determinism through the potential non-confluence (or non-serializability) of parallel events.

OE simulators are computer programs that implement the OES formalism. Typically, for performance reasons, discrete event simulators do not first collect all state changes brought about by all the simultaneous next events (the set NE) of a simulation step before applying them, but rather apply them immediately in each triggered event routine. However, this approach takes the risk of an unreliable semantics of certain simulation models in favor of performance.