Simple and Explicit Bounds for Multiserver Queues with 1/1−ρ Scaling

References

• [1] Abate J, Gagan LC, Whitt W (1994) Waiting-time tail probabilities in queues with long-tail service-time distributions. Queueing Systems 16:311–338.Crossref, Google Scholar
• [2] Aghajani R, Ramanan K (2020) The limit of stationary distributions of many-server queues in the Halfin–Whitt regime. Math. Oper. Res. 45(3):1016–1055.Link, Google Scholar
• [3] Allen AO (2014) Probability, Statistics, and Queueing Theory (Academic Press, New York).Google Scholar
• [4] Arjas E, Lehtonen T (1978) Approximating many server queues by means of single server queues. Math. Oper. Res. 3(3):205–223.Link, Google Scholar
• [5] Asmussen S (2008) Applied Probability and Queues, Stochastic Modelling and Applied Probability, vol. 51 (Springer Science and Business Media, New York).Google Scholar
• [6] Asmussen S, Nerman O, Olsson M (1996) Fitting phase-type distributions via the EM algorithm. Scand. J. Statist. 23(4):419–441.Google Scholar
• [7] Atar R, Solomon N (2011) Asymptotically optimal interruptible service policies for scheduling jobs in a diffusion regime with nondegenerate slowdown. Queueing Systems 69(3):217–235.Crossref, Google Scholar
• [8] Baccelli F, Bremaud P (2013) Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, Stochastic Modelling and Applied Probability, vol. 26 (Springer Science and Business Media, New York).Google Scholar
• [9] Bandi C, Bertsimas D, Youssef N (2015) Robust queueing theory. Oper. Res. 63(3):676–700.Link, Google Scholar
• [10] Batir N (2017) Bounds for the gamma function. Results Math. 72:865–874.Crossref, Google Scholar
• [11] Berger A, Whitt W (1992) Comparisons of multi-server queues with finite waiting rooms. Stochastic Models 8(4): 719–732.Crossref, Google Scholar
• [12] Bertsimas D, Nakazato D (1995) The distributional Little’s law and its applications. Oper. Res. 43(2):298–310.Link, Google Scholar
• [13] Borovkov AA (1965) Some limit theorems in the theory of mass service, II: Multiple channels systems. Theory Probab. Appl. 10(3):375–400.Crossref, Google Scholar
• [14] Borst S, Mandelbaum A, Reiman M (2004) Dimensioning large call centers. Oper. Res. 52(1):17–34.Link, Google Scholar
• [15] Braverman A, Dai JG (2017) Stein’s method for steady-state diffusion approximations of M/Ph/n + M systems. Ann. Appl. Probab. 27(1):550–581.Crossref, Google Scholar
• [16] Braverman A, Dai JG (2016) High order steady-state diffusion approximation of the Erlang-C system. Preprint, submitted February 9, https://arxiv.org/abs/1602.02866.Google Scholar
• [17] Braverman A, Dai JG, Feng J (2017) Stein’s method for steady-state diffusion approximations: An introduction through the Erlang-A and Erlang-C models. Stochastic Systems 6(2):301–366.Link, Google Scholar
• [18] Braverman A, Dai JG, Fang X (2022) High-order steady-state diffusion approximations. Oper. Res. 72(2):604–616.Google Scholar
• [19] Brumelle S (1973) Bounds on the wait in a GI/M/k Queue. Management Sci. 19(7):773–777.Link, Google Scholar
• [20] Burman DY, Smith DR (1983) A light-traffic theorem for multi-server queues. Math. Oper. Res. 8(1):15–25.Link, Google Scholar
• [21] Chawla S, Devanur N, Holroyd A, Karlin A, Martin J, Sivan B (2017) Stability of service under time-of-use pricing. Proc. 49th Annu. ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 184–197.Google Scholar
• [22] Dai JG, Harrison JM (2020) Processing Networks: Fluid Models and Stability (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [23] Dai JG, He S (2013) Many-server queues with customer abandonment: Numerical analysis of their diffusion model. Stochastic Systems 3(1):96–146.Link, Google Scholar
• [24] Dai JG, Dieker AB, Gao X (2014) Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Queueing Systems 78(1):1–29.Crossref, Google Scholar
• [25] Daley D (1977) Inequalities for moments of tails of random variables, with a queueing application. Probab. Theory Related Fields 41(2):139–143.Google Scholar
• [26] Daley D (1997) Some results for the mean waiting-time and workload in GI/GI/k queues. Dshalalow JH, ed. Frontiers in Queueing: Models and Applications in Science and Engineering (CRC Press, Boca Raton, FL), 35–59.Google Scholar
• [27] Daley D, Rolski T (1984) Some comparability results for waiting times in single- and many-server queues. J. Appl. Probab. 21(4):887–900.Crossref, Google Scholar
• [28] Daley D, Rolski T (1992) Light traffic approximations in many-server queues. Adv. Appl. Probab. 24(1):202–218.Crossref, Google Scholar
• [29] Doig A (1957) A bibliography on the theory of queues. Biometrika 44(3/4):490–514.Crossref, Google Scholar
• [30] Downey P (1991) Bounding synchronization overhead for parallel iteration. ORSA J. Comput. 3(4):288–298.Link, Google Scholar
• [31] Eick S, Massey W, Whitt W (1993) The physics of the Mt/G/∞ queue. Oper. Res. 41(4):731–742.Link, Google Scholar
• [32] Gamarnik D, Goldberg DA (2013) Steady-state GI/G/n queue in the Halfin–Whitt regime. Ann. Appl. Probab. 23(6):2382–2419.Crossref, Google Scholar
• [33] Gamarnik D, Momcilovic P (2008) Steady-state analysis of a multiserver queue in the Halfin-Whitt regime. Adv. Appl. Probab. 40(2):548–577.Crossref, Google Scholar
• [34] Gamarnik D, Stolyar A (2012) Multiclass multiserver queueing system in the Halfin–Whitt heavy traffic regime: Asymptotics of the stationary distribution. Queueing Systems 71:25–51.Crossref, Google Scholar
• [35] Gamarnik D, Zeevi A (2006) Validity of heavy traffic steady-state approximations in generalized Jackson networks. Ann. Appl. Probab. 16(1):56–90.Google Scholar
• [36] Gaunt R, Walton N (2020) Stein’s method for the single server queue in heavy traffic. Statist. Probab. Lett. 156:108566.Crossref, Google Scholar
• [37] Goldberg DA (2016) On the steady-state probability of delay and large negative deviations for the GI/GI/n queue in the Halfin-Whitt regime. Preprint, submitted August 31, https://arxiv.org/abs/1307.0241v2.Google Scholar
• [38] Goldberg DA, Li Y (2017) Heavy-tailed queues in the Halfin-Whitt regime. Preprint, submitted July 25, https://arxiv.org/abs/1707.07775.Google Scholar
• [39] Goldberg DA, Li Y (2017) Simple and explicit bounds for multi-server queues with universal 1/(1-rho) scaling. Preprint, submitted June 14, https://arxiv.org/abs/1706.04628.Google Scholar
• [40] Goldberg DA, Mukherjee D, Li Y (2018) Large deviations analysis for the M/H2/n+M queue in the Halfin-Whitt regime. Preprint, submitted March 3, https://arxiv.org/abs/1803.01082.Google Scholar
• [41] Goldberg DA, Katz-Rogozhnikov D, Lu Y, Sharma M, Squillante M (2016) Asymptotic optimality of constant-order policies for lost sales inventory models with large lead times. Math. Oper. Res. 41(3):898–913.Link, Google Scholar
• [42] Grosof I, Harchol-Balter M, Scheller-Wolf A (2021) The finite-skip method for multiserver analysis. Preprint, submitted September 26, https://arxiv.org/abs/2109.12663v1.Google Scholar
• [43] Grosof I, Scully Z, Harchol-Balter M (2018) SRPT for multiserver systems. Performance Eval. 127:154–175.Crossref, Google Scholar
• [44] Gross D, Shortle J, Thompson J, Harris C (2011) Fundamentals of Queueing Theory, Wiley Series in Probability and Statistics, vol. 627 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [45] Gupta V, Osogami T (2011) Tight moments-based bounds for queueing systems. Proc. ACM SIGMETRICS Joint Internat. Conf. Measurement Modeling Comput. Systems (Association for Computing Machinery, New York), 133–134.Google Scholar
• [46] Gupta V, Harchol-Balter M, Dai JG, Zwart B (2010) On the inapproximability of M/G/K: Why two moments of job size distribution are not enough. Queueing Systems 64(1):5–48.Crossref, Google Scholar
• [47] Gurvich I (2014) Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. Ann. Appl. Probab. 24(6):2527–2559.Crossref, Google Scholar
• [48] Gurvich I, Huang J, Mandelbaum A (2013) Excursion-based universal approximations for the Erlang-A queue in steady-state. Math. Oper. Res. 39(2):325–373.Link, Google Scholar
• [49] Gut A (2009) Stopped Random Walks (Springer-Verlag, New York).Crossref, Google Scholar
• [50] Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• [51] Harchol-Balter M, Scheller-Wolf A, Young A (2009) Surprising results on task assignment in server farms with high-variability workloads. Performance Eval. Rev. 37(1):287–298.Crossref, Google Scholar
• [52] Hokstad P (1985) Relations for the workload of the GI/G/s queue. Adv. Appl. Probab. 17(4):887–904.Crossref, Google Scholar
• [53] Hong Y, Wang W (2022) Sharp waiting-time bounds for multiserver jobs. Proc. Twenty-Third Internat. Sympos. Theory Algorithmic Foundations Protocol Design Mobile Networks Mobile Comput. (Association for Computing Machinery, New York), 161–170.Google Scholar
• [54] Huang J, Gurvich I (2018) Beyond heavy-traffic regimes: Universal bounds and controls for the single-server queue. Oper. Res. 66(4):1168–1188.Link, Google Scholar
• [55] Iglehart D, Whitt W (1970) Multiple channel queues in heavy traffic. II: Sequences, networks, and batches. Adv. Appl. Probab. 2(02):355–369.Crossref, Google Scholar
• [56] Janssen A, Van Leeuwaarden JSH (2008) Back to the roots of the M/D/s queue and the works of Erlang, Crommelin and Pollaczek. Stat. Neerlandica 62(3):299–313.Crossref, Google Scholar
• [57] Janssen A, Van Leeuwaarden JSH, Zwart B (2008) Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime. Queueing Systems 58(4):261–301.Crossref, Google Scholar
• [58] Janssen A, Van Leeuwaarden JSH, Zwart B (2011) Refining square-root safety staffing by expanding Erlang C. Oper. Res. 59(6):1512–1522.Link, Google Scholar
• [59] Jin X, Pang G, Xu L, Xu X (2021) An approximation to steady-state of M/Ph/n + M queue. Preprint, submitted September 8, https://arxiv.org/abs/2109.03623.Google Scholar
• [60] Kennedy D (1972) Rates of convergence for queues in heavy traffic. II: Sequences of queueing systems. Adv. Appl. Probab. 4(2):382–391.Crossref, Google Scholar
• [61] Kiefer J, Wolfowitz J (1956) On the characteristics of the general queueing process, with applications to random walk. Ann. Math. Statist. 27(1):147–161.Crossref, Google Scholar
• [62] Kingman JFC (1962) On queues in heavy traffic. J. Roy. Statist. Soc. B 24(2):383–392.Crossref, Google Scholar
• [63] Kingman JFC (1964) A martingale inequality in the theory of queues. Math. Proc. Cambridge Philosophical Soc. 60(2):359–361.Google Scholar
• [64] Kingman JFC (1965) The heavy traffic approximation in the theory of queues. Proc. Sympos. Congestion Theory No. 2 (University of North Carolina Press, Chapel Hill, NC).Google Scholar
• [65] Kingman JFC (1970) Inequalities in the theory of queues. J. Roy. Statist. Soc. B 32(1):102–110.Crossref, Google Scholar
• [66] Kollerstrom J (1974) Heavy traffic theory for queues with several servers. I. J. Appl. Probab. 11(3):544–552.Crossref, Google Scholar
• [67] Kollerstrom J (1979) Heavy traffic theory for queues with several servers. II. J. Appl. Probab. 12(2):393–401.Crossref, Google Scholar
• [68] Kollerstrom J (1981) A second-order heavy traffic approximation for the queue GI/G/1. Adv. Appl. Probab. 13(1):167–185.Crossref, Google Scholar
• [69] Longnecker M, Serfling RJ (1977) General moment and probability inequalities for the maximum partial sum. Acta Math. Hungarica 30(1–2):129–133.Crossref, Google Scholar
• [70] Loulou R (1973) Multi-channel queues in heavy traffic. J. Appl. Probab. 10(04):769–777.Crossref, Google Scholar
• [71] Maglaras C, Yao J, Zeevi A (2018) Optimal price and delay differentiation in large-scale queueing systems. Management Sci. 64(5):2427–2444.Link, Google Scholar
• [72] Makino T (1969) Investigation of the mean waiting time for queueing system with many servers. Ann. Inst. Statist. Math. 21(1):357–366.Crossref, Google Scholar
• [73] Mandelbaum A, Momcilovic P (2012) Queues with many servers and impatient customers. Math. Oper. Res. 37(1):41–65.Link, Google Scholar
• [74] Mandelbaum A, Massey W, Reiman M (1998) Strong approximations for Markovian service networks. Queueing Systems 30(1):149–201.Crossref, Google Scholar
• [75] Mori M (1975) Some bounds for queues. J. Oper. Res. Soc. Japan 18:152–181.Google Scholar
• [76] Nagaev S (1970) On the speed of convergence in a boundary problem. I. Theory Probab. Appl. 15(2):163–186.Crossref, Google Scholar
• [77] Nagaev S (1970) On the speed of convergence in a boundary problem. II. Theory Probab. Appl. 15(3):403–429.Crossref, Google Scholar
• [78] Oliver SY (1974) Stochastic bounds for heterogeneous-server queues with Erlang service times. J. Appl. Probab. 11(04):785–796.Crossref, Google Scholar
• [79] Olvera-Cravioto M, Glynn P (2011) Uniform approximations for the M/G/1 queue with subexponential processing times. Queueing Systems 68(1):1–50.Crossref, Google Scholar
• [80] Olvera-Cravioto M, Blanchet J, Glynn P (2011) On the transition from heavy traffic to heavy tails for the M/G/1 queue: The regularly varying case. Ann. Appl. Probab. 21(2):654–668.Crossref, Google Scholar
• [81] Ovuworie G (1980) Multi-channel queues: A survey and bibliography. Internat. Statist. Rev. 48(1):49–71.Google Scholar
• [82] Reed J (2009) The G/GI/N queue in the Halfin–Whitt regime. Ann. Appl. Probab. 19(6):2211–2269.Crossref, Google Scholar
• [83] Reiman M (1984) Open queueing networks in heavy traffic. Math. Oper. Res. 9(3):441–458.Link, Google Scholar
• [84] Rolski T, Stoyan D (1976) On the comparison of waiting times in GI/G/1 queues. Oper. Res. 24:197–200.Link, Google Scholar
• [85] Sadowsky J (1991) Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Trans. Automatic Control 36(12):1383–1394.Crossref, Google Scholar
• [86] Scheller-Wolf A (2003) Necessary and sufficient conditions for delay moments in FIFO multiserver queues with an application comparing s slow servers with one fast one. Oper. Res. 51(5):748–758.Link, Google Scholar
• [87] Scheller-Wolf A, Vesilo R (2006) Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues. Queueing Systems 54(3):221–232.Crossref, Google Scholar
• [88] Scully Z, Grosof I, Harchol-Balter M (2020) The Gittins policy is nearly optimal in the M/G/k under extremely general conditions. Proc. ACM Measurement Anal. Comput. Systems 4(3):1–29.Google Scholar
• [89] Seshadri S (1996) A sample path analysis of the delay in the M/G/C system. J. Appl. Probab. 33:256–266.Crossref, Google Scholar
• [90] Sevastyanov BA (1957) An ergodic theorem for Markov processes and its application to telephone systems with refusals. Theory Probab. Appl. 2(1):104–112.Crossref, Google Scholar
• [91] Smith D, Whitt W (1981) Resource sharing for efficiency in traffic systems. Bell Syst. Tech. J. 60(1):39–55.Crossref, Google Scholar
• [92] Suzuki T, Yoshida Y (1970) Inequalities for many-server queue and other queues. J. Oper. Res. Soc. Japan 13:59–77.Google Scholar
• [93] Szczotka W (1999) Tightness of the stationary waiting time in heavy traffic. Adv. Appl. Probab. 31(3):788–794.Crossref, Google Scholar
• [94] Szczotka W, Woyczynski WA (2004) Heavy-tailed dependent queues in heavy traffic. Probab. Math. Statist. 24(1):67–96.Google Scholar
• [95] Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• [96] Vesilo R, Scheller-Wolf A (2013) Delay moment bounds for multiserver queues with infinite variance service times. INFOR Inform. Systems Oper. Res. 51(4):161–174.Crossref, Google Scholar
• [97] Wang W, Xie Q, Harchol-Balter M (2021) Zero queueing for multi-server jobs. Abstract Proc. 2021 ACM SIGMETRICS/Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery, New York), 13–14.Google Scholar
• [98] Whitt W (1974) The continuity of queues. Adv. Appl. Probab. 6(1):175–183.Crossref, Google Scholar
• [99] Whitt W (1980) The effect of variability in the GI/G/s queue. J. Appl. Probab. 17:1062–1071.Crossref, Google Scholar
• [100] Whitt W (1981) Comparing counting processes and queues. Adv. Appl. Probab. 13(1):207–220.Crossref, Google Scholar
• [101] Whitt W (1982) Refining diffusion approximations for queues. Oper. Res. Lett. 1(5):165–169.Crossref, Google Scholar
• [102] Whitt W (1982) The Marshall and Stoyan bounds for IMRL/G/1 queues are tight. Oper. Res. Lett. 1(6):209–213.Crossref, Google Scholar
• [103] Whitt W (1982) On the heavy-traffic limit theorem for GI/G/∞ queues. Adv. Appl. Probab. 14(1):171–190.Crossref, Google Scholar
• [104] Whitt W (1983) Comparison conjectures about the M/G/s queue. Oper. Res. Lett. 2(5):203–209.Crossref, Google Scholar
• [105] Whitt W (1984) On approximations for queues, I: Extremal distributions. ATT Bell Lab. Tech. J. 63(1):115–138.Crossref, Google Scholar
• [106] Whitt W (1984) On approximations for queues, III: Mixtures of exponential distributions. ATT Bell Lab. Tech. J. 63(1):163–175.Crossref, Google Scholar
• [107] Whitt W (1993) Approximations for the GI/G/m queue. Production Oper. Management 2(2):114–161.Crossref, Google Scholar
• [108] Whitt W (2000) The impact of a heavy-tailed service-time distribution upon the M/GI/s waiting-time distribution. Queueing Systems 36(1):71–87.Crossref, Google Scholar
• [109] Whitt W, Kuncewicz JG (1984) On approximations for queues, II: Shape constraints. ATT Bell Lab. Tech. J. 63(1):139–161.Crossref, Google Scholar
• [110] Wolff RW (1987) Upper bounds on work in system for multichannel queues. J. Appl. Probab. 24(02):547–551.Crossref, Google Scholar
• [111] Worthington D (2009) Reflections on queue modelling from the last 50 years. J. Oper. Res. Soc. 60(1):S83–S92.Crossref, Google Scholar
• [112] Xin L, Goldberg DA (2016) Optimality gap of constant-order policies decays exponentially in the lead time for lost sales models. Oper. Res. 64(6):1556–1565.Link, Google Scholar