Document Zbl 1312.60113

Hitting time in Erlang loss systems with moving boundaries. (English) Zbl 1312.60113

Queueing Syst. 78, No. 3, 225-254 (2014).

Summary: When the boundary – the total number of servers – in an Erlang loss system is a function of time, customers may also be lost due to boundary variations. On condition that these customers are selected independently of their history, we solve for the hitting-time distribution and transient distribution of busy servers. We derive concise asymptotic expressions in the time domain for normal loads in the heavy-traffic limit, i.e. when the offered load \(\rho \) is high, and the number of servers scales as \(\rho +O\left( \sqrt{\rho }\right) \). The solutions are computationally efficient, and simulations confirm the theoretical results.

Cited in 3 Documents

MSC:

60K25	Queueing theory (aspects of probability theory)
90B22	Queues and service in operations research
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)

Keywords:

Erlang loss systems; hitting time; first passing time; spectral decomposition; Charlier polynomial; Hermite function; diffusion; colored noise

Software:

DLMF

Cite Review PDF

Full Text: DOI

OA License

References:

[1]	Abate, J., Whitt, W.: Calculating transient characteristics of the Erlang loss model by numerical transform inversion. Stoch. Models 3, 663-680 (1998). doi:10.1080/15326349808807494 · Zbl 0905.60071 · doi:10.1080/15326349808807494
[2]	Alili, L., Patie, P., Pedersen, J.L.: Representations of the first hitting time density of an Ornstein-Uhlenbeck process. Stoch. Models 21(4), 967-980 (2005). doi:10.1080/15326340500294702 · Zbl 1083.60064 · doi:10.1080/15326340500294702
[3]	Borovkov, A.A.: Stochastic Processes in Queueing Theory. Springer, Berlin (1976) · Zbl 0319.60057 · doi:10.1007/978-1-4612-9866-3
[4]	Borovkov, A.A.: Asymptotic Methods in Queueing Theory. Wiley, New York (1984) · Zbl 0544.60085
[5]	Brockmeyer, E., Halstrøm, H.L., Jensen, A.: The life and works of A K Erlang: solution of some problems in the theory of the probabilities of significance in automatic telephone exchanges. Trans. Dan. Acad. Tech. Sci. 2, 138-155 (1948) · Zbl 0033.05101
[6]	Buonocore, A., Nobile, A.G., Ricciardi, L.M.: A new integral equation for the evaluation of first-passage-time probability densities. Adv. Appl. Prob. 19(4), 784-800 (1987). URL http://www.jstor.org/stable/1427102 · Zbl 0632.60079
[7]	Charlier, C.V.L.: Über die Darstellung willkürlicher Funktionen. Ark. mat. astron. fys. 2 (1905). · JFM 36.0460.01
[8]	Chihara, T.S.: An Introduction to Orthogonal Polynomials. No. 13 in Mathematics and its applications. Gordon and Breach, New York (1978) · Zbl 0389.33008
[9]	Cox, D.R., Miller, H.D.: The Theory of Stochastic Processes. Methuen, London (1965) · Zbl 0149.12902
[10]	Dominici, D.: Asymptotic analysis of the Askey scheme I: from Krawchouk to Charlier. Cent. Eur. J. Math. 5(2), 280-304 (2007). doi:10.2478/s11533-006-0041-6 · Zbl 1124.33008
[11]	Dunster, T.M.: Uniform asymptotic expansions for Charlier polynomials. J. Approx. Theory. 112, 93-133 (2001). doi:10.1006/jath.2001.3595 · Zbl 0991.41020 · doi:10.1006/jath.2001.3595
[12]	Durbin, J.: The first-passage density of a continuous Gaussian process to a general boundary. J. Appl. Prob. 22(1), 99-122 (1985). URL http://www.jstor.org/stable/3213751 · Zbl 0576.60029
[13]	Elbert, A., Muldoon, M.E.: Inequalities and monotonicity properties for zeros of Hermite functions. Proc. R. Soc. Edinb., Sect. A 129, 57-75 (1999). doi:10.1017/S0308210500027463 · Zbl 0944.33006 · doi:10.1017/S0308210500027463
[14]	Erdélyi, A., Magnus, W., Oberhettinger, F., Tricomi, F.G.: Higher Transcendental Functions. McGraw-Hill, New York (1953) · Zbl 0051.30303
[15]	Feinsilver, P.J.: Special Functions, Probability Semigroups, and Hamiltonian Flows Lecture Notes in Mathematics, vol. 696. Springer, Berlin (1978) · Zbl 0394.33002
[16]	Feller, W.: An Introduction to Probability Theory and its Applications, vol. 1, 3rd edn. Wiley, New York (1968) · Zbl 0155.23101
[17]	Halfin, S., Whitt, W.: Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3), 567-588 (1981). URL http://www.jstor.org/stable/170115 · Zbl 0455.60079
[18]	Hänggi, P., Jung, P.: Colored noise in dynamical systems. Adv. Chem. Phys. 89, 239-326 (1995). doi:10.1002/9780470141489.ch4 · doi:10.1002/9780470141489.ch4
[19]	Jagerman, D.: Some properties of the Erlang loss function. Bell Syst. Tech. J. 53(3), 525-551 (1974). doi:10.1002/j.1538-7305.1974.tb02756.x · Zbl 0276.60092 · doi:10.1002/j.1538-7305.1974.tb02756.x
[20]	Karlin, S., McGregor, J.: The classification of birth and death processes. Trans. Am. Math. Soc. 86(2), 366-400 (1957). URL http://www.jstor.org/stable/1993021 · Zbl 0091.13802
[21]	Karlin, S., McGregor, J.: Many server queueing processes with Poisson input and exponential service times. Pac. J. Math. 8(1), 87-118 (1958). URL http://projecteuclid.org/euclid.pjm/1103040247 · Zbl 0091.13803
[22]	Karlin, S., McGregor, J.L.: The differential equations of birth-and-death processes, and the Stieltjes moment problem. Trans. Am. Math. Soc. 85(2), pp. 489-546 (1957). URL http://www.jstor.org/stable/1992942 · Zbl 0091.13801
[23]	Kijima, M.: On the largest negative eigenvalue of the infinitesimal generator associated with \[{M}/{M}/n/n\] M/M/n/n queues. Oper. Res. Lett. 9, 59-64 (1990). doi: 10.1016/0167-6377(90)90041-3 · Zbl 0693.60082 · doi:10.1016/0167-6377(90)90041-3
[24]	Knessl, C.: On the transient behavior of the M/M/m/m loss model. Stoch. Models 6(4), 749-776 (1990). doi:10.1080/15326349908807172 · Zbl 0706.60088 · doi:10.1080/15326349908807172
[25]	Koekoek, R., Lesky, P.A., Swarttouw, R.F.: Hypergeometric Orthogonal Polynomials and Their \[q\] q-Analogues. Springer, Berlin (2010) · Zbl 1200.33012 · doi:10.1007/978-3-642-05014-5
[26]	Lebedev, N.: Special Functions and their Applications. Dover Publications, New York (1972) · Zbl 0271.33001
[27]	Ledermann, W., Reuter, G.E.H.: Spectral theory for the differential equations of simple birth and death processes. Philos. Trans. R. Soc. London 246(914), pp. 321-369 (1954). URL http://www.jstor.org/stable/91569 · Zbl 0059.11704
[28]	Lee, A.M., Longton, P.A.: Queueing processes associated with airline passenger check-in. Oper. Res. Q. 10(1), 56-71 (1959). URL http://www.jstor.org/stable/3007312
[29]	Maejima, M., van Assche, W.: Probabilistic proofs of asymptotic formulas for some classical polynomials. Math. Proc. Camb. Philos. Soc. 97, 499-510 (1985). doi:10.1017/S0305004100063088 · Zbl 0557.33006 · doi:10.1017/S0305004100063088
[30]	Mandjes, M., Ridder, A.: A large deviations approach to the transient of the Erlang loss model. Perform. Eval. 43, 181-198 (2001). doi:10.1016/S0166-5316(00)00050-X · Zbl 1053.68016 · doi:10.1016/S0166-5316(00)00050-X
[31]	Meixner, J.: Erzeugende Funktionen der Charlierschen Polynome. Math. Z. 44(1), 531-535 (1939). doi:10.1007/BF01210670 · Zbl 0019.34203 · doi:10.1007/BF01210670
[32]	Mitra, D.; Weiss, A.; Bonatti, M. (ed.), The transient behavior in Erlang’s model for large trunk groups and various traffic conditions, 1367-1374 (1988), Amsterdam
[33]	Nilsson, M.: On the transition of Charlier polynomials to the Hermite function. arXiv:1202.2557 [math.CA] (2013). URL http://arxiv.org/abs/1202.2557 · Zbl 0991.41020
[34]	Olver, F.W., Lozier, D.W., Boisvert, R.F., Clark, C.W. (eds.): NIST Handbook of Mathematical Functions. Cambridge University Press, Cambridge (2010). URL http://dlmf.nist.gov · Zbl 1198.00002
[35]	Redner, S.: A Guide to First-Passage Processes. Cambridge University Press, Cambridge (2001) · Zbl 0980.60006 · doi:10.1017/CBO9780511606014
[36]	Ricciardi, L.M., Sato, S.: First-passage-time density and moments of the Ornstein-Uhlenbeck process. J. Appl. Prob. 25(1), 43-57 (1988).URL http://www.jstor.org/stable/3214232 · Zbl 0651.60080
[37]	Riordan, J.: Stochastic Service Systems. The SIAM Series in Applied Mathematics. SIAM, New York (1962) · Zbl 0106.33601
[38]	Risken, H.: The Fokker-Planck Equation: Methods of Solution and Applications, 2nd edn. Springer, Berlin (1989) · Zbl 0665.60084 · doi:10.1007/978-3-642-61544-3
[39]	Ronveaux, A., Zarzo, A., Area, I., Godoy, E.: Transverse limits in the Askey tableau. J. Comput. Appl. Math. 99, 327-335 (1998). doi:10.1016/S0377-0427(98)00167-8 · Zbl 0936.33004 · doi:10.1016/S0377-0427(98)00167-8
[40]	Ross, S.M., Seshadri, S.: Hitting time in an Erlang loss system. Prob. Eng. Inf. Sci. 16, 167-184 (2002). doi:10.1017/S0269964802162036 · Zbl 1004.60090 · doi:10.1017/S0269964802162036
[41]	Shin, Y.W., Moon, D.H.: Sensitivity and approximation of M/G/c queue: numerical experiments. In: Proceedings of the 8th International Symposium Operations Research and its Application (ISORA’09), pp. 140-147. Zhangjiajie, China (2009).
[42]	Shwartz, A., Weiss, A.: Large Deviations for Performance Analysis: Queues, Communications, and Computing. Chapman & Hall, New York (1994) · Zbl 0871.60021
[43]	Srikant, R., Whitt, W.: Simulation runlengths to estimate blocking probabilities. ASCM Trans. Comput. Simul. 6, 7-52 (1996). doi:10.1145/229493.229496 · Zbl 1391.90198 · doi:10.1145/229493.229496
[44]	Szegő, G.: Orthogonal Polynomials, vol. XXIII, 4th edn. AMS Colloquium Publication, Providence (1975) · Zbl 0305.42011
[45]	Takacs, L.: On Erlang’s formula. Ann. Math. Stat. 40(1), 71-78 (1969). URL http://www.jstor.org/stable/2239199 · Zbl 0177.22001
[46]	Tijms, H.C.: Stochastic Modelling and Analysis A Computational Approach. Wiley & Sons, Chichester (1986)
[47]	Van Kampen, N.G.: Stochastic Processes in Physics and Chemistry, 2nd edn. North-Holland, Amsterdam (1992) · Zbl 0974.60020
[48]	Virtamo, J., Aalto, S.: Calculation of time-dependent blocking probabilities. In: B. Goldstein, A. Koucheryavy, M. Shneps-Shneppe (eds.) Proceedings of the ITC Sponsored St. Petersburg Regional International Teletraffic Seminar Teletraffic Theory as a Base for QoS: Monitoring, Evaluation, Decisions, pp. 365-375. St. Petersburg (1998). URL http://www.netlab.hut.fi/tutkimus/cost257/publ/transient
[49]	Wang, L., Pötzlberger, K.: Boundary crossing probability for Brownian motion and general boundaries. J. Appl. Prob. 34, 54-65 (1997). URL http://www.jstor.org/stable/3215174 · Zbl 0874.60034
[50]	Xie, S., Knessl, C.: On the transient behavior of the Erlang loss model: heavy usage asymptotics. SIAM J. Appl. Math. 53(2), 555-599 (1993). URL http://www.jstor.org/stable/2102350 · Zbl 0776.60118

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.