Index Heuristics for Multiclass M/G/1 Systems with Nonpreemptive Service and Convex Holding Costs

We consider the optimal service control of a multiclass M/G/1 queueing system in which customers are served nonpreemptively and the system cost rate is additive across classes and increasing convex in the numbers present in each class. Following Whittle's approach to a class of restless bandit...

Full description

Saved in:
Bibliographic Details
Published in:Queueing systems 2003-10, Vol.45 (2), p.81-111
Main Authors: Glazebrook, K.D., Lumley, R.R., Ansell, P.S.
Format: Article
Language:English
Subjects:
Costs
Customer services
Dynamic programming
Heuristic
Numerical analysis
Optimization
Queuing
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the optimal service control of a multiclass M/G/1 queueing system in which customers are served nonpreemptively and the system cost rate is additive across classes and increasing convex in the numbers present in each class. Following Whittle's approach to a class of restless bandit problems, we develop a Langrangian relaxation of the service control problem which serves to motivate the development of a class of index heuristics. The index for a particular customer class is characterised as a fair charge for service of that class. The paper develops these indices and reports an extensive numerical investigation which exhibits strong performance of the index heuristics for both discounted and average costs. [PUBLICATION ABSTRACT]
ISSN:0257-0130
1572-9443
DOI:10.1023/A:1026060405346