Simulation and numerical solution of stochastic Petri nets with discrete and continuous timing.

摘要

We introduce a novel stochastic Petri net formalism where discrete and continuous phase-type firing delays can appear in the same model. By capturing deterministic and generally random behavior in discrete or continuous time, as appropriate, the formalism affords higher modeling fidelity and efficiencies to use in practice. We formally specify the underlying stochastic process as a general state space Markov chain and show that it is regenerative, thus amenable to renewal theory techniques to obtain steady-state solutions. We present two steady-state analysis methods depending on the class of problem: one using exact numerical techniques, the other using simulation. Although regenerative structures that ease steady-state analysis exist in general, a noteworthy problem class arises when discrete-time transitions are synchronized. In this case, the underlying process is semi-regenerative and we can employ Markov renewal theory to formulate exact and efficient numerical solutions for the stationary distribution. We propose a solution method that shows promise in terms of time and space efficiency. Also noteworthy are the computational tradeoffs when analyzing the “embedded” versus the “subordinate” Markov chains that are hidden within the original process. In the absence of simplifying assumptions, we propose an efficient regenerative simulation method that identifies hidden regenerative structures within continuous state spaces. The new formalism and solution methods are demonstrated with two applications.