Optimal control of admission in service in a queue with impatience and setup costs

Abstract : We consider a single server queue in continuous time, in which customers must be served before some limit sojourn time of exponential 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 fact of holding them in the queue also induces a constant cost per customer and per unit time. 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. Since the standard uniformization approach is not applicable here, we introduce a family of approximated uniformizable models, for which we establish the structural properties of the stochastic dynamic programming operator, and we deduce that the optimal policy is of threshold type. The threshold is computed explicitly. We then pass to the limit to show that this threshold policy is also optimal in the original model. A particular care is given to the completeness of the proof. We also illustrate the difficulties involved in the proof with numerical examples.
Complete list of metadatas

Cited literature [54 references]  Display  Hide  Download

https://hal.inria.fr/hal-01856331
Contributor : Alain Jean-Marie <>
Submitted on : Friday, August 10, 2018 - 4:19:13 PM
Last modification on : Friday, July 5, 2019 - 3:26:03 PM
Long-term archiving on : Sunday, November 11, 2018 - 1:33:33 PM

File

RR-9199.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01856331, version 1

Citation

Alain Jean-Marie, Emmanuel Hyon. Optimal control of admission in service in a queue with impatience and setup costs. [Research Report] RR-9199, Inria - Sophia Antipolis; Univ. Montpellier; Sorbonne Université, CNRS, Laboratoire d'Informatique de Paris 6, LIP6, Paris, France; Université Paris Nanterre. 2018, pp.1-47. ⟨hal-01856331⟩

Share

Metrics

Record views

699

Files downloads

98