Themethod of stochastic state classes approaches the analysis of Generalised SemiMarkov Processes (GSMPs) through the symbolic derivation of probability density functions over supports described by Difference Bounds Matrix (DBM) zones. This makes steady state analysis viable, provided that at least one regeneration point is visited by every cyclic behaviour of the model. We extend the approach providing a way to derive transient probabilities. To this end, stochastic state classes are extendedwith a supplementary timer that enables the symbolic derivation of the distribution of time at which a class can be entered. The approach is amenable to efficient implementation when model timings are given by expolynomial distributions, and it can be applied to perform transient analysis of GSMPs within any given time bound. In the special case of models underlying a Markov Regenerative Process (MRGP), the method can also be applied to the symbolic derivation of local and global kernels, which in turn provide transient probabilities through numerical integration of generalised renewal equations. Since much of the complexity of this analysis is due to the local kernel, we propose a selective derivation of its entries depending on the specific transient measure targeted by the analysis. © 2011 Elsevier B.V. All rights reserved.
15 Figures and Tables
Fig. 1. The pseudo-code describes the construction of the transient stochastic tree rooted in Σ0 with approximation ϵ ≥ 0 within time x. The next node added to the tree is the one with highest reaching probability.
Table 1 Symbols and notation of transient stochastic state classes.
Fig. 2. Petri net representation of the preemptive G/G/1/2/2 queue. All transitions have firing times distributed uniformly on the interval [1, 2].
Fig. 3. Transient probabilities of the 4 markings reachable in the preemptive G/G/1/2/2 queue.
Fig. 4. Transient probabilities of the 4 markings reachable in the preemptive G/G/1/2/2 queue with firing intervals enlarged to [0, 2], using threshold ϵ = 0.1.
Fig. 5. Transient probabilities of marking p2p4 in the preemptive G/G/1/2/2 queue with firing intervals enlarged to [0, 2] using thresholds 0.1, 0.2 and 0.3.
Fig. 6. The pseudo-code describes the computation of local and global kernel from an initial class Σ0 with approximation ϵ ≥ 0 within time x.
Fig. 7. Petri net representation of the modified G/G/1/2/2 preemptive queue.
Fig. 8. Transient probabilities of the 4 markings reachable in the modified G/G/1/2/2 queue for two different time scales.
Fig. 9. Transientmarking probabilities of G/G/1/2/2 preemptive queue, computedwith approximate kernels, L̂ij(t) and Ĝij(t), for different approximation thresholds: (a) ϵ = 0.01, 25 enumerated classes; (b) ϵ = 0.0001, 36 enumerated classes.
Fig. 10. Transient probabilities of markings p1p3 (left) and p2p3 (right): exact values, approximation with non-defective kernels (ϵ = 0.01) and approximation with defective kernels (ϵ = 0.01).
Fig. 11. Petri netmodelling a systemwith two production cells. E(0.3) denotes an exponential transitionwith rate 0.3 and all other transitions are uniform on the indicated interval.
Fig. 12. Probability of having reached double failure at least once as function of time for two different time scales.
Fig. 13. Probability of being in double failure as function of time for two different time scales.
Fig. 14. A trivial model to illustrate the calculations.
Download Full PDF Version (Non-Commercial Use)