Asymptotic optimality of a joint scheduling–control policy for parallel server queues with multiclass jobs in heavy traffic

Xiaolong Li; Xiaolong Li

doi:10.3934/math.2025196

AIMS Mathematics

2025, Volume 10, Issue 2: 4226-4267. doi: 10.3934/math.2025196

Previous Article Next Article

Research article Special Issues

Asymptotic optimality of a joint scheduling–control policy for parallel server queues with multiclass jobs in heavy traffic

Xiaolong Li ^,

School of Mathematics, Nanjing University, Nanjing 210093, China

Received: 17 December 2024 Revised: 07 February 2025 Accepted: 20 February 2025 Published: 28 February 2025
MSC : 90B22, 90B36, 49L20

To optimize the control of a queuing system with multiple classes of customers and multiple servers, we introduce a novel joint scheduling–control policy that includes customer admission control, service scheduling control, and service rate control. In this policy, any server can serve any class of customers; the service rate control for a server is a unique feature of this policy and is determined by the overall state of the system, not the state of a server or the class of customers it serves. Given the inherent complexity of the system$ ^\prime $s equations and the difficulty of solving them directly, we apply diffusion approximation theory and consider the Halfin–Whitt heavy traffic regime. This approach yields a formally weak limit of the joint scheduling–control problem. This limit problem, which we call the diffusion control problem (DCP), is a stochastic differential equation (SDE). Next, we present the corresponding Hamilton–Jacobi–Bellman (HJB) equation and prove the existence and uniqueness of the solution to this equation. This solution is the optimal Markov policy for the diffusion control problem, and we use this solution to devise a policy for the original joint scheduling–control problem and prove its asymptotic optimality. We designed several experiments to compare the system$ ^\prime $s performance and value functions under different control policies. Our designed joint scheduling–control policy has significant advantages in reducing the system$ ^\prime $s cost and improving service efficiency.
- multiclass queues,
- multiserver queue,
- Halfin–Whitt heavy traffic,
- diffusion control,
- HJB equation,
- asymptotic optimality
Citation: Xiaolong Li. Asymptotic optimality of a joint scheduling–control policy for parallel server queues with multiclass jobs in heavy traffic[J]. AIMS Mathematics, 2025, 10(2): 4226-4267. doi: 10.3934/math.2025196

Related Papers:

Abstract

To optimize the control of a queuing system with multiple classes of customers and multiple servers, we introduce a novel joint scheduling–control policy that includes customer admission control, service scheduling control, and service rate control. In this policy, any server can serve any class of customers; the service rate control for a server is a unique feature of this policy and is determined by the overall state of the system, not the state of a server or the class of customers it serves. Given the inherent complexity of the system$ ^\prime $s equations and the difficulty of solving them directly, we apply diffusion approximation theory and consider the Halfin–Whitt heavy traffic regime. This approach yields a formally weak limit of the joint scheduling–control problem. This limit problem, which we call the diffusion control problem (DCP), is a stochastic differential equation (SDE). Next, we present the corresponding Hamilton–Jacobi–Bellman (HJB) equation and prove the existence and uniqueness of the solution to this equation. This solution is the optimal Markov policy for the diffusion control problem, and we use this solution to devise a policy for the original joint scheduling–control problem and prove its asymptotic optimality. We designed several experiments to compare the system$ ^\prime $s performance and value functions under different control policies. Our designed joint scheduling–control policy has significant advantages in reducing the system$ ^\prime $s cost and improving service efficiency.

References

[1]	S. L. Bell, R. J. Williams, Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold polic, Ann. Appl. Probab., 11 (2001), 608–649. https://doi.org/10.1214/aoap/1015345343 doi: 10.1214/aoap/1015345343
[2]	J. M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, In: W. Fleming, P. L. Lions, Stochastic differential systems, stochastic control theory and applications, The IMA Volumes in Mathematics and Its Applications, 10 (1988), 147–186. https://doi.org/10.1007/978-1-4613-8762-6_11
[3]	E. V. Krichagina, M. I. Taksar, Diffusion approximation for GI/G/1 controlled queues, Queueing Syst., 12 (1992), 333–367. https://doi.org/10.1007/bf01158808 doi: 10.1007/bf01158808
[4]	S. Kumar, Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimality, Ann. Appl. Probab., 10 (2000), 930–961. https://doi.org/10.1214/aoap/1019487514 doi: 10.1214/aoap/1019487514
[5]	H. J. Kushner, Y. N. Chen, Optimal control of assignment of jobs to processors under heavy traffic, Stochastics Stochastic Rep., 68 (2000), 177–228. https://doi.org/10.1080/17442500008834223 doi: 10.1080/17442500008834223
[6]	L. F. Martins, S. E. Shreve, H. M. Soner, Heavy traffic convergence of a controlled, multiclass queueing system, SIAM J. Control Optim., 34 (1996), 2133–2171. https://doi.org/10.1137/s0363012994265882 doi: 10.1137/s0363012994265882
[7]	E. Plambeck, S. Kumar, J. M. Harrison, A multiclass queue in heavy traffic with throughput time constraints: asymptotically optimal dynamic controls, Queueing Syst. Theory Appl., 39 (2001), 23–54. https://doi.org/10.1023/a:1017983532376 doi: 10.1023/a:1017983532376
[8]	J. A. Van Mieghem, Dynamic scheduling with convex delay costs: the generalized $c\mu$ rule, Ann. Appl. Probab., 5 (1995), 809–833. https://doi.org/10.1214/aoap/1177004706 doi: 10.1214/aoap/1177004706
[9]	A. Weerasinghe, Optimal service rate perturbations of many server queues in heavy traffic, Queueing Syst., 79 (2015), 321–363. https://doi.org/10.1007/s11134-014-9423-9 doi: 10.1007/s11134-014-9423-9
[10]	R. Atar, A. Mandelbaum, M. I. Reiman, Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic, Ann. Appl. Probab., 14 (2004), 1084–1134. https://doi.org/10.1214/105051604000000233 doi: 10.1214/105051604000000233
[11]	S. Halfin, W. Whitt, Heavy-traffic limits for queues with many exponential servers, Oper. Res., 29 (1981), 567–588. https://doi.org/10.1287/opre.29.3.567 doi: 10.1287/opre.29.3.567
[12]	D. L. Jagerman, Some properties of the Erlang loss function, Bell Syst. Tech. J., 53 (1974), 525–551. https://doi.org/10.1002/j.1538-7305.1974.tb02756.x doi: 10.1002/j.1538-7305.1974.tb02756.x
[13]	W. H. Fleming, H. M. Soner, Controlled Markov processes and viscosity solutions, 2 Eds., New York: Springer, 2006. https://doi.org/10.1007/0-387-31071-1
[14]	A. Arapostathis, H. Hmedi, G. Pang, On uniform exponential ergodicity of markovian multiclass many-server queues in the halfin-whitt regime, Math. Oper. Res., 46 (2021), 772–796. https://doi.org/10.1287/moor.2020.1087 doi: 10.1287/moor.2020.1087
[15]	A. Arapostathis, G. Pang, Y. Zheng, Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment, Appl. Math. Opt., 84 (2021), 1857–1901. https://doi.org/10.1007/s00245-020-09698-9 doi: 10.1007/s00245-020-09698-9
[16]	Y. L. Kocağa, An approximating diffusion control problem for dynamic admission and service rate control in a G/M/N+G queue, Oper. Res. Lett., 45 (2017), 538–542. https://doi.org/10.1016/j.orl.2017.08.005 doi: 10.1016/j.orl.2017.08.005
[17]	D. Y. Sze, A queueing model for telephone operator staffing, Oper. Res., 32 (1984), 229–249. https://doi.org/10.1287/opre.32.2.229 doi: 10.1287/opre.32.2.229
[18]	M. Armony, C. Maglaras, On customer contact centers with a call-back option: customer decisions, routing rules, and system design, Oper. Res., 52 (2004), 271–292. https://doi.org/10.1287/opre.1030.0088 doi: 10.1287/opre.1030.0088
[19]	W. Dai, $n$-qubit operations on sphere and queueing scaling limits for programmable quantum computer, Quantum Inf. Process., 22 (2023), 122–164. https://doi.org/10.1007/s11128-023-03851-3 doi: 10.1007/s11128-023-03851-3
[20]	O. Garnett, A. Mandelbaum, M. I. Reiman, Designing a telephone call center with impatient customers, Manuf. Serv. Oper. Manage., 4 (2002), 208–227. https://doi.org/10.1287/msom.4.3.208.7753 doi: 10.1287/msom.4.3.208.7753
[21]	A. Weerasinghe, Controlling the running maximum of a diffusion process and an application to queueing systems, SIAM J. Control Optim., 56 (2018), 1412–1440. https://doi.org/10.1137/17m1135967 doi: 10.1137/17m1135967
[22]	W. Dai, Optimal rate scheduling via utility-maximization for $j$-user MIMO Markov fading wireless channels with cooperation, Oper. Res., 61 (2013), 1450–1462. https://doi.org/10.1287/opre.2013.1224 doi: 10.1287/opre.2013.1224
[23]	W. Dai, Platform modeling and scheduling game with multiple intelligent cloud-computing pools for big data, Math. Comput. Model. Dyn. Syst., 24 (2018), 506–552. https://doi.org/10.1080/13873954.2018.1516677 doi: 10.1080/13873954.2018.1516677
[24]	W. Dai, Quantum-computing with AI & blockchain: modelling, fault tolerance and capacity scheduling, Math. Comput. Model. Dyn. Syst., 25 (2019), 523–559. https://doi.org/10.1080/13873954.2019.1677725 doi: 10.1080/13873954.2019.1677725
[25]	S. N. Ethier, T. G. Kurtz, Markov processes: characterization and convergence, New York: Wiley, 1986. https://doi.org/10.1002/9780470316658
[26]	J. M. Harrison, A. Zeevi, Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime, Oper. Res., 52 (2004), 243–257. https://doi.org/10.1287/opre.1030.0084 doi: 10.1287/opre.1030.0084
[27]	A. A. Puhalskii, M. I. Reiman, The multiclass GI/PH/N queue in the Halfin–Whitt regime, Adv. Appl. Probab., 32 (2000), 564–595. https://doi.org/10.1017/s0001867800010089 doi: 10.1017/s0001867800010089
[28]	W. Whitt, Stochastic–process limits, New York: Springer, 2002. https://doi.org/10.1007/b97479
[29]	D. J. Higham, An algorithmic introduction to numerical simulation of stochastic differential equations, SIAM Rev., 43 (2001), 525–546. https://doi.org/10.1137/s0036144500378302 doi: 10.1137/s0036144500378302
[30]	W. Dai, Convolutional neural network based simulation and analysis for backward stochastic partial differential equations, Comput. Math. Appl., 119 (2022), 21–58. https://doi.org/10.1016/j.camwa.2022.05.019 doi: 10.1016/j.camwa.2022.05.019
[31]	W. Fang, M. B. Giles, Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift: Part I, finite time interval, arXiv Preprint, 2016. https://doi.org/10.48550/arXiv.1609.08101
[32]	I. Karatzas, S. E. Shreve, Brownian motion and stochastic calculus, 2 Eds., New York: Springer, 1998. https://doi.org/10.1007/978-1-4612-0949-2
[33]	H. J. Kushner, Optimal discounted stochastic control for diffusion processes, SIAM J. Control, 5 (1967), 520–531. https://doi.org/10.1137/0305032 doi: 10.1137/0305032
[34]	O. A. Ladyzhenskaya, N. N. Uraltseva, Linear and quasilinear elliptic equations, New York: Academic Press, 1968.
[35]	W. Rudin, Real and complex analysis, New York: Wiley, 1987.
[36]	P. Protter, Stochastic integration and differential equations: a new approach, Berlin: Springer, 1990. https://doi.org/10.1007/978-3-662-02619-9_6
[37]	P. Billingsley, Convergence of probability measures, New York: John Wiley & Sons, 1999. https://doi.org/10.1002/9780470316962

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)