What Are Event Graphs?
Event Graphs (EGs) have been proposed as a diagram language for making Event-Based Simulation models by Schruben (1983). A node E in an EG is visually rendered as a circle and represents a typed event variable (such that the node name E is the name of the associated event type). An event circle may be annotated with state change statements in the form of state variable assignments. 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 Event-Based Simulation 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.
Schruben's original notation for EGs used above can be improved in the following way:
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, EGs are a rather low-level DES modeling language: they do not support object-oriented state structure modeling (with attributes of objects taking the role of state variables) and they do not support the concept of activities.
See also:
- The SIGMA website, for getting the SIGMA book and downloading the SIGMA Event Graph simulator.
- When to use an Event Graph, blog post of the simulation consulting company MOSIMTEC.
- Events and Event Graphs, a section in Charles R. Standridge's book Beyond Lean - Simulation in Practice.
- Object Event Modeling and Simulation, a (free) book explaining how to incrementally extend Event Graphs by adding objects and activities resulting in Object Event Graphs and Activity Networks.