IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v30y2018i1p71-89.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Ni Ma & Ward Whitt, 2018. "A Rare-Event Simulation Algorithm for Periodic Single-Server Queues," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 71-89, February.
    • Handle: RePEc:inm:orijoc:v:30:y:2018:i:1:p:71-89
    DOI: 10.1287/ijoc.2017.0766
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2017.0766
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2017.0766?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Amarjit Budhiraja & Chihoon Lee, 2009. "Stationary Distribution Convergence for Generalized Jackson Networks in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 34(1), pages 45-56, February.
    2. William A. Massey & Ward Whitt, 1994. "Unstable Asymptomatics for Nonstationary Queues," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 267-291, May.
    3. Ira Gerhardt & Barry L. Nelson, 2009. "Transforming Renewal Processes for Simulation of Nonstationary Arrival Processes," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 630-640, November.
    4. Søren Asmussen & Tomasz Rolski, 1994. "Risk Theory in a Periodic Environment: The Cramér-Lundberg Approximation and Lundberg's Inequality," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 410-433, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yongkyu Cho & Young Myoung Ko, 2020. "Stabilizing the virtual response time in single-server processor sharing queues with slowly time-varying arrival rates," Annals of Operations Research, Springer, vol. 293(1), pages 27-55, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ward Whitt & Jingtong Zhao, 2017. "Many‐server loss models with non‐poisson time‐varying arrivals," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(3), pages 177-202, April.
    2. Ran Liu & Michael E. Kuhl & Yunan Liu & James R. Wilson, 2019. "Modeling and Simulation of Nonstationary Non-Poisson Arrival Processes," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 347-366, April.
    3. Chang Cao & J. G. Dai & Xiangyu Zhang, 2022. "State space collapse for multi-class queueing networks under SBP service policies," Queueing Systems: Theory and Applications, Springer, vol. 102(1), pages 87-122, October.
    4. Yang Miao & Kristina P. Sendova, 2024. "Advantages of Accounting for Stochasticity in the Premium Process," Risks, MDPI, vol. 12(10), pages 1-25, October.
    5. Ari Arapostathis & Hassan Hmedi & Guodong Pang, 2021. "On Uniform Exponential Ergodicity of Markovian Multiclass Many-Server Queues in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 772-796, May.
    6. Xin Liu, 2019. "Diffusion approximations for double-ended queues with reneging in heavy traffic," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 49-87, February.
    7. Song‐Hee Kim & Ward Whitt, 2014. "Choosing arrival process models for service systems: Tests of a nonhomogeneous Poisson process," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(1), pages 66-90, February.
    8. Ward Whitt & Wei You, 2020. "Heavy-traffic limits for stationary network flows," Queueing Systems: Theory and Applications, Springer, vol. 95(1), pages 53-68, June.
    9. Yongkyu Cho & Young Myoung Ko, 2020. "Stabilizing the virtual response time in single-server processor sharing queues with slowly time-varying arrival rates," Annals of Operations Research, Springer, vol. 293(1), pages 27-55, October.
    10. Nasr, Walid W. & Elshar, Ibrahim J., 2018. "Continuous inventory control with stochastic and non-stationary Markovian demand," European Journal of Operational Research, Elsevier, vol. 270(1), pages 198-217.
    11. Chihoon Lee & Amy R. Ward & Heng-Qing Ye, 2021. "Stationary distribution convergence of the offered waiting processes in heavy traffic under general patience time scaling," Queueing Systems: Theory and Applications, Springer, vol. 99(3), pages 283-303, December.
    12. Yang, Feng & Liu, Jingang, 2012. "Simulation-based transfer function modeling for transient analysis of general queueing systems," European Journal of Operational Research, Elsevier, vol. 223(1), pages 150-166.
    13. Hassan Hmedi & Ari Arapostathis & Guodong Pang, 2022. "Uniform stability of some large-scale parallel server networks," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 509-552, December.
    14. Anton Braverman, 2020. "Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1069-1103, August.
    15. Zhong, Zhiheng & Cao, Ping, 2023. "Balanced routing with partial information in a distributed parallel many-server queueing system," European Journal of Operational Research, Elsevier, vol. 304(2), pages 618-633.
    16. Amarjit Budhiraja & Xin Liu, 2012. "Stability of Constrained Markov-Modulated Diffusions," Mathematics of Operations Research, INFORMS, vol. 37(4), pages 626-653, November.
    17. Li, Yaohan & Dong, You & Qian, Jing, 2020. "Higher-order analysis of probabilistic long-term loss under nonstationary hazards," Reliability Engineering and System Safety, Elsevier, vol. 203(C).
    18. Itai Gurvich, 2014. "Validity of Heavy-Traffic Steady-State Approximations in Multiclass Queueing Networks: The Case of Queue-Ratio Disciplines," Mathematics of Operations Research, INFORMS, vol. 39(1), pages 121-162, February.
    19. Ma, Ni & Whitt, Ward, 2016. "Efficient simulation of non-Poisson non-stationary point processes to study queueing approximations," Statistics & Probability Letters, Elsevier, vol. 109(C), pages 202-207.
    20. Heng-Qing Ye & David D. Yao, 2016. "Diffusion Limit of Fair Resource Control—Stationarity and Interchange of Limits," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1161-1207, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:30:y:2018:i:1:p:71-89. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.