Asymptotically Optimal Clearing Control of Backlogs in Multiclass Processing Systems

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.

Funding: O. Perry and L. Yu were partially supported by NSF [Grants CMMI 1763100 and CMMI 2006350]. L. Yu is currently supported by NSFC [Grants 72201153, 72242106, and 72394361].

Supplemental Material: The online appendix and code are available at https://doi.org/10.1287/opre.2022.0570.