Abstract
We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b *>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b *>0.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ata B. Dynamic control of a multiclass queue with thin arrival streams. Oper Res 2006;54(5):876–92.
Ata B, Harrison JM, Shepp LA. Drift rate control of a Brownian processing system. Ann Appl Probab 2005;15:1145–60.
Ata B, Shneorson S. Dynamic control of an M/M/1 service system with adjustable arrival and service rates. Manag Sci 2006;52(11):1778–91.
Bell SL, Williams RJ. Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. Ann Appl Probab 2001;11:608–49.
Borkar VS, Ghosh MK. Ergodic control of muti-dimensional diffusions I: the existence results. SIAM J Control Optim 1988;26:112–26.
Budhiraja A, Ghosh AP. A large deviations approach to asymptotically optimal control of crisscross network in heavy traffic. Ann Appl Probab 2005;15(3):1887–935.
Budhiraja A, Ghosh AP. Diffusion approximations for controlled stochastic networks: an asymptotic bound for the value function. Ann Appl Probab 2006;16(4):1962–2006.
Fleming WH, Soner HM. Controlled Markov processes and viscosity solutions. New York: Springer; 1993.
Foschini GJ, Salz J. A basic dynamic routing problem and diffusion. IEEE Trans Commun 1978;26:320–7.
George JM, Harrison JM. Dynamic control of a queue with adjustable service rate. Oper Res 2001;49:720–31.
Harrison JM. Brownian models of queueing networks with heterogeneous customer population. In Stochastic differential systems, stochastic control theory and applications. IMA volumes in mathematics and its applications. vol 10. New York: Springer; 1988. p. 147–86.
Harrison JM, Zeevi A. Dynamic scheduling of a multi-class queue in the Halfin-Whitt heavy traffic regime. Oper Res 2004;52:243–57.
Hartman P. Ordinary differential equations. New York: Wiley; 1964.
Karatzas I. A class of singular stochastic control problems. Adv Appl Probab 1983;15:225–54.
Kumar S, Muthuraman M. A numerical method for solving singular stochastic control problems. Oper Res 2004;52(4):563–82.
Kushner HJ. Optimality conditions for the average cost per unit time problem with a diffusion model. SIAM J Control Optim 1978;16:330–46.
Kushner HJ. Heavy traffic analysis of controlled queueing and communication networks. New York: Springer; 2001.
Kushner HJ, Dupuis P. Numerical methods for stochastic control problems in continuous time. New York: Springer; 2001.
Meyer PA. Un cours sur les integrales stochastiques, seminare de probabilites X. Lecture notes in mathematics. vol 511. New York: Springer; 1974.
Ocone D, Weerasinghe A. Degenerate variance control in the one dimensional stationary case. Electron J Probab 2003;8:1–27.
Protter MH, Weinberger HF. Maximum principles in differential equations. New York: Springer; 1984.
Shreve SE, Soner HM. Optimal investment and consumption with transaction costs. Ann Appl Probab 1994;4:609–92.
Turner SRE. A join the shorter queue model in heavy traffic. J Appl Probab 2000;37(1):212–23.
Ward AR, Kumar S. (2006). Asymptotically optimal admission control of a queue with impatient customers. Preprint http://www.isye.gatech.edu/~amy/PAPERS/RenegeControlFinal.pdf.
Weerasinghe A. Stationary control for Ito processes. Adv Appl Probab 2002;34:128–40.
Weerasinghe A. A bounded variation control problem for diffusion processes. SIAM J Control Optim 2005;44:389–417.
Author information
Authors and Affiliations
Corresponding author
Additional information
A.P. Ghosh’s research supported by NSF grant DMS-0608634.
A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.
Rights and permissions
About this article
Cite this article
Ghosh, A.P., Weerasinghe, A.P. Optimal buffer size for a stochastic processing network in heavy traffic. Queueing Syst 55, 147–159 (2007). https://doi.org/10.1007/s11134-007-9012-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-007-9012-2
Keywords
- Stochastic control
- Ergodic control
- Dynamic scheduling
- Queueing systems
- Diffusion approximations
- Heavy traffic limits
- Optimal buffer size
- Hamilton–Jacobi–Bellman equations