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, μ_i, and θ_i, i ∈ ℐ := {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₀ < w₁ < ⋯ < w_K = ∞, 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μ [resp., greatest θ] value. This result stands in sharp contrast to known fluid-scale results where it is AO to prioritize by the fixed cμ/θ 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.