On the optimal allocation of service to impatient tasks
- 1 March 2004
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 41 (1), 51-72
- https://doi.org/10.1239/jap/1077134667
Abstract
Service is often provided in contexts where tasks or customers are impatient or perishable in that they have natural lifetimes of availability for useful service. Moreover, these lifetimes are usually unknown to the service provider. The question of how service might best be allocated to the currently waiting tasks or customers in such a context has been neglected and we propose three simple models. For each model, an index heuristic is developed and is assessed numerically. In all cases studied the heuristic comes close to optimality.Keywords
This publication has 22 references indexed in Scilit:
- Optimal threshold policies in a workload model with a variable number of service phases per jobMathematical Methods of Operations Research, 2003
- Whittle's index policy for a multi-class queueing system with convex holding costsMathematical Methods of Operations Research, 2003
- Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approachMathematical Programming, 2002
- Computation of a near-optimal service policy for a single-server queue with homogeneous jobsEuropean Journal of Operational Research, 2001
- Real-time queues in heavy traffic with earliest-deadline-first queue disciplineThe Annals of Applied Probability, 2001
- Using real-time queueing theory to control lateness in real-time systemsACM SIGMETRICS Performance Evaluation Review, 1997
- A duality approach to admission and scheduling controls of queuesQueueing Systems, 1994
- Addendum to ‘On an index policy for restless bandits'Advances in Applied Probability, 1991
- The Multi-Armed Bandit Problem: Decomposition and ComputationMathematics of Operations Research, 1987
- On stochastic scheduling problems with due datesInternational Journal of Systems Science, 1983