Workload-Dependent Dynamic Priority for the Multiclass Queue with Reneging

Scheduling control for a single-server queue with I customer classes and reneging is considered, with linear holding or reneging cost. An asymptotically optimal (AO) policy in heavy traffic is identified where classes are prioritized according to a workload-dependent dynamic index rule. Denote by c(i), mu(i), and theta(i), i is an element of J := {1, . . . , I} the queue length cost, service rate, and reneging rate, for class-i customers. Then, a relabeling of the classes and a partition 0 = w(0)< w(1) < . . . < w(k) = infinity, K <= I are identified such that the policy acts to always assign least priority to the class i when the rescaled workload is in the interval [w(i-1), w(i)). The relabeling is such that when workload is withing the lowest [resp., highest] interval [w(i-1), w(i)), the least priority class is the one with smallest c mu [resp., greatest theta] value. This result stands in sharp contrast to known fluid-scale results where it is AO to prioritize by the fixed c mu/theta index. One of the technical challenges is the discontinuity of the limiting queue length process under optimality. Discontinuities occur whenever the workload reaches one of the levels w(i).