Asymptotically Optimal Clearing Control of Backlogs in Multiclass Processing Systems

• 成果类型: Article
• 署名作者: Yu, Lun; Iravani, Seyed; Perry, Ohad
• 署名单位: The Chinese University of Hong Kong, Shenzhen; Northwestern University; Southern Methodist University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0570
• 发表日期: 2025
• 页码: 2061-2078
• 关键词: many-server queues; convex delay costs; scheduling flexible servers; diffusion-approximation; queuing-networks; fluid limits; centers; regime

摘要

We consider a dynamic scheduling problem for a processing system facing the problem of optimally clearing a large backlog of unsatisfied demand from several classes of customers (or jobs). We formulate the problem as a multiclass queueing model with a large initial queue and arrival rates that approximately equal the system's processing capacity. The goal is to find a scheduling policy that minimizes a holding -and -abandonment cost during the transient period in which the system is considered congested. Because computing an exact solution to the optimal -control problem is infeasible, we develop a unified asymptotic approximation that covers, in particular, the conventional and the many -server heavy -traffic regimes. In addition to the generality and flexibility of our unified asymptotic framework, we also prove a strong form of asymptotic optimality, under which the costs converge in expectation and in probability. In particular, for the special two -class case, we prove that a static priority policy, which follows a discounted c mu/ theta rule, is asymptotically optimal. When there are more than two classes of customers, we show that any admissible control that follows the best -effort rule, which gives the lowest priority to one of the classes according to the discounted c mu /theta ordering, becomes asymptotically optimal after some relatively short time period. Finally, using heuristic arguments and insights from our analyses, we propose scheduling policies that build on the best -effort rule. An extensive numerical study shows that those proposed policies are effective and provides guidance as to when to use either policy in practice.