Whittle index approach to multiserver scheduling with impatient customers and DHR service times

Abstract

We consider the optimal scheduling problem in a multiserver queue with impatient customers belonging to multiple classes. We assume that each customer has a random abandonment time, after which the customer leaves the system if its service has not been completed before that. In addition, we assume that the scheduler is not able to anticipate the expiration of the abandonment times but only knows their distributions and how long each customer has been in the system. Many papers consider this scheduling problem under Poisson arrivals and linear holding costs assuming further that both the service times and the abandonment times have exponential distributions. Even with these additional assumptions, the exact solution is known only in very few special cases. To tackle this tricky problem, we apply the Whittle index approach. Unlike the earlier papers, which were restricted to exponential service times, we allow the service time distributions for which the hazard rate is decreasing. The Whittle index approach is applied to the discrete-time multiserver queueing problem with discounted costs. As our main theoretical result, we prove that the related relaxed optimization problem is indexable and derive the corresponding Whittle index explicitly. Based on this discrete-time result, we develop a reasonable heuristic for the original continuous-time multiserver scheduling problem. The performance of the resulting policy is evaluated in the M/G/M setup by numerical simulations, which demonstrate that it, indeed, gives better performance than the other policies included in the comparison.