Estimation Methods for Delays in Non-regenerative Discrete-Event Systems

Abstract

Many long-run delay characteristics of computer, communication, manufacturing, and transportation systems can be specified as time-average limits of sequences of delays in generalized semi-Markov processes (GSMPs). We consider sequences of delays that are determined from the state transitions of the GSMP using the method of start vectors. In this setting, time-average limits typically must be estimated using simulation. Previous work on estimation methods for delays has focused on GSMPs for which there exists a sequence of regeneration points. For such systems, it is often possible to find an explicit sequence of regeneration points or od-regeneration points for the sequence of delays, so that point estimates and confidence intervals for time-average limits can be obtained using the regenerative method for simulation output analysis or one of its variants. This paper is concerned with GSMPS for which this approach is not feasible, either because regeneration points for the GSMP cannot be identified or because regenerations occur too infrequently. We provide conditions on the building blocks of a GSMP and start-vector mechanism under which the sequence of delays is an od-regenerative process and cycle sums have finite moments—these conditions do not require that there exist regeneration points for the GSMP. Although in our setting the od-regeneration points for the sequence of delays usually cannot be determined explicitly, the mere existence of these points implies that time-average limits are well defined and the sequence of delays obeys a multivariate functional central limit theorem. It then follows from results of Glynn, Iglehart, and Muñoz that methods based on standardized time series can be used to obtain strongly consistent point estimates and asymptotic confidence intervals for time-average limits and functions of time-average limits. In particular, the method of batch means is applicable.

Keywords:

• Stochastic simulation
• Standardized time series
• Batch means
• Delays
• Discrete-event stochastic systems
• Generalized semi-Markov processes

Acknowledgment

The author wishes to thank Peter Glynn, the Associate Editor, and two anonymous reviewers for comments that led to various improvements in the paper.

Notes

^#Subsequent to the submission of this paper, results similar to those given here—but in the setting of stochastic Petri nets—have appeared in Ref.[2].

^{* *}Recall that a sequence {X _n :n≥1} is (strictly) stationary if (X ₁,X ₂,…,X _k ) and (X _n+1,X _n+2,…,X _n+k ) are identically distributed for all k,n≥1. The sequence is identically distributed if the preceding equality in distribution holds for k=1 and n≥1. The sequence is one-dependent if X _n+j is independent of {X ₁,X ₂,…,X _n } for each n≥1 and j>1.

^‡Although the length of each start vector V _n is always equal to N for this model, the length of the intermediate vector V′ _n is equal to N+1 whenever there is a service completion at center 2 at time ζ _n . Thus the “+2” terms in the definition of i _β (s′;s,E ^*).