8481 articles  [version française]

inria-00369382, version 2

Scheduling in a queuing system with impatience and setup costs

Alain Jean-Marie (Author to contact preferably) 1, 2, Emmanuel Hyon a, 3

N° RR-6881 (2009)

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 fact of serving customers and the fact of losing them due to impatience induce costs. The purpose is to decide when to serve the customers so as to minimize costs. 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, thanks to a pathwise comparison analysis of two threshold policies, we are able to compute explicitly the optimal value of this threshold according to the parameters of problem.

  • a –  Université Paris Ouest Nanterre La Défense
  • 1:  Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
  • CNRS : UMR5506 – Université Montpellier II - Sciences et techniques
  • 2:  MAESTRO (INRIA Sophia Antipolis)
  • INRIA – Université Montpellier II - Sciences et techniques
  • 3:  Laboratoire d'Informatique de Paris 6 (LIP6)
  • CNRS : UMR7606 – Université Pierre et Marie Curie [UPMC] - Paris VI
  • Domain : Computer Science/Operations Research
    Computer Science/Performance and Reliability
    Mathematics/Optimization and Control
  • Internal note : RR-6881
  • Available versions :  v1 (2009-03-19) v2 (2010-02-09)
 
  • inria-00369382, version 2
  • http://hal.inria.fr/inria-00369382
  • oai:hal.inria.fr:inria-00369382
  • From: Alain Jean-Marie <>
  • Submitted on: Monday, 8 February 2010 17:43:14
  • Updated on: Tuesday, 9 February 2010 05:36:22