Chapter 1. Basic Concepts

1.1. What Is Discrete Event Simulation?

The term Discrete Event Simulation (DES) has been established as an umbrella term subsuming various kinds of computer simulation approaches, all based on the general idea of modeling entities/objects and events. In the DES literature, it is often stated that DES is based on the concept of entities flowing through the system (more precisely, through a queueing network). This is the paradigm of an entire class of simulation software in the tradition of GPSS (Gordon, 1961) and SIMAN/Arena (Pegden & Davis, 1992). However, this paradigm characterizes a special (yet important) class of DES only, it does not apply to all discrete event systems.

Pegden (2010) explains that the 50 year history of DES has been shaped by three fundamental paradigms: Markowitz, Hausner and Karr (1962) pioneered the Event-Based Simulation paradigm with SIMSCRIPT, Gordon (1961) pioneered the Processing Network paradigm[1] with GPSS, and Dahl and Nygaard (1967) pioneered Object-Orientation and the (co-routine-based) Process Interaction paradigm with Simula.

While the concept of an event is often limited to instantaneous events in the area of DES, the general concept of an event, as discussed in philosophy and in many fields of computer science, includes composite events and events with non-zero duration.

A discrete event system (or discrete dynamic system) consists of

• objects (of various types) having a state (consisting of qualities) and dispositions, and
• events (of various types) triggering certain dispositions of objects participating in them,

such that the states of affected objects may be changed by events according to the dispositions triggered by them. It is natural to consider the concept of discrete events, occurring at times from a discrete set of time points.

For modeling a discrete event system as a state transition system, we have to describe its

1. object types , e.g., in the form of classes of an object-oriented language;
2. event types , e.g., in the form of classes of an object-oriented language;
3. causal regularities (disposition types) e.g., in the form of event rules.

Any DES formalism has one or more language elements that allow specifying event rules representing causal regularities. These rules specify, for any event type, the state changes of objects and the follow-up events caused by the occurrence of an event of that type, thus defining the dynamics of the transition system. Unfortunately, this is often obscured by the standard definitions of DES that are repeatedly presented in simulation textbooks and tutorials.

According to Pegden (2010), a simulation modeling worldview provides a framework for defining a system in sufficient detail that it can be executed to simulate the behavior of the system. It must precisely define the dynamic state transitions that occur over time. Pegden explains that the 50 year history of DES has been shaped by three fundamental paradigms: Markowitz, Hausner, and Karr (1962) pioneered the event worldview with SIMSCRIPT, Gordon (1961) pioneered the processing network worldview with GPSS, and Dahl and Nygaard (1966) pioneered the object worldview with Simula. Pegden characterizes these paradigms in the following way:

Event worldview: The system is viewed as a series of instantaneous events that change the state of the system over time. The modeler defines the events in the system and models the state changes that take place when those events occur. According to Pegden, the event worldview is the most fundamental worldview since the other worldviews also use events, at least implicitly.

Processing Network worldview: The system under investigation is described as a processing network where entities flow through the system (or, more precisely, work objects are routed through the network) and are subject to a series of processing steps performed at processing nodes through processing activities, possibly requiring resources and inducing queues of work objects waiting for the availability of resources (processing networks have been called queueing networks in Operations Research). This approach allows high-level modeling with semi-visual languages and is therefore the most widely used DES approach nowadays, in particular in manufacturing industries and service industries. Simulation platforms based on this worldview may or may not support object-oriented modeling and programming.

Object worldview: The system is modeled by describing the objects that make up the system. The system behavior emerges from the interaction of these objects.

All three worldviews lack important conceptual elements. The event worldview does not consider objects with their (categorical and dispositional) properties. The processing network worldview neither considers events nor objects. And the object worldview, while it considers objects with their categorical properties, does not consider events. None of the three worldviews includes modeling the dispositional properties of objects with a full-fledged explicit concept of event rules.

The event worldview and the object worldview can be combined in approaches that support both objects and events as first-class citizens. This seems highly desirable because (1) objects (and classes) are a must-have in today’s state-of-the-art modeling and programming, and (2) a general concept of events is fundamental in DES, as demonstrated by the classical event worldview. We use the term object-event worldview for any DES approach combining OO modeling and programming with a general concept of events.

1.2. Object Event Modeling and Simulation

Object Event (OE) Modeling and Simulation (M&S) is a new general modeling paradigm based on the two most important ontological categories: objects and events. In philosophy, objects have also been called endurants or continuants, while events have also been called perdurants or occurrents.

OEM&S combines Object-Oriented (OO) Modeling with the event scheduling paradigm of Event Graphs (Schruben 1983). The relevant object types and event types are described in an information model, which is the basis for making a process model. A modeling approach that follows the OEM paradigm is called an OEM approach. Such an approach needs to choose, or define, an information modeling language (such as Entity Relationship Diagrams or UML Class Diagrams) and a process modeling language (such as UML Activity Diagrams or BPMN Process Diagrams).

We propose an OEM approach based on Object Event (OE) Class Models (a form of UML Class Diagrams) for conceptual information modeling and information design modeling, as well as DPMN Process Diagrams for conceptual process modeling and for process design modeling.

In the proposed approach, object types and event types are modeled as special categories of classes in an OE Class Diagram. Random variables are modeled as a special category of class-level operations constrained to comply with a specific probability distribution such that they can be implemented as static methods of a class. Queues are not modeled as objects, but rather as ordered association ends, which can be implemented as collection-valued reference properties. Finally, event rules, which include event routines, are modeled in DPMN process diagrams (and possibly also in pseudo-code), such that they can be implemented in the form of special onEvent methods of event classes.

Like Petri Nets (Petri 1962) and DEVS (Zeigler 1976), OEM&S has a formal semantics. But while Petri Nets and DEVS are abstract computational formalisms without an ontological foundation, OEM&S is based on the fundamental ontological categories of objects, events and causal regularities.

In model-based simulation engineering, we distinguish between (1) a conceptual model describing a real-world problem domain, and (2) a simulation design model defining a certain computational solution for the purpose of a simulation study. Both conceptual models and design models consist of an OE class model describing/defining the system's state structure (in the form of object types and event types, and the associations between them) and a DPMN process model describing/defining the system's dynamics (in the form of causal regularities captured by event rules).

An OEM approach results in a simulation design model that can, in principle, be implemented with any object-oriented simulation technology. However, a straightforward implementation can only be expected from a technology that implements the OEM&S paradigm, such as the OES JavaScript (OESjs) framework.

The formal semantics of OEM/DPMN is based on the semantics of Event Graphs (Schruben 1983), which was originally defined in terms of integer programming. Wagner (2017a) has proposed a more general semantics of Event Graphs where such a graph is decomposed into a set of transition functions ("event rules") such that a transition system (or Abstract State Machine) semantics is obtained. This semantics can be easily extended to Object Event Graphs, as shown in Wagner (2017a). Finally, the semantics of DPMN-A models ("Activity Networks") is obtained by reduction to Object Event Graphs using two rewriting patterns, and the semantics of DPMN-PN models ("Processing Networks") is obtained by reduction to DPMN-A.

It has been an unfortunate course of the history of science that Event Graphs have not become more well-known and, instead of Event Graphs, Petri Nets have been chosen as the standard semantics of BP models, despite the fact that Event Graphs would have been a much more natural choice.

1.3. Model-Driven Engineering

Model-Driven Engineering (MDE), also called model-driven development, is a well-established paradigm in software engineering. Since simulation engineering can be viewed as a special case of software engineering, it is natural to apply the ideas of MDE also to simulation engineering.

In MDE, there is a distinction between three kinds of models as engineering artifacts created in the analysis, design and implementation phases of a development project:

1. domain models (also called conceptual models), which describe a real-world domain (and are independent of a computational solution),
2. design models, which define platform-independent solution designs,
3. implementation models, which are platform-specific.

Domain models are solution-independent descriptions of a problem domain produced in the analysis phase. A domain model may include both descriptions of the domain's state structure (in conceptual information models) and descriptions of its processes (in conceptual process models). They are solution-independent, or computation-independent, in the sense that they are not concerned with making any system design choices or with other computational issues. Rather, they focus on the perspective and language of the subject matter experts for the domain under consideration.

In the design phase, first a platform-independent design model, as a general computational solution, is developed on the basis of the domain model. The same domain model can potentially be used to produce a number of (even radically) different design models. Then, by taking into consideration a number of implementation issues ranging from architectural styles, nonfunctional quality criteria to be maximized (e.g., performance, adaptability) and target technology platforms, one or more platform-specific implementation models are derived from the design model. These one-to-many relationships between conceptual models, design models and implementation models are illustrated in Figure 1-1.

In general, a model does not consist of just one model diagram including all viewpoints or aspects of the system to be developed. Rather it consists of a set of models, one (or more) for each viewpoint. The two most important viewpoints, crosscutting all three modeling levels (domain conceptualization, design and implementation) are

1. information modeling, which is concerned with the state structure of the domain, design or implementation;
2. process modeling, which is concerned with the dynamics of the domain, design or implementation.

Examples of widely used languages for information modeling are Entity Relationship (ER) Diagrams and UML Class Diagrams. Since the latter subsume the former, we prefer using UML class diagrams for making all kinds of information models, including SQL database models.

Examples of widely used languages for process modeling are (Colored) Petri Nets, UML Sequence Diagrams, UML Activity Diagrams and the BPMN. Notice that there is more agreement on the right concepts for information modeling than for process modeling, as indicated by the much larger number of different process modeling languages. This reflects a lower degree of understanding the nature of events and processes compared to understanding objects and their relationships.

Model-driven simulation engineering is based on the same kinds of models as model-driven software engineering: going from a domain model via a design model to an implementation model for the simulation platform of choice (or to several implementation models if there are several target simulation platforms). The specific concerns of simulation engineering, like, e.g., the concern to capture certain parts of the overall system dynamics with the help of random variables, do not affect the applicability of MDE principles. However, they define requirements for the modeling languages to be used.