Critically loaded queueing models that are throughput suboptimal. (English) Zbl 1221.60130

Atar, Rami; Shaikhet, Gennady

Ann. Appl. Probab. 19, No. 2, 521-555 (2009).

The queueing model under consideration has multiple customer classes, indexed by a finite set \(I\), and heterogeneous exponential servers. The servers are grouped in pools, indexed by a finite set \(J\), and it is assumed that each pool has a large number of servers that have identical capabilities. The rate \(\mu _{ij} \), at which a server from pool \(j \in J\) serves customers from class \(i \in I\), depends on both \(i\) and \(j\). The arrival of class-\(i\) customers is modeled as a renewal process with rate \(\lambda _i \). Servers are dynamically chosen to serve customers, and buffers are available to accommodate customers that wait to be served. The model is considered in a many-server heavy traffic regime, in which the number of servers at each pool and the arrival rates are scaled up at a nearly fixed proportion, and in such a way that the processes that represent the number of class-\(i\) customers in the system fluctuate about a certain static fluid model. This fluid model is assumed to be critically loaded, in a standard sense. In particular, (1) servers can be allocated in such a way that the total processing rate devoted to class-\(i\) customers is equal to the arrival rate \(\lambda _i \), for every \(i \in I\); and (2) property (1) does not hold if one of the arrival rates \(\lambda _i \) is replaced by some \(\lambda _i^1 > \lambda _i \). It is possible for such a model to satisfy the following condition: servers can be allocated so as to achieve a total processing rate that is greater than the total arrival rate. If this condition holds, the fluid model is said to be throughout suboptimal. The main result shows that when the fluid model is throughout suboptimal, one can find a dynamic control policy for the queueing model that exhibits a strong form of efficiency: under this policy, 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 arrival rates and number or servers go to infinity.

Reviewer: Oleg K. Zakusilo (Kyïv)

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

Keywords:

multi-class queueing systems; heavy traffic; scheduling and routing; throughout optimality; asymptotic null controllability; buffer-station graph

References:

[1]	Aksin, Z., Armony, M. and Mehrotra, V. (2007). The modern call center: A multi-disciplinary perspective on operations management research. Production and Operations Management 16 665-688.
[2]	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
[3]	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
[4]	Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[5]	Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks : Performance , Asymptotics , and Optimization. Applications of Mathematics ( New York ) 46 . Springer, New York. · Zbl 0992.60003
[6]	Diestel, R. (2000). Graph Theory , 2nd ed. Graduate Texts in Mathematics 173 . Springer, New York. · Zbl 0945.05002
[7]	Harrison, J. M. and López, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems Theory Appl. 33 339-368. · Zbl 0997.60108 · doi:10.1023/A:1019188531950
[8]	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