Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-27T14:35:30.578Z Has data issue: false hasContentIssue false
  • English
  • Français

OPTIMAL STATIC ASSIGNMENT AND ROUTING POLICIES FOR SERVICE CENTERS WITH CORRELATED TRAFFIC

Published online by Cambridge University Press:  17 March 2014

Nelson Lee ,
Vidyadhar G. Kulkarni  and
Yasutaka Hirasawa
Nelson Lee
Affiliation:
Department of Statistics and Operations Research, University of North Carolina, Chapel Hill, NCUSA. E-mail: [email protected]; [email protected]
Vidyadhar G. Kulkarni
Affiliation:
Department of Statistics and Operations Research, University of North Carolina, Chapel Hill, NCUSA. E-mail: [email protected]; [email protected]
Yasutaka Hirasawa
Affiliation:
NetApp, Research Triangle Park, NCUSA. E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A service center is a facility with multiple heterogeneous servers providing specialized service to multiple types of customers. An assignment policy specifies which server is enabled to serve which types of customer, and a routing policy specifies which server a customer will be routed to for service. Thus, a server can be enabled to serve many types of customer, and a customer may have many alternate servers who can serve him. This paper aims to provide decision models to determine optimal static assignment and routing policies, explicitly taking into account the stochastic fluctuations of demand along with the autocorrelations and cross-correlations of the different traffic streams. We consider several possible performance measures and formulate the optimization problem as a mixed integer nonlinear programming problem. We also develop an efficient heuristic algorithm to enhance scalability. Finally, we compare the different policies using the heuristic algorithms. We observe numerically that the routing policy tries to combine the negatively correlated traffic streams, and separate the positively correlated traffic streams.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 28 , Issue 3 , July 2014 , pp. 279 - 311
Copyright
Copyright © Cambridge University Press 2014 

References

1.Adan, I.J.B.F. & Kulkarni, V.G. (2003). Single-server queue with Markov-dependent inter-arrival and service times. Queueing Systems 45: 113–134.CrossRefGoogle Scholar
2.Andradóttir, S., Ayhan, H. & Down, D.G. (2001). Server assignment policies for maximizing the steady-state throughput of finite queueing systems. Management Science 47(10): 1421–1439.CrossRefGoogle Scholar
3.Andradóttir, S., Ayhan, H. & Down, D.G. (2003). Dynamic server allocation for queueing networks with flexible servers. Operations Research 51(6): 952–968.CrossRefGoogle Scholar
4.Anselmi, J., Amaldi, E. & Cremonesi, P. (2008). Service consolidation with end-to-end response time constraints. In Proceedings of the 2008 34th Euromicro Conference Software Engineering and Advanced Applications, SEAA ’08, pp. 345–352, Washington, DC, USA, IEEE Computer Society.CrossRefGoogle Scholar
5.Anselmi, J., Cremonesi, P. & Amaldi, E. (2009). On the consolidation of data-centers with performance constraints. In Architectures for Adaptive Software Systems, vol. 5581 of Lecture Notes in Computer Science (Mirandola, R., Gorton, I. & Hofmeister, C., Eds.), Berlin/Heidelberg: Springer, pp. 163–176.Google Scholar
6.Bassamboo, A., Harrison, J.M. & Zeevi, A. (2006). Design and control of a large call center: asymptotic analysis of an LP-based method. Operations Research 54(3): 419–435.CrossRefGoogle Scholar
7.Bichler, M., Setzer, T. & Speitkamp, B. (2006). Capacity planning for virtualized servers. Presented at Workshop on Information Technologies and Systems (WITS), Milwaukee, Wisconsin, USA.Google Scholar
8.Borst, S.C. (1995). Optimal probabilistic allocation of customer types to servers. SIGMETRICS Performance Evaluation Review 23(1): 116–125CrossRefGoogle Scholar
9.Buzacott, J.A. & Shanthikumar, J.G. (1992). Design of manufacturing systems using queueing models. Queueing Systems 12(1): 135–213.CrossRefGoogle Scholar
10.Chen, Y., Das, A., Qin, W., Sivasubramaniam, A., Wang, Q. & Gautam, N. (2005). Managing server energy and operational costs in hosting centers. SIGMETRICS Performance Evaluation Review 33: 303–314.CrossRefGoogle Scholar
11.de Véricourt, F. & Jennings, O.B. (2011). Nurse staffing in medical units: a queueing perspective. Operations Research 59(6): 1320–1331.CrossRefGoogle Scholar
12.Good, I.J. (1961). The frequency count of a Markov chain and the transition to continuous time. The Annals of Mathematical Statistics 32(1): 41–48.CrossRefGoogle Scholar
13.Green, L. (2006). Queueing analysis in healthcare. In Patient Flow: Reducing Delay in Healthcare Delivery. volume 91 of International Series in Operations Research & Management Science, US: Springer, pp. 281–307.Google Scholar
14.Guo, X., Lu, Y. & Squillante, M.S. (2004). Optimal probabilistic routing in distributed parallel queues. SIGMETRICS Performance Evaluation Review 32(2): 53–54.CrossRefGoogle Scholar
15.Gurvich, I., Armony, M. & Mandelbaum, A. (2008). Service-level differentiation in call centers with fully flexible servers. Management Science 54(2): 279–294.CrossRefGoogle Scholar
16.Gurvich, I. & Whitt, W. (2010). Service-level differentiation in many-server service systems via queue-ratio routing. Operations Research 58(2): 316–328.CrossRefGoogle Scholar
17.Harrison, J.M. & Zeevi, A. (2005). A method for staffing large call centers based on stochastic fluid models. Manufacturing & Service Operations Management 7(1): 20–36.CrossRefGoogle Scholar
18.Jaumard, B., Semet, F. & Vovor, T. (1998). A generalized linear programming model for nurse scheduling. European Journal of Operational Research 107(1): 1–18.CrossRefGoogle Scholar
19.Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R. & Graham, R.L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing 3(4): 299–325.CrossRefGoogle Scholar
20.Kulkarni, V.G. (1995). Modeling and Analysis of Stochastic Systems. Boca Raton: Chapman & Hall/CRC.Google Scholar
21.Kwak, N.K. & Lee, C. (1997). A linear goal programming model for human resource allocation in a health-care organization. Journal of Medical Systems 21: 129–140.CrossRefGoogle Scholar
22.Li, T.-H. (2007). A statistical framework of optimal workload consolidation with application to capacity planning for on-demand computing. Journal of the American Statistical Association 102(479): 841–855.CrossRefGoogle Scholar
23.Sethuraman, J. & Squillante, M.S. (1999). Optimal stochastic scheduling in multiclass parallel queues. SIGMETRICS Performance Evaluation Review 27(1): 93–102.CrossRefGoogle Scholar
24.Shanthikumar, J.G. & Xu, S.H. (1997). Asymptotically optimal routing and service rate allocation in a multiserver queueing system. Operations Research 45(3): 464–469.CrossRefGoogle Scholar
25.Speitkamp, B. & Bichler, M. (2010). A mathematical programming approach for server consolidation problems in virtualized data centers. IEEE Transactions on Services Computing 3: 266–278.CrossRefGoogle Scholar
26.Tekin, S., Andradóttir, S. & Down, D. (2012). Dynamic server allocation for unstable queueing networks with flexible servers. Queueing Systems 70: 45–79.CrossRefGoogle Scholar
27.Vogels, W. (2008). Beyond server consolidation. Queue 6(1): 20–26.CrossRefGoogle Scholar
28.Wallace, R.B. & Whitt, W. (2005). A staffing algorithm for call centers with skill-based routing. Manufacturing & Service Operations Management 7(4): 276–294.CrossRefGoogle Scholar
29.Wang, Y.-T. & Morris, R.J.T. (1985). Load sharing in distributed systems. IEEE Transactions on Computers C-34(3): 204–217.CrossRefGoogle Scholar
30.Whitt, W. (1982). Refining diffusion approximations for queues. Operations Research Letters 1(5): 165–169.CrossRefGoogle Scholar
31.Whitt, W. (2006). A multi-class fluid model for a contact center with skill-based routing. AEU — International Journal of Electronics and Communications 60(2): 95–102.CrossRefGoogle Scholar
32.Yankovic, N. & Green, L.V. (2011). Identifying good nursing levels: a queuing approach. Operations Research 59(4): 942–955.CrossRefGoogle Scholar