Phantom Harmonic Gradient Estimators for Nonpreemptive Priority Queueing Systems

This paper presents a new gradient estimator for the steady-state expected sojourn (system) time in a nonpreemptive priority queueing system. The estimator uses the concept of a phantom system, together with the basic ideas in harmonic gradient estimation, to develop a single simulation run estimator, termed the phantom harmonic gradient (PHG) estimator. The estimator is shown to be strongly consistent and strongly consistent in the average sense as the sample size grows. An upper bound for the variance of the PHG estimator is presented. This bound is used to show that under mild conditions, the variance of the PHG estimator tends to zero as both the number of phantom systems and the sample size approach infinity. A variance-reduction technique that simultaneously uses both common and antithetic random numbers is presented. Computational results on several nonpreemptive queueing systems illustrate the effectiveness of the method and show that common and antithetic random numbers can be used simultaneously to reduce the variance of the phantom harmonic gradient estimator.