Scheduling Services in a Queuing System with Impatience and Setup Costs

Emmanuel Hyon 1, 2 Alain Jean-Marie 3, 4
2 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
3 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
4 LIRMM/HE - Hors Équipe
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We consider a single-server queue in discrete time, in which customers must be served before some limit sojourn time of geometrical distribution. A customer who is not served before this limit leaves the system: it is impatient. The service of customers, the loss due to impatience and the holding of customers in the queue induce costs. The purpose is to decide when to serve the customers so as to minimize them. We use a Markov decision process with infinite horizon and discounted cost. We establish the structural properties of the stochastic dynamic programming operator and we deduce that the optimal policy is of threshold type. In addition, we are able to compute explicitly the optimal value of this threshold in terms of the parameters of problem.
Type de document :
Article dans une revue
The Computer Journal, Oxford University Press (UK), 2012, Special Focus on Probability Models in Performance Analysis, 55 (5), pp.553-563. 〈10.1093/comjnl/bxq096〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00862926
Contributeur : Alain Jean-Marie <>
Soumis le : mardi 17 septembre 2013 - 18:52:13
Dernière modification le : mercredi 4 juillet 2018 - 23:14:10

Lien texte intégral

Identifiants

Collections

Citation

Emmanuel Hyon, Alain Jean-Marie. Scheduling Services in a Queuing System with Impatience and Setup Costs. The Computer Journal, Oxford University Press (UK), 2012, Special Focus on Probability Models in Performance Analysis, 55 (5), pp.553-563. 〈10.1093/comjnl/bxq096〉. 〈hal-00862926〉

Partager

Métriques

Consultations de la notice

279