One-dependent cycles and passage times in stochastic Petri nets

The lengths of certain passage-time intervals (random time intervals) in stochastic Petri nets correspond to delays in computer, communication, manufacturing, and transportation systems. Simulation is often the only available means for analyzing a sequence of such lengths. It is sometimes possible to obtain meaningful estimates for the limiting average delay indirectly, that is, without measuring lengths of individual passage-time intervals. For general time-average limits of a sequence of delays, however, it is necessary to measure individual lengths and combine them to form point and interval estimates. We consider sequences of delays determined by marking changes of the net and use a sequence of random vectors, called start vectors, to provide the link between the starts and terminations of individual passage-time intervals. This method of start vectors for measuring delays avoids the need for additional places and transitions to “tag” entities in the system. We show that whenever the marking process of a stochastic Petri net has a recurrent single-state, the sample paths of any sequence of delays can be decomposed into one-dependent, identically distributed cycles. We then show that an extension of the regenerative method for analysis of simulation output can be used to obtain meaningful point estimates and confidence intervals for time-average limits. This estimation procedure is valid not only when there are no ongoing passage times at any regeneration point but, unlike previous methods, also when the sequence of delays does not inherit regenerative structure. Application of these methods to simulation of a manufacturing flow-line with a shunt bank is discussed