×
Shaikhet, Gennady

Necessary condition for null controllability in many-server heavy traffic. (English) Zbl 1311.60108

Ann. Appl. Probab. 25, No. 1, 406-428 (2015).
Author’s abstract: Throughput sub-optimality (TSO), introduced in [R. Atar and G. Shaikhet, Ann. Appl. Probab. 19, No. 2, 521–555 (2009; Zbl 1221.60130)] for static fluid models of parallel queueing networks, corresponds to the existence of a resource allocation, under which the total service rate becomes greater than the total arrival rate. As shown in [R. Atar et al., Ann. Appl. Probab. 16, No. 4, 1764–1804 (2006; Zbl 1121.60092)] and [R. Atar and G. Shaikhet, loc. cit.], in the many-server Halfin-Whitt regime, TSO implies null controllability (NC), the existence of a routing policy under which, for every finite \(T\), the measure of the set of times prior to \(T\) at which at least one customer is in the buffer converges to zero in probability as the scaling limit. The present paper investigates the question whether the converse relation is also true, and TSO is both sufficient and necessary for the NC behaviour. In what follows, we do get the affirmation for systems with either of two customer classes (and possibly more service pools) or vice-versa and state a condition on the underlying static fluid model that allows the extension of the result to general structures.
Reviewer: Vyacheslav Abramov (Melbourne)

MSC:

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

Keywords:

multiclass queueing systems; heavy traffic; scheduling; routing; throughput optimality; null controllability; buffer-station graph; simple paths

Citations:

Zbl 1221.60130; Zbl 1121.60092
Cite Review PDF
Full Text: DOI arXiv Euclid

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. and Gurvich, I. (2014). Scheduling parallel servers in the nondegenerate slowdown diffusion regime: Asymptotic optimality results. Ann. Appl. Probab. 24 760-810. · Zbl 1320.60150 · doi:10.1214/13-AAP935
[4] Atar, R., Mandelbaum, A. and Reiman, M. I. (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
[5] Atar, R., Mandelbaum, A. and Shaikhet, G. (2006). Queueing systems with many servers: Null controllability in heavy traffic. Ann. Appl. Probab. 16 1764-1804. · Zbl 1121.60092 · doi:10.1214/105051606000000358
[6] Atar, R. and Shaikhet, G. (2009). Critically loaded queueing models that are throughput suboptimal. Ann. Appl. Probab. 19 521-555. · Zbl 1221.60130 · doi:10.1214/08-AAP551
[7] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[8] Diestel, R. (2000). Graph Theory , 2nd ed. Graduate Texts in Mathematics 173 . Springer, New York. · Zbl 0957.05001
[9] Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29 567-588. · Zbl 0455.60079 · doi:10.1287/opre.29.3.567
[10] Harrison, J. M. and López, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Syst. 33 339-368. · Zbl 0997.60108 · doi:10.1023/A:1019188531950
[11] Mandelbaum, A. and Stolyar, A. L. (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] Stolyar, A. L. and Tezcan, T. (2010). Control of systems with flexible multi-server pools: A shadow routing approach. Queueing Syst. 66 1-51. · Zbl 1205.60162 · doi:10.1007/s11134-010-9183-0
[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). Fields Inst. Commun. 28 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.