×

A rare-event simulation algorithm for periodic single-server queues. (English) Zbl 1446.90063

Summary: 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 \leq 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.

MSC:

90B22 Queues and service in operations research
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
60J65 Brownian motion
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abate J, Whitt W (1998) Calculating transient characteristics of the Erlang loss model by numerical transform inversion. Stochastic Models 15(3):223-230.Google Scholar · Zbl 0905.60071
[2] Abate J, Choudhury GL, Whitt W (1993) Calculation of the GI/G/1 steady-state waiting-time distribution and its cumulants from Pollaczek’s formula. Archiv fur Elektronik Übertragungstechnik 47(5):311-321.Google Scholar
[3] Abate J, Choudhury GL, Whitt W (1994) Asymptotics for steady-state tail probabilities in structured Markov queueing models. Stochastic Models 10(1):99-143.Crossref, Google Scholar · Zbl 0801.60082 · doi:10.1080/15326349408807290
[4] Asmussen S (2003) Applied Probability and Queues, 2nd ed. (Springer, New York).Google Scholar · Zbl 1029.60001
[5] Asmussen S, Albrecher H (2010) Ruin Probabilities, 2nd ed. (World Scientific, Singapore).Crossref, Google Scholar · doi:10.1142/7431
[6] Asmussen S, Glynn PW (2007) Stochastic Simulation, 2nd ed. (Springer, New York).Google Scholar · Zbl 1126.65001
[7] Asmussen S, Rolski T (1994) Risk theory in a periodic environment: The Cramer-Lundberg approximation and Lundberg’s inequality. Math. Oper. Res. 19(2):410-433.Link, Google Scholar · Zbl 0801.60091
[8] Budhiraja A, Lee C (2009) Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34(1):45-56.Link, Google Scholar · Zbl 1214.60013
[9] Choudhury GL, Lucantoni DM, Whitt W (1996) Squeezing the most out of ATM. IEEE Trans. Comm. 44(2):203-217.Crossref, Google Scholar · doi:10.1109/26.486613
[10] Choudhury GL, Mandelbaum A, Reiman MI, Whitt W (1997) Fluid and diffusion limits for queues in slowly changing random environments. Stochastic Models 13(1):121-146.Crossref, Google Scholar · Zbl 0871.60070 · doi:10.1080/15326349708807417
[11] Ethier SN, Kurtz TG (1986) Markov Processes: Characterization and Convergence (Wiley, New York).Crossref, Google Scholar · Zbl 0592.60049 · doi:10.1002/9780470316658
[12] Falin GI (1989) Periodic queues in heavy traffic. Adv. Appl. Probab. 21(2):485-487.Crossref, Google Scholar · Zbl 0668.60082 · doi:10.2307/1427175
[13] Feller W (1971) An Introduction to Probability Theory and Its Applications, 2nd ed. (John Wiley, New York).Google Scholar · Zbl 0219.60003
[14] Gerhardt I, Nelson BL (2009) Transforming renewal processes for simulation of nonstationary arrival processes. INFORMS J. Comput. 21(4):630-640.Link, Google Scholar · Zbl 1243.60068
[15] Glynn PW, Whitt W (1994) Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. Galambos J, Gani J, eds. Studies in Applied Probability, Papers in Honour of Lajos Takacs (Applied Probability Trust, Sheffield, UK), 131-156.Google Scholar · Zbl 0805.60093
[16] Harrison JM, Lemoine AJ (1977) Limit theoorems for periodic queues. J. Appl. Probab. 14(3):566-576.Crossref, Google Scholar · Zbl 0372.60127 · doi:10.2307/3213459
[17] He B, Liu Y, Whitt W (2016) Staffing a service system with non-Poisson nonstationary arrivals, probability in the engineering and informational sciences. Probab. Engrg. Inform. Sci. 30(4):593-621.Crossref, Google Scholar · Zbl 1370.90135 · doi:10.1017/S026996481600019X
[18] Iglehart DL, Whitt W (1970) Multiple channel queues in heavy traffic, II: Sequences, networks and batches. Adv. Appl. Probab. 2(2):355-369.Crossref, Google Scholar · Zbl 0206.22503 · doi:10.2307/1426324
[19] Jacod J, Shiryaev AN (1987) Limit Theorems for Stochastic Processes (Springer, New York).Crossref, Google Scholar · Zbl 0635.60021 · doi:10.1007/978-3-662-02514-7
[20] Lemoine AJ (1981) On queues with periodic Poisson input. J. Appl. Probab. 18(4):889-900.Crossref, Google Scholar · Zbl 0472.60084 · doi:10.2307/3213063
[21] Lemoine AJ (1989) Waiting time and workload in queues with periodic Poisson input. J. Appl. Probab. 26(2):390-397.Crossref, Google Scholar · Zbl 0683.60069 · doi:10.2307/3214044
[22] Loynes R (1962) The stability of a queue with non-independent inter-arrival and service times. Math. Proc. Cambridge Philos. Soc. 58(3):497-520.Crossref, Google Scholar · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[23] Ma N, Whitt W (2015) Efficient simulation of non-Poisson non-stationary point processes to study queueing approximations. Statist. Probab. Lett. 102(1):202-207.Google Scholar · Zbl 1382.60118
[24] Ma N, Whitt W (2016) Online supplement to “a rare-event simulation algorithm for periodic single-server queues,” Columbia University. Accessed August 4, 2017, http://www.columbia.edu/˜ww2040/allpapers.html.Google Scholar
[25] Massey WA, Whitt W (1994) Unstable asymptotics for nonstationary queues. Math. Oper. Res. 19(2):267-291.Link, Google Scholar · Zbl 0801.60087
[26] Morales M (2004) On a surplus process under a periodic environment: A simulation approach. North Amer. Actuarial J. 8(4):76-89.Crossref, Google Scholar · Zbl 1085.91527 · doi:10.1080/10920277.2004.10596172
[27] Nelson BL, Gerhardt I (2011) Modeling and simulating renewal nonstationary arrival processes to facilitate analysis. J. Simulation 5(1):3-8.Crossref, Google Scholar · doi:10.1057/jos.2010.21
[28] Nieuwenhuis G (1989) Equivalence of functional limit theorems for stationary point processes and their Palm distributions. Probab. Related Fields 81(4):593-608.Crossref, Google Scholar · Zbl 0671.60025 · doi:10.1007/BF00367306
[29] Rolski T (1981) Queues with nonstationary input stream: Ross’s conjecture. Adv. Appl. Probab. 13(3):603-618.Crossref, Google Scholar · Zbl 0462.60090 · doi:10.2307/1426787
[30] Rolski T (1989) Queues with nonstationary inputs. Queueing Systems 5(1-3):113-130.Crossref, Google Scholar · Zbl 0687.60082 · doi:10.1007/BF01149189
[31] Sigman K (1995) Stationary Marked Point Processes: An Intuitive Approach (Chapman & Hall/CRC, New York).Google Scholar · Zbl 0873.60034
[32] Whitt W (1982) Approximating a point process by a renewal process I: Two basic methods. Oper. Res. 30(1):125-147.Link, Google Scholar · Zbl 0481.90025
[33] Whitt W (2002) Stochastic-Process Limits (Springer, New York).Crossref, Google Scholar · Zbl 0993.60001 · doi:10.1007/b97479
[34] Whitt W (2014) Heavy-traffic limits for queues with periodic arrival processes. Oper. Res. Lett. 42(6-7):458-461.Crossref, Google Scholar · Zbl 1408.90100 · doi:10.1016/j.orl.2014.08.001
[35] Whitt W (2015) Stabilizing performance in a single-server queue with time-varying arrival rate. Queueing Systems 81(4):341-378.Crossref, Google Scholar · Zbl 1332.60131 · doi:10.1007/s11134-015-9462-x
[36] Whitt W (2016) A Poisson limit for the departure process from a queue with many slow server. Oper. Res. Lett. 44(5):602-606.Crossref, Google Scholar · Zbl 1408.60089 · doi:10.1016/j.orl.2016.06.006
[37] Whitt W, Zhao J (2016) Staffing to stabilize blocking in loss models with non-Markovian arrivals. Columbia University, http://www.columbia.edu/˜ww2040/allpapers.html.Google Scholar
[38] Xiong Y, · Zbl 1319.60177 · doi:10.1007/s11134-014-9431-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.