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.