Chapter 5. Event-Based Simulation with Objects

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.

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

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 D ⊆ N ⨉ N , such that

1. each node n ∈ N is associated with

   1. an event type E ∈ ET with event participation roles P_E,
   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 p ∈ P_E by setting o := e.p,
   4. a (possibly empty) set of definitions of on-event object state transition functions { f_p | p ∈ P_E };
2. each directed edge ⟨ n₁, n₂ ⟩ ∈ D may be associated with
   1. a numeric delay expression δ possibly expressed with the help of the variables associated with n₁,
   2. a condition (or Boolean expression) C expressed with the help of the variables associated with n₁.

5.2. The OES Formalism

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

A set of object types OT defines a predicate-logical signature as the basis of a logical expression language L_OT: each object type defines a unary predicate, and its properties define binary predicates. A state change language C_OT 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.p₁ := 4 or o.p₁ := o.p₂ where o is an object variable and p₁, p₂ are property names.

A set of objects O = {o₁, o₂, ...o_n} 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) Δ ⊆ C_OT with the help of an update operation Upd. For instance, for a system state O₁ = {o₁} with o₁ = { p₁: 2, p₂: 5} and a set of state changes Δ₁ = { o₁.p₁ := o₁.p₂ } we obtain

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 x₁, x₂, …, x_n 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.

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.

An event rule associates an event expression with an event routine F:

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 C_OT 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 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 O to a pair ⟨ Δ, FE ⟩ of system state changes Δ ⊆ C_OT 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 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 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 O by mapping it to a set of state changes and a set of follow-up events:

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

with Δ₁ = { ws1.waitingParts.push( a.part)} and FE₁ = {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 NE ⊆ E, which is the set of all imminent events with minimal occurrence time;

   2. processing all next events e ∈ NE by applying the event rules r ∈ R triggered by them to the current system state O according to

      r_e( O ) = ⟨ Δ_e , FE_e ⟩

      resulting in a set of state changes Δ = ∪ {Δ_e | e ∈ NE } and a set of follow-up events FE = ∪ {FE_e | e ∈ NE }.

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

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.