Stochastic Petri Nets

Predicting the performance of a computer, manufacturing, telecommunication, workflow, or transportation system is almost always a challenging task. Such a system usually comprises multiple activities or processes that proceed concurrently. In a typical computer workstation, for example, the storage subsystem writes data to a disk while, at the same time, one or more CPUs perform computations and a keyboard transmits characters to a buffer. Activities often have precedence relationships: assembly of a part in a manufacturing cell does not begin until assembly of each of its subparts has completed. Moreover, specified activities may be synchronized in that they must always start or terminate at the same time. Activities frequently compete for limited resources, and one activity may have either preemptive or nonpreemptive priority over another activity for use of a resource. To further complicate matters, many of the component processes of a system—such as the arrival process of calls to a telephone network—are random in nature. Because of this complexity and randomness, developing mathematical models of the system under study is usually nontrivial. The standard “network of queues” modelling framework, for example, can fail to capture complex synchronization behavior or precedence constraints. Assessment of system performance is equally difficult. Models that are accurate enough to adequately represent system behavior often cannot be analyzed using, for example, methods based on the theory of continuous-time Markov chains on a finite or countably infinite state space.

Stochastic Petri nets (SPNs) are well suited to representing concurrency, synchronization, precedence, and priority. After presenting the basic SPN building blocks in Section 2.1, we give a series of examples in Section 2.2 that illustrates the use of SPNs for modelling discrete-event systems. We pay particular attention to complications that arise in the specification of new-marking probabilities. These probabilities determine the mechanism by which a transition removes tokens from a random subset of its normal input places and deposits tokens in a random subset of its output places when it fires. Consideration of a queueing system with batch arrivals shows that new-marking probabilities must be allowed to depend explicitly on the current marking; that is, the SPN formalism must include marking-dependent transitions. By means of an example, we show how new-marking probabilities for an SPN with marking-dependent transitions can be specified in a form suitable for processing by a computer program. Another complication arises when more than one transition can fire at a time point. In principle, new-marking probabilities must be defined for all possible sets of simultaneously firing transitions, and there can be an extremely large number of such sets. As shown in Section 2.3, concise specification of new-marking probabilities can be facilitated by assigning numerical “priorities” to transitions.

The marking process of an SPN records the marking as it evolves over continuous time. As discussed in Section 3.1, formal definition of the marking process is in terms of an underlying general state-space Markov chain that describes the net at successive marking changes. This definition leads to an algorithm for generating sample paths of the process.

The marking process of an SPN must be stable for time-average limits to be well defined and for simulation-based estimation techniques to be applicable. Although nontrivial, establishing stability properties for a specified SPN is therefore a key step in a methodologically sound simulation study.

A regenerative stochastic process has the characteristic property that there exists an infinite sequence of random times at which the process probabilistically restarts. As discussed in Section 6.1, the essence of regeneration is that the evolution of the process between any two successive regeneration points is an independent probabilistic replica of the process in any other such “cycle.” Under mild regularity conditions, time-average limits for a regenerative process are well defined and finite, provided that the regenerative cycle length has finite mean. The value of a time-average limit is determined by the expected behavior of the process in a single regenerative cycle—a fact that has important implications for simulation analysis. Under some additional regularity conditions, the time-average limit can also be interpreted as a steady-state or limiting mean. Most of these results extend to the setting of “od-equilibrium” and “od-regenerative” processes. Such processes are similar to regenerative processes in that sample paths can be decomposed into identically distributed cycles, but differ in that adjacent cycles need not be independent.

The previous chapter concerns SPNs in which regeneration points exist for the marking process or underlying chain or both. For such nets, regenerative methods often can be used to obtain strongly consistent point estimates and asymptotic confidence intervals for time-average limits of the form \(r\, = \,\text{lim}_{\text{t} \to \infty } \bar r\left( t \right),\) where \(\bar r\left( t \right)\, = \,(1/t)\,\int\limits_0^t f (X(u))\) du for some function f. This chapter deals with methods for estimation of time-average limits when regenerative methods are not applicable. This situation can occur either because there is no apparent sequence of regeneration points or because regenerations occur so infrequently that the method is impractical—in Section 7.1 we give examples of both types of scenario.

Our discussion up to this point has centered around performance measures that can be expressed as time-average limits—or functions of time-average limits—that involve the marking process or underlying chain of an SPN. Such measures include long-run system reliability, availability, and cost, as well as throughput and discounted cost. Assessment of computer, communication, manufacturing, and transportation systems, however, often involves analysis of long-run delay characteristics. Examples of such characteristics include the long-run average time to produce an item in a flexible manufacturing system, the long-run fraction of queries in a database system that require more than a specified amount of time to compute, and the long-run average revenue generated by telephone traffic under a graduated rate structure. When the system of interest is modelled as an SPN, each of these latter characteristics can be expressed as a time-average limit of the form \(\text{lim}_{\text{t} \to \infty } (1\backslash n)\,\sum\limits_{j = 0}^{n - 1} f (D_j ),\) where f is a real-valued function and D ₀, D ₁,… is a sequence of delays determined by the marking changes of the net. Other delay characteristics—such as the long-run variability in the time required to transmit a message packet from one node to another in a communication network—can be expressed as functions of time-average limits. As with time-average limits defined in terms of the marking process, time-average limits defined in terms of delays often cannot be computed analytically or numerically, but must be estimated using simulation.

Use of the standard set of SPN building blocks to model very large or complex systems can sometimes result in nets that have an enormous number of places and transitions. One popular strategy for obtaining more concise specifications in such cases is to associate “colors” with both tokens and transitions and to work with “colored stochastic Petri nets” (CSPNs). This approach is especially effective when the system under study is composed of many subsystems having a similar structure or behavior.