Chapter 6. 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 incrementally extend Event Graphs by adding increasingly high-level modeling concepts: in the first step, we add the concept of objects, resulting in Object Event Graphs, and in the second step, we add the concept of (resource-constrained) activities, resulting in the Activity Network modeling language OEM/DPMN-AN.
6.1. 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 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_{1} := 4 or o.p_{1} := o.p_{2} where o is an object variable and p_{1}, p_{2} are property names.
A set of objects O = {o_{1}, o_{2}, ...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_{1} = {o_{1}} with o_{1} = { p_{1}: 2, p_{2}: 5} and a set of state changes Δ_{1} = { o_{1}.p_{1} := o_{1}.p_{2} } we obtain
An event expression is a term E(x)@t where
- E is an event type,
- x is a (possibly empty) list of event parameters x_{1}, x_{2}, …, x_{n} according to the signature of the event type E,
- 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) |
r_{PA} a: PartArrival | PartArrival(ws) @ t | Δ := { ws.waitingParts.push( a.part)} IF ws.status = AVAILABLE RETURN ⟨ Δ, FE ⟩ |
r_{PS} ps: ProcessingStartws: WorkStation ws := ps.workStation | ProcessingStart(ws) @ t | Δ := { ws.status := BUSY} FE := {ProcessingEnd(ws)@t + ProcessingStart.processingTime()} RETURN ⟨ Δ, FE ⟩ |
r_{PE} pe: ProcessingEndws: WorkStation ws := pe.workStation | ProcessingEnd(ws) @ t | Δ := { ws.waitingParts.pop()} IF ws.waitingParts.length > 0 RETURN ⟨ Δ, FE ⟩ |
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 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 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_{0} = {ws1.status: AVAILABLE, ws1.waitingParts: []}. We obtain
with Δ_{1} = { ws1.waitingParts.push( a.part)} and FE_{1} = {ProcessingStart@2}.
An OE model defines a state transition system where
A state is a simulation state S = ⟨t, O, E⟩.
A transition of a simulation state S consists of
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;
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.
6.2. Object Event Graphs
Object Event (OE) Graphs 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 is an Object Event Graph 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 type 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 type 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 OE Graph specifies a set of chained event rules, one rule for each event circle of the model. The above OE Graph specifies the following three event rules:
- 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.
- 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.
- 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 basic DPMN diagrams, based on the semantics of event rules as transition functions, has been presented in (Wagner 2017a). It can be shown that the basic DPMN diagram language is a conservative extension of the Event Graph diagram language by means of a homomorphic embedding of Event Graphs in DPMN diagrams.