Asymptotically Optimal Admission Control of a Queue with Impatient Customers

Sunil Kumar
Graduate School of Business
Stanford University


Wednesday, March 1, 2006
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

Customers arrive at a single server queue according to a renewal process. Their service times are independent and identically distributed. Customers waiting for service in the queue renege, that is, leave the queue before being served, according to an independent, exponentially distributed impatience clock. Each reneging customer costs the server $r. The server exercises control by turning away customers on arrival at a cost $p, with p < r. The goal is to design a control policy that minimizes the expected infinite horizon discounted cost of reneging and turning away customers.

We study this system in the heavy traffic asymptotic regime where the nominal load on the server is nearly one. We begin by solving an associated diffusion control problem. Because this problem does not admit a pathwise solution (and the solution depends on second moment data), we explicitly solve the Hamilton-Jacobi-Bellman equation using an iterative procedure. We use this solution to construct a candidate control policy. We establish asymptotic optimality in heavy traffic of this policy by showing that the cost under this policy converges to the optimal cost in the diffusion control problem, and then showing that this cost is a lower bound on the cost of any admissible control policy.

Joint work with Amy Ward, ISYE, Georgia Tech.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html