Sharp and simple bounds for the Erlang delay and loss formulae
Tóm tắt
We prove some simple and sharp lower and upper bounds for the Erlang delay and loss formulae and for the number of servers that invert the Erlang delay and loss formulae. We also suggest simple and sharp approximations for the number of servers that invert the Erlang delay and loss formulae. We illustrate the importance of these bounds by using them to establish convexity proofs. We show that the probability that the M/M/s queue is empty is a decreasing and convex function of the traffic intensity. We also give a very short proof to show that the Erlang delay formula is convex in the traffic intensity when the number of servers is held constant. The complete proof of this classical result has never been published. We also give a very short proof to show that the Erlang delay formula is a convex function of the (positive integer) number of servers. One of our results is then used to get a sharp bound to the Flow Assignment Problem.
Tài liệu tham khảo
Adelman, D.: A simple algebraic approximation to the Erlang loss system. Oper. Res. Lett. 36(4), 484–491 (2008)
Berezner, S.A., Krzesinski, A.E., Taylor, P.G.: On the inverse of Erlang’s function. J. Appl. Probab. 35, 246–252 (1998)
Cooper, R.B.: Introduction to Queueing Theory, 2nd edn. North-Holland, Amsterdam (1981)
Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the Lambert W function. Adv. Comput. Math. 5(4), 329–359 (1996)
Fuhrmann, S., Kogan, Y., Milito, R.A.: An adaptive autonomous network congestion controller. In: Proceeding of the 35th IEEE Conference on Decision and Control, Kobe, Japan, December 1996, pp. 301–306 (1996)
Halfin, S., Whitt, W.: Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29, 567–588 (1981)
Harel, A.: Sharp bounds and simple approximations for the Erlang delay and loss formulas. Manag. Sci. 34, 959–972 (1988)
Harel, A.: Erratum to: sharp bounds and simple approximations for the Erlang delay and loss formulas. Manag. Sci. 34, 1277 (1988)
Harel, A.: Convexity properties of the Erlang loss formula. Oper. Res. 38, 499–505 (1990)
Harel, A., Zipkin, P.: Strong convexity results for queueing systems. Oper. Res. 35(3), 405–418 (1987)
Jagerman, D.L.: Some properties of the Erlang loss function. Bell Syst. Tech. J. 53, 525–551 (1974)
Jagers, A.A., van Doorn, E.A.: Convexity of functions which are generalizations of the Erlang loss function and the Erlang delay function. SIAM Rev. 33(2), 281–282 (1991)
Janssen, A.J.E.M., van Leeuwaarden, J.S.H., Zwart, B.: Corrected asymptotics for a multi-server queue in the Halfin–Whitt regime. Queueing Syst. 58(4), 261–301 (2008)
Kleinrock, L.: Queueing Systems. Vol. II. Computer Applications. Wiley, New York (1976)
Ko, S.S., Serfozo, R., Sivakumar, A.I.: Reducing cycle times in manufacturing and supply chains by input and service rate smoothing. IIE Trans. 36(2), 145–153 (2004)
Lee, H.L., Cohen, M.A.: A note on the convexity of performance measures of M/M/c queueing systems. Working Paper 82-06-04, Department of Decision Sciences, The Wharton School, University of Pennsylvania (1982)
Lee, H.L., Cohen, M.A.: A note on the convexity of performance measures of M/M/c queueing systems. J. Appl. Probab. 20, 920–923 (1983)
van Leeuwaarden, J.S.H., Temme, N.M.: Asymptotic inversion of the Erlang B formula. SIAM J. Appl. Math. 70(1), 1–23 (2009)
Newell, G.F.: The M/M/∞ Service System with Ranked Servers in Heavy Traffic. Springer, New York (1984)
Sobel, M.J.: Simple inequality for multiserver queues. Manag. Sci. 26, 951–956 (1980)
Whitt, W.: The Erlang B and C formulas: problems and solutions. Unpublished Manuscript. http://www.columbia.edu/~ww2040/ErlangBandCFormulas.pdf (2002)