Asymptotically optimal index policies for an abandonment queue with convex holding cost

摘要

We investigate a resource allocation problem in a multi-class server with convex holding costs and user impatience under the average cost criterion. In general, the optimal policy has a complex dependency on all the input parameters and state information. Our main contribution is to derive index policies that can serve as heuristics and are shown to give good performance. Our index policy attributes to each class an index, which depends on the number of customers currently present in that class. The index values are obtained by solving a relaxed version of the optimal stochastic control problem and combining results from restless multi-armed bandits and queueing theory. They can be expressed as a function of the steady-state distribution probabilities of a one-dimensional birth-and-death process. For linear holding cost, the index can be calculated in closed-form and turns out to be independent of the arrival rates and the number of customers present. In the case of no abandonments and linear holding cost, our index coincides with the cμ-rule, which is known to be optimal in this simple setting. For general convex holding cost, we derive properties of the index value in limiting regimes: we consider the behavior of the index (ⅰ) as the number of customers in a class grows large, which allows us to derive the asymptotic structure of the index policies, (ⅱ) as the abandonment rate vanishes, which allows us to retrieve an index policy proposed for the multi-class M/M/1 queue with convex holding cost and no abandonments, and (ⅲ) as the arrival rate goes to either 0 or ∞, representing light-traffic and heavy-traffic regimes, respectively. We show that Whittle's index policy is asymptotically optimal in both light-traffic and heavy-traffic regimes. To obtain further insights into the index policy, we consider the fluid version of the relaxed problem and derive a closed-form expression for the fluid index. The latter is shown to coincide with the index values for the stochastic model in asymptotic regimes. For arbitrary convex holding cost the fluid index can be seen as the Gcμ/θ-rule; that is, including abandonments into the generalized cμ-rule (Gcμ-rule). Numerical experiments for a wide range of parameters have shown that the Whittle index policy and the fluid index policy perform very well for a broad range of parameters.