Workload-Dependent Dynamic Priority for the Multiclass Queue with Reneging

• 成果类型: Article
• 署名作者: Atar, Rami; Lev-Ari, Anat
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0869
• 发表日期: 2018
• 页码: 494-515
• 关键词: Asymptotic Optimality; ABANDONMENT; Servers; SYSTEM

摘要

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).