Asymptotically Optimal Clearing Control of Backlogs in Multiclass Processing Systems

Lun Yu (), Seyed Iravani () and Ohad Perry ()
Additional contact information
Lun Yu: School of Data Science, The Chinese University of Hong Kong (Shenzhen), Shenzhen 518172, China
Seyed Iravani: Department of Industrial Engineering and Management Science, Northwestern University, Evanston, Illinois 60208
Ohad Perry: Department of Operations Research and Engineering Management, Southern Methodist University, Dallas, Texas 75205

Operations Research, 2025, vol. 73, issue 4, 2061-2078

Abstract: 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 μ / θ 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 μ / θ 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.

Keywords: Stochastic; Models; heavy-traffic approximation; many-server queue; scheduling control (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0570 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:2061-2078

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().