×

Queueing systems with many servers: null controllability in heavy traffic. (English) Zbl 1121.60092

Summary: A queueing model has \(J\geq 2\) heterogeneous service stations, each consisting of many independent servers with identical capabilities. Customers of \(I\geq 2\) classes can be served at these stations at different rates, that depend on both the class and the station. A system administrator dynamically controls scheduling and routing. We study this model in the central limit theorem (or heavy traffic) regime proposed by Sh. Halfin and W. Whitt [Oper. Res. 29, 567–588 (1981; Zbl 0455.60079)]. We derive a diffusion model on \(\mathbb R^I\) with a singular control term that describes the scaling limit of the queueing model. The singular term may be used to constrain the diffusion to lie in certain subsets of \(\mathbb R^I\) at all times \(t>0\). We say that the diffusion is null-controllable if it can be constrained to \(\mathbb X_-\), the minimal closed subset of \(\mathbb R^I\) containing all states of the prelimit queueing model for which all queues are empty. We give sufficient conditions for null controllability of the diffusion. Under these conditions we also show that an analogous, asymptotic result holds for the queueing model, by constructing control policies under which, for any given \(0<\varepsilon<T<\infty\), all queues in the system are kept empty on the time interval \([\varepsilon,T]\), with probability approaching one. This introduces a new, unusual heavy traffic behavior: On one hand, the system is critically loaded, in the sense that an increase in any of the external arrival rates at the fluid level results with an overloaded system. On the other hand, as far as queue lengths are concerned, the system behaves as if it is underloaded.

MSC:

60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research
60F05 Central limit and other weak theorems
49N25 Impulsive optimal control problems

Citations:

Zbl 0455.60079

References:

[1] Atar, R. (2005). A diffusion model of scheduling control in queueing systems with many servers. Ann. Appl. Probab. 15 820–852. · Zbl 1084.60053 · doi:10.1214/105051604000000963
[2] Atar, R. (2005). Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic. Ann. Appl. Probab. 15 2606–2650. · Zbl 1098.60083 · doi:10.1214/105051605000000601
[3] Atar, R., Mandelbaum, A. and Reiman, M. (2004). Scheduling a multi-class queue with many exponential servers: Asymptotic optimality in heavy-traffic. Ann. Appl. Probab. 14 1084–1134. · Zbl 1049.60079 · doi:10.1214/105051604000000233
[4] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[5] Bramson, M. and Williams, R. J. (2003). Two workload properties for Brownian networks. Queueing Systems 45 191–221. · Zbl 1131.60305 · doi:10.1023/A:1027372517452
[6] Gans, N., Koole, G. and Mandelbaum, A. (2003). Telephone call centers: Tutorial, review and research prospects. MSOM 5 79–141.
[7] Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29 567–588. JSTOR: · Zbl 0455.60079 · doi:10.1287/opre.29.3.567
[8] Harrison, J. M. and López, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33 339–368. · Zbl 0997.60108 · doi:10.1023/A:1019188531950
[9] Kushner, H. J. and Dupuis, P. (2001). Numerical Methods for Stochastic Control Problems in Continuous Time , 2nd ed. Springer, New York. · Zbl 0968.93005
[10] Lions, P. L. and Sznitman, A. S. (1984). Stochastic differential equations with reflecting boundary conditions. Comm. Pure Appl. Math. 37 511–537. · Zbl 0598.60060 · doi:10.1002/cpa.3160370408
[11] Mandelbaum, A. and Stolyar, A. (2004). Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized \(c\mu\)-rule. Oper. Res. 52 836–855. · Zbl 1165.90402 · doi:10.1287/opre.1040.0152
[12] Puhalskii, A. A. and Reiman, M. I. (2000). The multiclass \(GI/PH/N\) queue in the Halfin–Whitt regime. Adv. in Appl. Probab. 32 564–595. · Zbl 0962.60089 · doi:10.1239/aap/1013540179
[13] Williams, R. J. (2000). On dynamic scheduling of a parallel server system with complete resource pooling. In Analysis of Communication Networks : Call Centres , Traffic and Performance ( Toronto , ON , 1998 ) 49–71. Amer. Math. Soc., Providence, RI. · Zbl 0982.90024
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.