Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-28T17:47:10.711Z Has data issue: false hasContentIssue false
  • English
  • Français

STABILIZING PERFORMANCE IN NETWORKS OF QUEUES WITH TIME-VARYING ARRIVAL RATES

Published online by Cambridge University Press:  09 July 2014

Yunan Liu  and
Ward Whitt
Yunan Liu
Affiliation:
Department of Industrial Engineering, North Carolina State University, Raleigh, NC 27695, USA E-mail: [email protected]
Ward Whitt
Affiliation:
Department of Industrial Engineering and Operations Research, Columbia University New York, NY 10027, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper investigates extensions to feed-forward queueing networks of an algorithm to set staffing levels (the number of servers) to stabilize performance % at Quality of Service (QoS) targets in an Mt/GI/st+GI multi-server queue with a time-varying arrival rate. The model has a non-homogeneous Poisson process (NHPP), customer abandonment, and non-exponential service and patience distributions. For a single queue, simulation experiments showed that the algorithm successfully stabilizes abandonment probabilities and expected delays over a wide range of Quality-of-Service (QoS) targets. A limit theorem showed that stable performance at fixed QoS targets is achieved asymptotically as the scale increases (by letting the arrival rate grow while holding the service and patience distributions fixed). Here we extend that limit theorem to a feed-forward queueing network. However, these fixed QoS targets provide low QoS as the scale increases. Hence, these limits primarily support the algorithm with a low QoS target. For a high QoS target, effectiveness depends on the NHPP property, but the departure process never is exactly an NHPP. Thus, we investigate when a departure process can be regarded as approximately an NHPP. We show that index of dispersion for counts is effective for determining when a departure process is approximately an NHPP in this setting. In the important common case when all queues have high QoS targets, we show that both: (i) the departure process is approximately an NHPP from this perspective and (ii) the algorithm is effective.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 28 , Issue 4 , October 2014 , pp. 419 - 449
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Aksin, O.Z., Armony, M. & Mehrotra, V. (2007). The modern call center: a multi-disciplinary perspective on operations management research. Production and Operations Management 16: 665–688.Google Scholar
2.Albin, S.L. (1982). On Poisson approximations for superposition arrival processes in queues. Management Science 28(2): 126–137.Google Scholar
3.Albin, S.L. (1984). Approximating a point process by a renewal process, II: superposition arrival processes to queues. Operations Research 32(5): 1133–1162.CrossRefGoogle Scholar
4.Armony, M., Israelit, S., Mandelbaum, A., Marmor, Y., Tseytlin, Y. & Yom-Tov, G. (2011). Patient flow in hospitals: a data-based queueing-science perspective. New York University, http://www.stern.nyu.edu/om/faculty/armony/.Google Scholar
5.Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S. & Zhao, L. (2005). Statistical analysis of a telephone call center: a queueing-science perspective. Journal of American Statistics Association 100: 36–50.Google Scholar
6.Chevalier, P. & Tabordon, N. (2003). Overflow analysis and cross-trained servers. International Journal of Production Economics 86(1): 47–60.CrossRefGoogle Scholar
7.Cox, D.R. & Lewis, J.A.W. (1966). The Statistical Analysis of Series of Events. London: Methuen.Google Scholar
8.Defraeye, M. & van Nieuwenhuyse, I. (2013). Controlling excessive waiting times in small service systems with time-varying demand: an extension of the ISA algorithm. Decision Support Systems 54(4): 1558–1567.CrossRefGoogle Scholar
9.Durbin, J. (1961). Some methods for constructing exact tests. Biometrika 48(1): 41–55.Google Scholar
10.Eick, S.G., Massey, W.A. & Whitt, W. (1993). M t/G/∞ queues with sinusoidal arrival rates. Management Science 39: 241–252.CrossRefGoogle Scholar
11.Eick, S.G., Massey, W.A. & Whitt, W. (1993). The physics of the M t/G/∞ queue. Operations Research 41: 731–742.CrossRefGoogle Scholar
12.Feldman, Z., Mandelbaum, A., Massey, W.A. & Whitt, W. (2008). Staffing of time-varying queues to achieve time-stable performance. Management Science 54(2): 324–338.Google Scholar
13.Fendick, K.W. & Whitt, W. (1989). Measurements and approximations to describe the offered traffic and predict the average workload in a single-server queue. Proceedings of the IEEE 77(1): 171–194.Google Scholar
14.Garnett, O., Mandelbaum, A. & Reiman, M.I. (2002). Designing a call center with impatient customers. Manufacturing and Service Operations Management 4(3): 208–227.Google Scholar
15.Gebhardt, I. & Nelson, B.L. (2009). Transforming renewal processes for simulation of non-stationary arrival processes. INFORMS Journal on Computing 21: 630–640.Google Scholar
16.Green, L.V., Kolesar, P.J. & Whitt, W. (2007). Coping with time-varying demand when setting staffing requirements for a service system. Production and Operations Management 16: 13–29.Google Scholar
17.Ingolfsson, I., Akhmetshina, E., Li, Y. & Wu, X. (1979). A survey and experimental comparison of service-level-approximation methods for nonstationary M(t)/M/s(t) queueing systems with exhaustive discipline. INFORMS Journal on Computing 19(2): 201–214.CrossRefGoogle Scholar
18.Jennings, O.B., Mandelbaum, A., Massey, W.A. & Whitt, W. (1996). Server staffing to meet time-varying demand. Management Science 42: 1383–1394.Google Scholar
19.Kim, S.-H. & Whitt, W. (2014). Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes? Manufacturing and Service Operations Management, forthcoming.Google Scholar
20.Kim, S.-H. & Whitt, W. (2014). Choosing arrival process models for service systems: tests of a nonhomogeneous Poisson process. Naval Research Logistics 61(1): 66–90.Google Scholar
21.Koizumi, N., Kuno, E. & Smith, T.E. (2005). Modeling patient flows using a queueing network with blocking. Health Care Management Science 8: 49–60.CrossRefGoogle Scholar
22.Korporaal, R., Ridder, A., Kloprogge, P. & Dekker, R. (2000). An analytical model for capacity planning of prisons in the Netherlands. The Journal of the Operational Research Society 51(11): 1228–1237.Google Scholar
23.Larson, R.C., Cahn, M.F. & Shell, M.C. (1990). The New York city arrest-to-arraignment system. Interfaces 23(1): 76–96.Google Scholar
24.Lewis, P.A.W. (1965). Some results on tests for Poisson processes. Biometrika 52(1): 67–77.Google Scholar
25.Li, A. & Whitt, W. (2014). Approximate blocking probabilities for loss models with independence and distribution assumptions relaxed. Performance Evaluation.Google Scholar
26.Liu, Y., Gorton, I. & Zhu, L. (2007). Performance prediction of service-oriented applications on an enterprise service bus. Thirty-first Computer Software and Applications Conference (COMPSAC 2007) 36: 1–8.Google Scholar
27.Liu, Y. & Whitt, W. (2011). A network of time-varying many-server fluid queues with customer abandonment. Operations Research 59: 835–846.Google Scholar
28.Liu, Y. & Whitt, W. (2012). The G t/GI/s t+GI many-server fluid queue. Queueing Systems 71: 405–444.Google Scholar
29.Liu, Y. & Whitt, W. (2012). A many-server fluid limit for the G t/GI/s t+GI queueing model experiencing periods of overloading. Operations Research Letters 40: 307–312.Google Scholar
30.Liu, Y. & Whitt, W. (2012). Stabilizing customer abandonment in many-server queues with time-varying arrivals. Operations Research 60: 1551–1564.Google Scholar
31.Liu, Y. & Whitt, W. (2014). Algorithms for time-varying networks of many-server fluid queues. Informs Journal on Computing 26: 59–73.Google Scholar
32.Liu, Y. & Whitt, W. (2014). Many-server heavy-traffic limits for queues with time-varying parameters. Annals of Applied Probability 24: 378–421.Google Scholar
33.Mandelbaum, A., Massey, W.A. & Reiman, (1998). Strong approximations for Markovian service networks. Queueing Systems 30: 149–201.Google Scholar
34.Massey, W.A. & Pender, J. (2013). Gasussian skewness approximation for dynamic rate multi-server queues with abandonment. Queueing Systems 75: 243–277.Google Scholar
35.Massey, W.A. & Whitt, W. (1993). Networks of infinite-server queues with nonstationary Poisson input. Queueing Systems 13(1): 183–250.Google Scholar
36.Massey, W.A. & Whitt, W. (1994). Unstable asymptotics for nonstationary queues. Mathematics of Operations Research 19(2): 267–291.Google Scholar
37.Sriram, K. & Whitt, W. (1986). Characterizing superposition arrival processes in packet multiplexers for voice and data. IEEE Journal on Selected Areas in Communications SAC-4(6): 833–846.Google Scholar
38.Stolletz, R. (2008). Approximation of the nonstationary M(t)/M(t)/c(t) queue using stationary models: the stationary backlog-carryover approach. Biometrika 190(2): 478–493.Google Scholar
39.Whitt, W. (1982). Approximating a point process by a renewal process: two basic methods. Operations Research 30: 125–147.CrossRefGoogle Scholar
40.Whitt, W. (1984). Departures from a queue with many busy servers. Mathematics of Operations Res 9(4): 534–544.Google Scholar
41.Whitt, W. (2002). Stochastic-Process Limits. New York: Springer.Google Scholar
42.Whitt, W. (2005). Engineering solution of a basic call-center model. Management Science 51: 221–235.Google Scholar
43.Yom-Tov, G. & Mandelbaum, A. (2010). The Erlang-R queue: time-varying QED queues with re-entrant customers in support of healthcare staffing. Working paper, the Technion.Google Scholar