A Rare-Event Simulation Algorithm for Periodic Single-Server Queues

Ni Ma () and Ward Whitt ()
Additional contact information
Ni Ma: Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Ward Whitt: Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

INFORMS Journal on Computing, 2018, vol. 30, issue 1, 71-89

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.

Keywords: periodic queues; ruin probabilities; rare-event simulation; exponential change of measure; heavy traffic; reflected periodic Brownian motion (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0766 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:71-89

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().