Skip to main content

Research Repository

Advanced Search

Dynamic routing of customers with general delay costs in a multiserver queuing system

Argon, N.T.; Ding, L.; Glazebrook, K.D.; Ziya, S.

Dynamic routing of customers with general delay costs in a multiserver queuing system Thumbnail


Authors

N.T. Argon

K.D. Glazebrook

S. Ziya



Abstract

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.

Citation

Argon, N., Ding, L., Glazebrook, K., & Ziya, S. (2009). Dynamic routing of customers with general delay costs in a multiserver queuing system. Probability in the Engineering and Informational Sciences, 23(2), 175-203. https://doi.org/10.1017/s0269964809000138

Journal Article Type Article
Publication Date Apr 1, 2009
Deposit Date May 22, 2009
Publicly Available Date Mar 28, 2024
Journal Probability in the Engineering and Informational Sciences
Print ISSN 0269-9648
Electronic ISSN 1469-8951
Publisher Cambridge University Press
Peer Reviewed Peer Reviewed
Volume 23
Issue 2
Pages 175-203
DOI https://doi.org/10.1017/s0269964809000138
Public URL https://durham-repository.worktribe.com/output/1527593

Files




You might also like



Downloadable Citations