Optimal Incentive Compatible Control of a Queue with Some Patient Customers

Consider an exponential single-server queue with two classes of customers that differ in price-and delay-sensitivity. A system manager sets the production rate and a static price for each class, dynamically quotes the leadtime for each class of customer and decides the order in which customers are processed. The arrival rate for each class decreases linearly with price and leadtime. The manager’s objective is to maximize profit, subject to the constraint that each customer must be processed within the promised leadtime. Because the manager cannot distinguish whether a potential customer is of class 1 or class 2, the prices and quoted leadtimes must be incentive compatible. That is, each customer chooses the price and leadtime combination intended for his class. Assuming that some customers will tolerate a long queueing delay in return for a small price discount, we show that this problem has a simple near-optimal solution. Under our proposal policy, capacity utilization is near 100%. Impatient customers pay a premium for immediate delivery and receive priority in scheduling. When the queue is long, patient customers are quoted a leadtime proportional to the current queue length. However, when the queue is short, the quoted leadtime is longer than the actual queueing delay. This ensures that the impatient class 1 customers will not choose the deal intended for class 2 customers. Subject Classifications: pricing, dynamic leadtime quotation and sequencing in production/scheduling, diffusion approximations for priority queues