Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 1 (2011) open journal systems 


An ODE for an overloaded X model involving a stochastic averaging principle

Ohad Perry, CWI
Ward Whitt, IEOR, Columbia University


Abstract
We study an ordinary differential equation (ODE) arising as the many-server heavy-traffic fluid limit of a sequence of overloaded Markovian queueing models with two customer classes and two service pools. The system, known as the X model in the call-center literature, operates under the fixed-queue-ratio-with-thresholds (FQR-T) control, which we proposed in a recent paper as a way for one service system to help another in face of an unanticipated overload. Each pool serves only its own class until a threshold is exceeded; then one-way sharing is activated with all customer-server assignments then driving the two queues toward a fixed ratio. For large systems, that fixed ratio is achieved approximately. The ODE describes system performance during an overload. The control is driven by a queue-difference stochastic process, which operates in a faster time scale than the queueing processes themselves, thus achieving a time-dependent steady state instantaneously in the limit. As a result, for the ODE, the driving process is replaced by its long-run average behavior at each instant of time; i.e., the ODE involves a heavy-traffic averaging principle (AP).

AMS 2000 subject classifications: 60K25; 90B15; 90B22; 37C75; 93D05

Keywords: Many-server queues, averaging principle, heavy traffic, deterministic fluid approximation, ordinary differential equations, overload control

Creative Common LOGO

Full Text: PDF


Perry, Ohad, Whitt, Ward, An ODE for an overloaded X model involving a stochastic averaging principle, Stochastic Systems, 1, (2011), 59-108 (electronic). DOI: 10.1214/10-SSY009.

References

[1]    Abate, J., Choudhury, G. L., Whitt, W. (1994). Asymptotics for steady-state tail probabilities in structured Markov queueing models. Stochastic Models 10 99–143. MR1259856

[2]    Bassamboo, A., Zeevi, A. (2009). On a data-driven method for staffing large call centers. Oper. Res. 57, 714–726.

[3]    Choudhury, G. L., Whitt, W. (1994). Heavy-traffic asymptotic expansions for the asymptotic decay rates in the BMAP/G/1 queue. Stochastic Models 10 453–498. MR1268561

[4]    Coddington, E. A., Levinson, N. (1955). Theory of Ordinary Differential Equations, McGraw-Hill, New York. MR0069338

[5]    Coffman, E. G., Puhalskii, A. A., Reiman, M. I. (1995). Polling systems with zero switchover times: a heavy-traffic averaging principle. Annals of Applied Probability 5 681–719. MR1359825

[6]    Ethier, S. N., Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. MR0838085

[7]    Gurvich, I., Whitt, W. (2009). Queue-and-idleness-ratio controls in many-server service systems. Math. Oper. Res. 34 (2) 363–396. MR2554064

[8]    He, Q. (1995). Differentiability of the matrices R and G in the matrix analytic method. Stochastic Models 11 (1) 123–132. MR1316771

[9]    Hunt, P. J., Kurtz, T. G. (1994). Large loss networks. Stochastic Processes and their Applications 53 363–378. MR1302919

[10]    Khalil, H. K. (2002). Nonlinear Systems. Prentice Hall, New Jersey.

[11]    Latouche, G., Ramaswami, V. (1999). Introduction to Matrix Analystic Methods in Stochastic Modeling, Siam and ASA, Philadelphia MR1674122

[12]    Marquez, H. J. (2003). Nonlinear Control Systems. Wiley, New York.

[13]    Neuts, M. F. (1986). The caudal characteristic curve of queues. Adv. Appl. Prob. 18 221–254. MR0827337

[14]    Neuts, M. F. (1989). Structured Stochastic Matrices of M∕G∕1 Type and Their Applications, Marcel Dekker, New York. MR1010040

[15]    Pang, G., Talreja, R., Whitt, W. (2007). Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probability Surveys 4, 193–267. MR2368951

[16]    Perry, O., Whitt, W. (2009). Responding to unexpected overloads in large-scale service systems. Management Sci., 55 (8) 1353–1367.

[17]    Perry, O., Whitt, W. (2010a). A fluid limit for an overloaded X model via an averaging principle. working paper, Columbia University, NY. Available at: http://www.columbia.edu/ww2040/allpapers.html

[18]    Perry, O., Whitt, W. (2010b). Gaussian approximations for an overloaded X model via an averaging principle. working paper, Columbia University, NY.Available at: http://www.columbia.edu/ww2040/allpapers.html

[19]    Perry, O., Whitt, W. (2011). A fluid approximation for service systems responding to unexpected overloads. Operations Res., forthcoming Available at: http://www.columbia.edu/ww2040/allpapers.html

[20]    Stolyar, A. L., Tezcan, T. (2010). Control of systems with flexible multi-server pools: a shadow routing approach. Queueing Systems 66, 1–51. MR2674107

[21]    Teschl, G. (2009). Ordinary Differential Equations and Dynamical Systems, Universit├Ąt Wien. Available online: www.mat.univie.ac.at/gerald/ftp/book-ode/ode.pdf

[22]    Whitt, W. (2002). Stochastic-Process Limits, New York, Springer MR1876437

[23]    Whitt, W. (2004). Efficiency-driven heavy-traffic approximations for many-server queues with abandonments. Management Sci. 50 (10) 1449–1461.




Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238