article

Heavy-Traffic Limits for Queues with Many Exponential Servers

Operations Research, Volume 29, Issue 3

Pages 567 - 588

https://doi.org/10.1287/opre.29.3.567

Published: 01 June 1981 Publication History

Abstract

<P>Two different kinds of heavy-traffic limit theorems have been proved for s-server queues. The first kind involves a sequence of queueing systems having a fixed number of servers with an associated sequence of traffic intensities that converges to the critical value of one from below. The second kind, which is often not thought of as heavy traffic, involves a sequence of queueing systems in which the associated sequences of arrival rates and numbers of servers go to infinity while the service time distributions and the traffic intensities remain fixed, with the traffic intensities being less than the critical value of one. In each case the sequence of random variables depicting the steady-state number of customers waiting or being served diverges to infinity but converges to a nondegenerate limit after appropriate normalization. However, in an important respect neither procedure adequately represents a typical queueing system in practice because in the heavy-traffic limit an arriving customer is either almost certain to be delayed first procedure or almost certain not to be delayed second procedure. Hence, we consider a sequence of GI/M/S systems in which the traffic intensities converge to one from below, the arrival rates and the numbers of servers go to infinity, but the steady-state probabilities that all servers are busy are held fixed. The limits in this case are hybrids of the limits in the other two cases. Numerical comparisons indicate that the resulting approximation is better than the earlier ones for many-server systems operating at typically encountered loads.</P>

References

[1]

BILLINGSLEY, P. 1968. Convergence of Probability Measures. John Wiley & Sons, New York.

[2]

BOROVKOV, A. A. 1965. Some Limit Theorems in the Theory of Mass Service, I. Theor. Prob. Appl. 10, 375-400.

[3]

BOROVKOV, A. A. 1967. On Limit Laws for Service Processes in Multi-channel Systems. Siberian Math. J. 8, 746-763.

[4]

BOROVKOV, A. A. 1976. Stochastic Processes in Queueing Theory. Springer-Verlag, New York.

[5]

BREIMAN, L. 1968. Probability. Addison-Wesley, Reading, Mass.

[6]

CHANDY, K. M., AND C. H. SAUER. 1978. Approximate Methods for Analyzing Queueing Network Models for Computer Systems. Comput. Surv. 10, 281-317.

Digital Library

[7]

COOPER, R. B. 1972. Introduction to Queueing Theory. Macmillan, New York.

[8]

FELLER, W. 1968. An Introduction to Probability Theory and Its Applications, Vol. I, Ed. 3. John Wiley & Sons, New York.

[9]

GNEDENKO, B. V., AND I. N. KOVALENKO. 1968. Introduction to Queueing Theory. Israel Program for Scientific Translation, Jerusalem.

[10]

HALACHMI, B., AND W. R. FRANTA. 1978. A Diffusion Approximation to the Multi-Server Queue. Mgmt. Sci. 24, 522-529.

Digital Library

[11]

HARRISON, J. M. 1978. The Diffusion Approximation for Tandem Queues in Heavy Traffic. Adv. Appl. Prob. 10, 886-905.

[12]

IGLEHART, D. L. 1965. Limit Diffusion Approximations for the Many-Server Queue and the Repairman Problem. J. Appl. Prob. 2, 429-441.

[13]

IGLEHART, D. L. 1973a. Weak Convergence in Queueing Theory. Adv. Appl. Prob. 5, 570-594.

[14]

IGLEHART, D. L. 1973b. Weak Convergence of Compound Stochastic Processes, I. Stock. Proc. Appl. 1, 11-31.

[15]

IGLEHART, D. L., AND W. WHITT. 1970. Multiple Channel Queues in Heavy Traffic; II. Sequences, Networks, and Batches. Adv. Appl. Prob. 2, 355-369.

[16]

KAMAE, T., U. KRENGEL AND G. O'BRIEN. 1977. Stochastic Inequalities on Partially Ordered Spaces. Ann. Prob. 5, 899-912.

[17]

KARLIN, S., AND J. MCGREGOR. 1964. On Some Stochastic Models in Genetics. In Stochastic Models in Medicine and Biology, pp. 245-279, J. Gurland (ed.). University of Wisconsin Press, Madison.

[18]

KINGMAN, J. F. C. 1962. On Queues in Heavy Traffic. J. Roy. Stat. Soc. Ser. B, 24, 383-392.

[19]

KINGMAN, J. F. C. 1965. The Heavy Traffic Approximation in the Theory of Queues. In Proceedings of Symposium on Congestion Theory, pp. 137-159, W. Smith and W. Wilkinson (eds.). University of North Carolina Press, Chapel Hill, N.C.

[20]

KÖLLERSTRÖM, J. 1974. Heavy Traffic Theory for Queues with Several Servers, I. J. Appl. Prob. 11, 544-552.

[21]

LEMOINE, A. J. 1978. Networks of Queues--A Survey of Weak Convergence Results. Mgmt. Sci. 24, 1175-1193.

Digital Library

[22]

LINDVALL, T. 1973. Weak Convergence of Probability Measures and Random Functions in the Function Space D[0, ¿). J. Appl. Prob. 10, 109-121.

[23]

NEWELL, G. F. 1973. Approximate Stochastic Behavior of n-Server Service Systems with Large n (Lecture Notes in Economics and Mathematical Systems, No. 87). Springer-Verlag, New York.

[24]

PROHOROV, YU. 1963. Transient Phenomena in Processes of Mass Service (in Russian). Litovsk. Mat. Sb. 3, 199-205.

[25]

RHEE, J. J. 1977. The Expectation Value and the Variance for the Poisson Distribution. Am. J. Phys. 46, 769-770.

[26]

STONE, C. 1961. Limit Theorems for Birth and Death Processes and Diffusion Processes, Ph.D. thesis, Department of Mathematics, Stanford University.

[27]

STONE, C. 1963. Limit Theorems for Random Walks, Birth and Death Processes, and Diffusion Processes. III. J. Math. 4, 638-660.

[28]

STROOCK, D., AND S. R. S. VARADHAN. 1979. Multidimensional Diffusion Processes. Springer-Verlag, New York.

[29]

WHITT, W. 1972. Embedded Renewal Processes in the GI/G/s Queue. J. Appl. Prob. 9, 650-658.

[30]

WHITT, W. 1974. Heavy Traffic Limit Theorems for Queues: A Survey. In Mathematical Methods in Queueing Theory (Lecture Notes in Economics and Mathematical Systems, No. 98), pp. 307-350. Springer-Verlag, Berlin.

[31]

WHITT, W. 1980. Some Useful Functions for Functional Limit Theorems. Math. Opns. Res. 5, 67-85.

Digital Library

[32]

WHITT, W. 1981. Comparing Counting Processes and Queues. Adv. Appl. Prob. (to appear).

[33]

WHITT, W. 1982. On the Heavy-Traffic Limit Theorem for GI/G/¿ Queues. Adv. Appl. Prob. (to appear).

Cited By

Braverman ADai JFang X(2024)High-Order Steady-State Diffusion ApproximationsOperations Research10.1287/opre.2022.236272:2(604-616)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2362
Chen JDong J(2024)Managing flexibility: optimal sizing and scheduling of flexible serversQueueing Systems: Theory and Applications10.1007/s11134-024-09926-x108:3-4(415-474)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11134-024-09926-x
Zuk JKirszenblat D(2024)Exact results for the distribution of the partial busy period for a multi-server queueQueueing Systems: Theory and Applications10.1007/s11134-024-09906-1107:1-2(63-108)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s11134-024-09906-1
Show More Cited By

Index Terms

Heavy-Traffic Limits for Queues with Many Exponential Servers
1. Applied computing
  1. Enterprise computing

Recommendations

Heavy-traffic limits for many-server queues with service interruptions

We establish many-server heavy-traffic limits for G/M/n+M queueing models, allowing customer abandonment (the +M), subject to exogenous regenerative service interruptions. With unscaled service interruption times, we obtain a FWLLN for the queue-length ...
Heavy Traffic Limits for Queues with Many Deterministic Servers

Consider a sequence of stationary GI/D/ N queues indexed by N ýý, with servers' utilization 1ýß/ $\sqrt{N}$ , ß>0. For such queues we show that the scaled waiting times $\sqrt{N}$ W _N converge to the (finite) supremum of a Gaussian random walk ...
Efficiency-Driven Heavy-Traffic Approximations for Many-Server Queues with Abandonments

To provide useful practical insight into the performance of service-oriented (non-revenue-generating) call centers, which often provide low-to-moderate quality of service, this paper investigates the efficiency-driven (ED), many-server heavy-traffic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 29, Issue 3

June 1981

211 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 June 1981

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

206
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Braverman ADai JFang X(2024)High-Order Steady-State Diffusion ApproximationsOperations Research10.1287/opre.2022.236272:2(604-616)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2362
Chen JDong J(2024)Managing flexibility: optimal sizing and scheduling of flexible serversQueueing Systems: Theory and Applications10.1007/s11134-024-09926-x108:3-4(415-474)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11134-024-09926-x
Zuk JKirszenblat D(2024)Exact results for the distribution of the partial busy period for a multi-server queueQueueing Systems: Theory and Applications10.1007/s11134-024-09906-1107:1-2(63-108)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s11134-024-09906-1
Hillas LCaldentey RGupta V(2024)Heavy traffic analysis of multi-class bipartite queueing systems under FCFSQueueing Systems: Theory and Applications10.1007/s11134-024-09903-4106:3-4(239-284)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s11134-024-09903-4
Özkan Evan Houtum G(2023)Joint Inventory and Scheduling Control in a Repair FacilityOperations Research10.1287/opre.2023.245971:5(1498-1514)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1287/opre.2023.2459
Hmedi HArapostathis APang G(2023)On System-Wide Safety Staffing of Large-Scale Parallel Server NetworksOperations Research10.1287/opre.2021.225671:2(415-432)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1287/opre.2021.2256
Yu LPerry O(2023)Many-Server Heavy-Traffic Limits for Queueing Systems with Perfectly Correlated Service and Patience TimesMathematics of Operations Research10.1287/moor.2022.130048:2(1119-1157)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/moor.2022.1300
Büke BQin W(2023)Many-Server Queues with Random Service RatesMathematics of Operations Research10.1287/moor.2022.128048:2(748-783)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/moor.2022.1280
Yu LIravani SPerry O(2022)A Fluid-Diffusion-Hybrid Limiting Approximation for Priority Systems with Fast and Slow CustomersOperations Research10.1287/opre.2021.215470:4(2579-2596)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/opre.2021.2154
Besbes OCastro FLobel I(2022)Spatial Capacity PlanningOperations Research10.1287/opre.2021.211270:2(1271-1291)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1287/opre.2021.2112
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents