A Rare-Event Simulation Algorithm for Periodic Single-Server Queues
针对周期到达率的单服务器队列，提出一种高效算法计算剩余工作量的周期稳态分布和矩，利用指数测度变换的重要性采样实现稀有事件仿真，并证明估计的相对误差一致有界。
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 .