Discrete Event Simulations

Under the hood of Abridged Petri Net (APN) tool there are good old discrete event simulations (DES). DES have a venerable past and some very smart folks stand at their origins (e.g., Harry Markowitz and Donald Knuth). The discussion on this page informally follows Tutorial presented at the last Winter Simulation Conference. Please refer to this paper for the references.

Discrete Event Simulation (DES) rely on sample paths (state trajectories). These state trajectories describe the evolution of the the modeled system in time. Due to the presence of non-deterministic effects, multiple replications of the indivudual trajectories are required to understand the system's behavior.

Simulations can be distinguished by their "world view". The following three views are generally considered: process interaction, activity scanning, and event scheduling. The latter two views are related to the actual algorithms implemented in modern simulation software (the "back end"). In contrast, the process-interaction view can be considered as a front end of simulation that needs to be converted to a back-end view. The activity-scanning world view corresponds to the listening mode in computer languages, and is relevant in the presence of exogenous events, the timing of which cannot be predicted in advance. However, in the context of stochastic simulation, candidate future events are usually internally generated, and as a result, the event-scheduling view generally provides signifiant computational advantages compared to the activity-scanning view.

The process-interaction view underpins the vast majority of modern DES software. Reflecting the manufacturing applications' heritage, the underlying idea is to model flows of entities through a network of servers that transform those entities (transactions) by changing their attributes. A certain degree of hierarchical (top-down) perspective is inherent in this view: there are transient low-level entities (jobs or transactions) and higher system-level persistent entities (such as resources and servers).

In contrast, in Stochastic Petri Nets (SPNs) the system is comprised of individual components (entities) that can change their states, thus triggering or preventing the state changes of other entities. In other words, SPNs are based on local (peer-to-peer or bottom-up) interactions among entities, and the concepts of resources and queues are derived, rather than being fundamental properties, as they represent specific examples of coordination (interaction) among individual entities. Adopting the language of agent-based simulation, models utilize the point of view of "agent activities" rather than business processes, and as such can be considered a particular restricted type of agent-based models. Here an activity is interpreted as a time delay between state transitions for a given entity (agent).

Another related viewpoint considers traditional DES as primarily designed to deal with so-called "transformational" systems, where the entities are transformed (processed). These systems are contrasted with "reactive" systems, where the entities are event driven and continuously reacting to external and internal stimuli; here the non-hierarchical, peer-to-peer nature of SPNs is more appropriate.

There is a lack of consistency in assigning Petri nets to a world view. It seems logical, however, to view Petri nets as a local, component-based equivalent of Markov chains, both providing state-based world views. This is consistent with the view of building blocks of DES as a set of state variables that characterize the modeled system and events (points in time when at least one of those state variables changes), with the assumption that no changes to the system occur between those events.

An analogy can be drawn between the global-local juxtaposition in stochastic state-space modeling (Markov chains vs SPNs) and in simulation (traditional process-focused DES vs. agent-based modeling). As commercial tools evolve to satisfy the needs of today's customers, the boundaries between the frameworks are blurred, and traditional DES frameworks allow the modeling of some agent-based behavior. In particular, state-space representation is utilized for persistent entities (such as resources), albeit without standard graphical means to depict the dynamic interactions of such entities.