Whittle index approach to the multi-class queueing systems with convex holding costs and IHR service times

We consider the dynamic scheduling problem in a single-server
multi-class queueing system, where the accumulated holding costs of a customer
is a convexly increasing function of the time that the customer spends
in the system. This problem was already addressed by van Mieghem in his seminal
paper [18]. He launched the so-called generalized cμ rule and proved its
asymptotic optimality in the heavy traffic limit. The optimal scheduling problem
with convex holding costs have also been studied in many other papers.
However, the holding costs in these papers are typically count-convex, i.e., the
aggregate holding cost rate related to a class of customers increases convexly
as a function of the current number of customers in this class, which is clearly
different from the time-convex holding costs introduced in [18] and studied also
in the present paper. We utilize the Whittle index approach to develop a novel
heuristic policy for the dynamic scheduling problem with time-convex holding
costs. Instead of the original open version of the continuous-time scheduling
problem, we apply the Whittle index approach to the corresponding discretetime
closed version of the problem. As the main theoretical contribution, we
prove that, for IHR service times, the discounted discrete-time problem is indexable
and also give an explicit expression for the Whittle index itself. A special
challenge in our model is the two-dimensional state space with an infinite
number of possible states. By utilizing the discrete-time results, we develop a
novel index policy for the original continuous-time problem and demonstrate,
by numerical simulations, that this Whittle index policy outperforms the generalized
cμ rule. Thus, while the generalized cμ rule is asymptotically optimal
in the heavy traffic limit, it can still be improved in normal traffic conditions.