Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-23T08:34:01.576Z Has data issue: false hasContentIssue false
  • English
  • Français

DYNAMIC ROUTING OF CUSTOMERS WITH GENERAL DELAY COSTS IN A MULTISERVER QUEUING SYSTEM

Published online by Cambridge University Press:  16 February 2009

Nilay Tanik Argon ,
Li Ding ,
Kevin D. Glazebrook  and
Serhan Ziya
Nilay Tanik Argon
Affiliation:
Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599 E-mail: nilay@unc.edu
Li Ding
Affiliation:
Durham Business SchoolDurham UniversityDurham, DH1 3LB, UK E-mail: li.ding@durham.ac.uk
Kevin D. Glazebrook
Affiliation:
Department of Mathematics and Statistics, Lancaster University Management School, Bailrigg, Lancaster LA1 4YX, UK E-mail: k.glazebrook@lancaster.ac.uk
Serhan Ziya
Affiliation:
Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599 E-mail: ziya@unc.edu
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.

We consider a network of parallel service stations each modeled as a single-server queue. Each station serves its own dedicated customers as well as generic customers who are routed from a central controller. We suppose that the cost incurred by a customer is an increasing function of her time spent in the system. In a significant advance on most previous work, we do not require waiting costs to be convex, still less linear. With the objective of minimizing the long-run average waiting cost, we develop two heuristic routing policies, one of which is based on dynamic programming policy improvement and the other on Lagrangian relaxation. In developing the latter policy, we show that each station is “indexable” under mild conditions for customers’ waiting costs and also prove some structural results on the admission control problem that naturally arises as a result of the Lagrangian relaxation. We then test the performance of our heuristics in an extensive numerical study and show that the Lagrangian heuristic demonstrates a strong level of performance in a range of traffic conditions. In particular, it clearly outperforms both a greedy heuristic, which is a standard proposal in complex routing problems, and a recent proposal from the heavy traffic literature.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 23 , Issue 2 , April 2009 , pp. 175 - 203
Copyright
Copyright © Cambridge University Press 2009

References

1.Ansell, P.S., Glazebrook, K.D. & Kirkbride, C. (2003). Generalised “join the shortest queue” policies for the dynamic routing of jobs to multi-class queues. Journal of the Operational Research Society 54: 379–389.Google Scholar
2.Ansell, P.S., Glazebrook, K.D., Niño-Mora, J. & O'Keeffe, M. (2003). Whittle's index policy for a multi-class queueing system with convex holding costs. Mathematical Methods in Operations Research 57: 21–39.Google Scholar
3.Armony, M. (2005). Dynamic routing in large-scale service systems with heterogeneous servers. Queueing Systems 51: 287–329.Google Scholar
4.Armony, M. & Maglaras, C. (2004). On customer contact centers with a call-back option: Customer decisions, routing rules, and system design. Operations Research 52: 271–292.Google Scholar
5.Armony, M. & Maglaras, C. (2004). Contact centers with a call-back option and real time delay information. Operations Research 52: 527–545.Google Scholar
6.Bassamboo, A., Harrison, J.M. & Zeevi, A. (2005). Dynamic routing and admission control in high-volume service systems: Asymptotic analysis via multi-scale fluid limits. Queueing Systems 51: 249–285.CrossRefGoogle Scholar
7.Becker, K.J., Gaver, D.P., Glazebrook, K.D., Jacobs, P.A. & Lawphongpanich, S. (2000). Allocation of tasks to specialised processors: a planning approach. European Journal of Operational Research 126: 80–88.Google Scholar
8.Bhulai, S. (2004). Dynamic routing policies for multi-skill call centers. Technical report 2004-11, Vrije University, Amsterdam.Google Scholar
9.Bhulai, S. & Koole, G. (2003). On the structure of value functions for threshold policies in queueing models. Journal of Applied Probability 40: 613–622.Google Scholar
10.Charnsirisakskul, K., Griffin, P.M. & Keskinocak, P. (2004). Order selection and scheduling with leadtime flexibility. IIE Transactions 36: 697–707.Google Scholar
11.Foley, R.D. & McDonald, D.R. (2001). Join the shortest queue: stability and exact asymptotics. Annals of Applied Probability 11: 569–607.Google Scholar
12.Foschini, G.J. & Salz, J. (1978). A basic dynamic routing problem and diffusion. IEEE Transactions on Communications 26: 320–327.Google Scholar
13.Gans, N. & Zhou, Y.P. (2003). A call routing problem with service level constraints. Operations Research 51: 255–271.Google Scholar
14.Glazebrook, K.D., Lumley, R.R. & Ansell, P.S. (2003). Index heuristics for multiclass M/G/1 systems with nonpreemptive service and convex holding costs. Queueing Systems 45: 81–111.Google Scholar
15.Glazebrook, K.D., Kirkbride, C. & Ouenniche, J. (2009). Index policies for the admission control and routing of impatient customers to heterogeneous service stations. Operations Research. In press.Google Scholar
16.Glazebrook, K.D., Mitchell, H.M. & Ansell, P.S. (2005). Index policies for the maintenance of a collection of machines by a set of repairmen. European Journal of Operational Research 165: 267–284.Google Scholar
17.Glazebrook, K.D., Niño-Mora, J. & Ansell, P.S. (2002). Index policies for a class of discounted restless bandits. Advances in Applied Probability 34: 754–774.Google Scholar
18.Gross, D. & Harris, C.M. (1998). Fundamentals of queueing theory. New York: Wiley.Google Scholar
19.Harrison, J.M. & Zeevi, A. (2004). Dynamic scheduling of a multi-class queue in the Halfin–Whitt heavy traffic regime. Operations Research 52: 243–257.Google Scholar
20.Hopp, W.J. & Sturgis, M.L.R. (2000). Quoting manufacturing due dates subject to a service level constraint. IIE Transactions 32: 771–784.CrossRefGoogle Scholar
21.Hordijk, A. & Koole, G. (1990). On the optimality of the generalized shortest queue policy. Probability in the Engineering and Information Sciences 4: 477–487.Google Scholar
22.Houck, D.J. (1987). Comparison of policies for routing customers to parallel queueing systems. Operations Research 35: 306–310.Google Scholar
23.Johri, P.K. (1989). Optimality of the shortest line discipline with state-dependent service rates. European Journal of Operational Research 41: 157–161.Google Scholar
24.Jones, D. (2004). Some hospital ERs begin guaranteeing quick service. USA Today, December 3.Google Scholar
25.Kelly, F.P. & Laws, C.N. (1993). Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems 13: 47–86.Google Scholar
26.Koole, G., Sparaggis, P.D. & Towsley, D. (1999). Minimizing response times and queue lengths in systems of parallel queues. Journal of Applied Probability 36: 1185–1193.Google Scholar
27.Krishnan, K.R. (1987). Joining the right queue: A Markov decision rule. In Proceedings of the 26th IEEE Conference on Decision Control, pp. 1863–1868.Google Scholar
28.Krishnan, K.R. (1990). Joining the right queue: A state-dependent decision rule. IEEE Transactions on Automatic Control 35: 104–108.Google Scholar
29.Krishnan, K.R. & Ott, T.J. (1986). State-dependent routing for telephone traffic: Theory and results. In Proceedings of the 25th IEEE Conference on Decision Control, pp. 2124–2128.Google Scholar
30.Laws, C.N. (1992). Resource pooling in queueing networks with dynamic routing. Advances in Applied Probability 24: 699–726.Google Scholar
31.MacKenzie, E.J., Hoyt, D.B., Sacra, J.C., Jurkovich, G.J., Carlini, A.R., Taitelbaum, S.D. & Teter, H. Jr. (2003). National inventory of hospital trauma centers. Journal of the American Medical Association 289: 1515–1522.CrossRefGoogle ScholarPubMed
32.Mandelbaum, A. & Stolyar, A.L. (2004). Scheduling flexible servers with convex delay costs: Heavy traffic optimality of generalized cμ-rule. Operations Research 52: 836–855.Google Scholar
33.Menich, B. & Serfozo, R. (1991). Optimality of routing and servicing in dependent parallel processing systems. Queueing Systems v9: 403–418.Google Scholar
34.Niño-Mora, J. (2002). Dynamic allocation indices for restless projects and queueing admission control. Mathematical Programming 93: 361–413.Google Scholar
35.Osterwalder, J.J. (2002). Can the “golden hour of shock” be safely extended in blunt polytrauma patients. Prehospital and Disaster Medicine 17: 75–80.Google Scholar
36.Opp, M., Glazebrook, K. & Kulkarni, V. (2005). Outsourcing warranty repairs: Dynamic allocation. Naval Research Logistics 52: 381–398.Google Scholar
37.Ross, K.W. & Yao, D.D. (1991). Optimal load balancing and scheduling in a distributed computer system. Journal of the Association for Computing Machinery 38: 676–690.Google Scholar
38.Sassen, S.A.E., Tijms, H.C. & Nobel, R.D. (1997). A heuristic rule for routing customers to parallel servers. Statistica Neerlandica 51: 107–121.Google Scholar
39.Sparaggis, P.D., Towsley, D. & Cassandras, C.G. (1993). Extremal properties of the SNQ and the LNQ policies in finite capacity systems with state-dependent service rates. Journal of Applied Probability 30: 223–236.Google Scholar
40.Stolyar, A.L. (2005). Optimal routing in output-queued flexible server systems. Probability in the Engineering and Informational Sciences 19: 141–189.Google Scholar
41.Teh, Y. & Ward, A. (2002). Critical thresholds for dynamic routing in queueing networks. Queueing Systems 42: 297–316.Google Scholar
42.Tezcan, T. (2005). Optimal control of distributed parallel server systems under the Halfin and Whitt regime. Mathematics of Operations Research 33: 51–90.Google Scholar
43.Tijms, H.C. (1994). Stochastic models: An algorithmic approach. New York: Wiley.Google Scholar
44.Towsley, D., Sparaggis, P.D. & Cassandras, C.G. (1993). Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Transactions on Automatic Control 37: 1446–1451.Google Scholar
45.Van Mieghem, J.A. (1995). Dynamic scheduling with convex delay costs: The generalized cμ rule. The Annals of Applied Probability 5: 809–833.Google Scholar
46.Wallace, R.B. & Whitt, W. (2005). A staffing algorithm for call centers with skill-based routing. Manufacturing and Service Operations Management 7: 276–294.Google Scholar
47.Weber, R. (1978). On the optimal assignment of customers to parallel servers. Journal of Applied Probability 15: 406–413.Google Scholar
48.Wein, L.M. (1991). Brownian networks with discretionary routing. Operations Research 39: 322–340.Google Scholar
49.Whitt, W. (1986). Deciding which queue to join: Some counterexamples. Operations Research 34: 55–62.Google Scholar
50.Whittle, P. (1996). Optimal control: Basics and beyond. New York: Wiley.Google Scholar
51.Whittle, P. (1988). Restless bandits: Activity allocation in a changing world. Journal of Applied Probability A25: 287–298.Google Scholar
52.Winston, W. (1977). Optimality of the shortest-processing-time discipline. Journal of Applied Probability 14: 181–189.Google Scholar