Politique de service optimal dans une file d'attente en temps discret avec impatiences

Emmanuel Hyon 1 Alain Jean-Marie 2, 3
1 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
3 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : On s'intéresse ici à l'ordonnancement (scheduling) optimal de clients dans une unité de traitement, dans le cas où les clients qui attendent sont impatients (l'impatience modélise aussi des clients soumis à des échéances). Le démarrage d'un service (set-up) aussi bien que le départ de clients avant leur service (que nous nommerons pertes) impliquent des coûts, et il s'agit de décider quand servir les clients pour minimiser ces coûts. De tels modèles, aussi bien déterministes que stochastiques, ont été largement étudiés dans la littérature. Néanmoins la plupart de ces travaux ne considère pas que les clients sont impatients. Ainsi, le problème incluant coûts de type holding et set-up, avec traitement par lots mais sans pertes, est résolu dans la littérature grâce à des techniques de contrôle optimal [2]. La politique optimale est une politique à seuil. Pour ce même modèle de coûts, [3] utilise des Processus de Décisions Markoviens (MDP) et s'attache à montrer des propriétés structurelles de la fonction de valeur et de l'opérateur de programmation dynamique qui permettent de déduire certaines propriétés de la politique optimale. Dans cet article, nous reprenons le problème et la méthode pour un modèle à une seule machine et à temps discret et nous utilisons un MDP à horizon infini et à coûts actualisés. Nous établissons les propriétés structurelles de l'opérateur de programmation dynamique stochastique, et nous déduisons que la politique optimale est à seuil. Par ailleurs, grâce à une analyse trajectorielle comparative de deux politiques à seuil, nous calculons la valeur de ce seuil en fonction des paramètres du problème.
Type de document :
Communication dans un congrès
ROADEF'2009: 10ième Conférence de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2009, Nancy, France. pp.214-215, 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00368260
Contributeur : Alain Jean-Marie <>
Soumis le : dimanche 15 mars 2009 - 18:20:14
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

  • HAL Id : inria-00368260, version 1

Citation

Emmanuel Hyon, Alain Jean-Marie. Politique de service optimal dans une file d'attente en temps discret avec impatiences. ROADEF'2009: 10ième Conférence de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2009, Nancy, France. pp.214-215, 2009. 〈inria-00368260〉

Partager

Métriques

Consultations de la notice

253