DYNAMIC ROUTING OF CUSTOMERS WITH GENERAL DELAY COSTS IN A MULTISERVER QUEUING SYSTEM
- 16 February 2009
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 23 (2) , 175-203
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.Keywords
This publication has 55 references indexed in Scilit:
- Outsourcing warranty repairs: Dynamic allocationNaval Research Logistics (NRL), 2005
- On the structure of value functions for threshold policies in queueing modelsJournal of Applied Probability, 2003
- National Inventory of Hospital Trauma CentersJAMA, 2003
- Index policies for a class of discounted restless banditsAdvances in Applied Probability, 2002
- Minimizing response times and queue lengths in systems of parallel queuesJournal of Applied Probability, 1999
- Extremal properties of the shortest/longest non-full queue policies in finite-capacity systems with state-dependent service ratesJournal of Applied Probability, 1993
- Resource pooling in queueing networks with dynamic routingAdvances in Applied Probability, 1992
- Restless bandits: activity allocation in a changing worldJournal of Applied Probability, 1988
- On the optimal assignment of customers to parallel serversJournal of Applied Probability, 1978
- Optimality of the shortest line disciplineJournal of Applied Probability, 1977