A Rare-Event Simulation Algorithm for Periodic Single-Server Queues
INFORMS Journal on Computing · 2018 · Volume 30 · Issue 1
Abstract
An efficient algorithm is developed to calculate the periodic steady-state distribution and moments of the remaining workload W y at time yc within a cycle of length c , 0 ≤ y < 1, in a single-server queue with a periodic arrival-rate function. The algorithm applies exactly to the GI t /GI/ 1 model, where the arrival process is a time-transformation of a renewal process. A new representation of W y makes it possible to apply a modification of the classic rare-event simulation for the stationary GI/GI/ 1 model exploiting importance sampling using an exponential change of measure. We establish bounds between the periodic workload and the stationary workload with the average arrival rate that enable us to prove that the relative error in estimates of P(W y > b) is uniformly bounded in b . With the aid of a recent heavy-traffic limit theorem, the algorithm also applies to compute the periodic steady-state distribution of (i) reflected periodic Brownian motion (RPBM) by considering appropriately scaled GI t /GI/ 1 models and (ii) a large class of general G t /G/ 1 queues by approximating by GI t /GI/ 1 models with the same heavy-traffic limit. Simulation examples demonstrate the accuracy and efficiency of the algorithm for both GI t /GI/ 1 queues and RPBM. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0766 .
Keywords
periodic queues, ruin probabilities, rare-event simulation, exponential change of measure, heavy traffic, reflected periodic Brownian motion
Enable JavaScript for citation tools and additional paper interactions.