×

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic. (English) Zbl 1208.60093

In this paper a stochastic processing system with variable arrival and service rates both drift control policy as well as rejection control policy are given consideration. The authors established a necessary and sufficient condition for the optimal buffer size. Then, with the aid of the assumed cost function, including a penalty for each rejected customers, the explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) was determined. In detail, an optimal buffer size and an optimal service rate for the queueing system in heavy traffic was established. The above referenced BCP problem addresses the cost structure for the control problem, as well as the main result of this paper. In my opinion it provides the proofs confirming the asymptotic optimality for the queueing system in heavy traffic. Furthermore, the problem of optimal buffer size and dynamic rate control for this queueing system with the rejection and impatient customers was effectively clarified. The specification about the BCP problem can be studied independently of other parts.

MSC:

60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60J70 Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
90B22 Queues and service in operations research
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ata, B., Dynamic control of a multiclass queue with thin arrival streams, Oper. Res., 54, 5, 876-892 (2006) · Zbl 1167.90439
[2] Ata, B.; Harrison, J. M.; Shepp, L. A., Drift rate control of a Brownian processing system, Ann. Appl. Probab., 15, 2, 1145-1160 (2005) · Zbl 1069.60074
[3] Ata, B.; Kumar, S., Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies, Ann. Appl. Probab., 15, 1A, 331-391 (2005) · Zbl 1071.60081
[4] Ata, B.; Shneorson, S., Dynamic control of an M/M/1 service system with adjustable arrival and service rates, Manage. Sci., 52, 11, 1778-1791 (2006) · Zbl 1232.90136
[5] Bell, S. L.; Williams, R. J., Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy, Ann. Appl. Probab., 11, 3, 608-649 (2001) · Zbl 1015.60080
[6] Bell, S. L.; Williams, R. J., Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: asymptotic optimality of a threshold policy, Electron. J. Probab., 10, 33, 1044-1115 (2005), (electronic) · Zbl 1109.60075
[7] Billingsley, P., (Convergence of Probability Measures. Convergence of Probability Measures, Wiley Series in Probability and Statistics: Probability and Statistics (1999), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York), A Wiley-Interscience Publication · Zbl 0944.60003
[8] Budhiraja, A.; Ghosh, A. P., A large deviations approach to asymptotically optimal control of crisscross network in heavy traffic, Ann. Appl. Probab., 15, 3, 1887-1935 (2005) · Zbl 1080.60084
[9] Budhiraja, A.; Ghosh, A. P., Diffusion approximations for controlled stochastic networks: an asymptotic bound for the value function, Ann. Appl. Probab., 16, 4, 1962-2006 (2006) · Zbl 1125.60096
[10] Ethier, S. N.; Kurtz, T. G., (Markov Processes: Characterization and Convergence. Markov Processes: Characterization and Convergence, Wiley Series in Probability and Mathematical Statistics (1986), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York) · Zbl 0592.60049
[11] Fleming, W. H.; Soner, H. M., (Controlled Markov Processes and Viscosity Solutions. Controlled Markov Processes and Viscosity Solutions, Stochastic Modelling and Applied Probability, vol. 25 (2006), Springer: Springer New York) · Zbl 1105.60005
[12] George, J. M.; Harrison, J. M., Dynamic control of a queue with adjustable service rate, Oper. Res., 49, 5, 720-731 (2001) · Zbl 1163.90420
[13] Ghosh, A. P.; Weerasinghe, A., Optimal buffer size for a stochastic processing network in heavy traffic, Queueing Syst., 55, 3, 1572-9443 (2007)
[14] Harrison, J. M.; Wein, L. M., Scheduling networks of queues: heavy traffic analysis of a simple open network, Queueing Syst., 5, 4, 265-279 (1989) · Zbl 0684.90034
[15] Harrison, J. M.; Wein, L. M., Scheduling networks of queues: heavy traffic analysis of a two-station closed network, Oper. Res., 38, 6, 1052-1064 (1990) · Zbl 0723.90026
[16] Hartman, P., Ordinary Differential Equations (1964), John Wiley and Sons Inc. · Zbl 0125.32102
[17] Kruk, L.; Lehoczky, J.; Ramanan, K.; Shreve, S., An explicit formula for the Skorokhod map on \([0, a]\), Ann. Probab., 35, 5, 1740-1768 (2007) · Zbl 1139.60017
[18] Kumar, S., Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimality, Ann. Appl. Probab., 10, 3, 930-961 (2000) · Zbl 1073.60538
[19] Kumar, S.; Muthuraman, M., A numerical method for solving singular stochastic control problems, Oper. Res., 52, 4, 56-582 (2004) · Zbl 1165.49305
[20] Kurtz, T. G., (Approximation of Population Processes. Approximation of Population Processes, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 36 (1981), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, Pa) · Zbl 0465.60078
[21] Kushner, H. J., (Heavy Traffic Analysis of Controlled Queueing and Communication Networks. Heavy Traffic Analysis of Controlled Queueing and Communication Networks, Applications of Mathematics (New York), vol. 47 (2001), Springer-Verlag: Springer-Verlag New York), Stochastic Modelling and Applied Probability · Zbl 0988.90004
[22] Meyer, P. A., Un cours sur les intégrales stochastiques, (Séminaire de Probabilités, X (Seconde partie: Théorie des intégrales stochastiques, Univ. Strasbourg, Strasbourg, année universitaire 1974/1975). Séminaire de Probabilités, X (Seconde partie: Théorie des intégrales stochastiques, Univ. Strasbourg, Strasbourg, année universitaire 1974/1975), Lecture Notes in Math., vol. 511 (1976), Springer: Springer Berlin), 245-400 · Zbl 0374.60070
[23] J. Reed, A.R. Ward, A diffusion approximation for a generalized Jackson network with reneging. in: Proceedings of the 42nd Annual Allerton Conference on Communication, Control, and Computing, 2004.; J. Reed, A.R. Ward, A diffusion approximation for a generalized Jackson network with reneging. in: Proceedings of the 42nd Annual Allerton Conference on Communication, Control, and Computing, 2004.
[24] Reed, J.; Ward, A. R., Approximating the GI/GI/1+GI queue with a nonlinear drift diffusion: Hazard rate scaling in heavy traffic, Math. Oper. Res., 33, 3, 606-644 (2008) · Zbl 1231.90142
[25] Skorokhod, A. V., Stochastic equations for diffusions in a bounded region, Theory Probab. Appl., 6, 264-274 (1961) · Zbl 0215.53501
[26] Stolyar, A. L., Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic, Ann. Appl. Probab., 14, 1, 1-53 (2004) · Zbl 1057.60092
[27] Ward, A. R.; Glynn, P. W., A diffusion approximation for a Markovian queue with reneging, Queueing Syst., 43, 1-2, 103-128 (2003) · Zbl 1054.60100
[28] Ward, A. R.; Glynn, P. W., A diffusion approximation for a GI/GI/1 queue with balking or reneging, Queueing Syst., 50, 4, 371-400 (2005) · Zbl 1094.60064
[29] Ward, A.; Kumar, S., Asymptotically optimal admission control of a queue with impatient customers, Math. Oper. Res., 33, 1, 167-202 (2008) · Zbl 1159.90017
[30] Weerasinghe, A., An Abelian limit approach to a singular ergodic control problem, SIAM J. Control Optim., 46, 2, 714-737 (2007) · Zbl 1330.93246
[31] Whitt, W., (Stochastic-process Limits. Stochastic-process Limits, Springer Series in Operations Research (2002), Springer-Verlag: Springer-Verlag New York) · Zbl 0993.60001
[32] Yamada, K., Diffusion approximation for open state-dependent queueing networks in the heavy traffic situation, Ann. Appl. Probab., 5, 4, 958-982 (1995) · Zbl 0870.60025
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.