🔢 mathematics

Design and Scheduling of an AI-based Queueing System

This paper proposes a near-optimal, index-based scheduling policy for large queueing systems with AI-based job classification that explicitly accounts for the impact of prediction errors on congestion, offering a framework to guide model selection and system design in human-AI collaborative environments like content moderation.

Original authors: Jiung Lee, Hongseok Namkoong, Yibo Zeng

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiung Lee, Hongseok Namkoong, Yibo Zeng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you run a busy customer service center. You have a team of human reviewers (servers) who need to process a massive, never-ending stream of incoming requests (jobs). Some requests are simple and quick to fix; others are complex, dangerous, or require deep thought and take a long time.

To help your team, you hire an AI assistant. This AI looks at every request and tries to guess how difficult it is. It sorts the requests into different "buckets" (queues) based on its guess. For example, it might put "easy" requests in one line and "hard" requests in another.

The Problem: The AI Makes Mistakes
Here's the catch: The AI isn't perfect. Sometimes it thinks a "hard" request is "easy," and sometimes it thinks an "easy" request is "hard."

If you just blindly follow the AI's sorting, chaos ensues.

If the AI thinks a slow, complex job is fast, you might put it in the "fast" line. Your team rushes to finish it, but it takes forever, clogging up the line and making everyone else wait longer.
If the AI thinks a fast job is slow, you might put it in the "slow" line, where it sits idle while the "fast" line is empty.

This is the core problem the paper tackles: How do you schedule work when your AI sorter is noisy and makes mistakes?

The Old Way (The Naive Approach)
Most people would just trust the AI completely. They would say, "The AI says this is a 'Type A' job, so we treat it like a 'Type A' job." The paper calls this the Naive Gcµ-rule. It's like a traffic cop who only looks at the color of a car's paint to decide who goes first, ignoring the fact that the car might actually be a slow-moving truck painted red. This leads to traffic jams (congestion) and angry customers (high costs).

The New Way: The "Pcµ-rule"
The authors propose a smarter strategy called the Pcµ-rule.

Instead of blindly trusting the AI's label, this rule asks: "Given that the AI made this specific guess, what is the real probability that this job is actually hard or easy?"

To do this, the rule uses a "confusion matrix." Think of this as a report card for the AI that says:

"When the AI says 'Easy,' it's actually 'Easy' 90% of the time, but 'Hard' 10% of the time."
"When the AI says 'Hard,' it's actually 'Hard' 95% of the time."

The Pcµ-rule combines the AI's guess with this report card to calculate a "weighted cost." It doesn't just ask, "How long does this job take?" It asks, "How long does this job likely take, considering the AI's track record?"

It then prioritizes the jobs that are most likely to cause the biggest traffic jams if delayed. It's like a traffic cop who knows that a red car usually means a fast sports car, but sometimes means a slow truck. If the traffic is heavy, the cop might give the red car a second look before letting it cut in line, just in case it's a truck.

Why This Matters (The "Heavy Traffic" Insight)
The paper proves mathematically that in a system that is constantly overwhelmed (heavy traffic), this smart rule is the best possible way to run the show. It minimizes the total waiting time and frustration for everyone.

The authors also show that simply making the AI "more accurate" isn't always the answer. Sometimes, a slightly less accurate AI that makes mistakes in a specific, predictable way can actually lead to better overall system performance than a highly accurate AI that makes unpredictable errors.

Real-World Example: Content Moderation
The paper tests this idea using content moderation (like Facebook or Twitter removing hate speech).

The Job: Reviewing user comments.
The AI: A model that flags comments as "Toxic" or "Safe."
The Reality: Toxic comments about protected groups take longer to review and cause more harm if left up too long.
The Result: When they tested their new rule against standard methods and even advanced AI learning methods (Deep Reinforcement Learning), their simple "smart index" rule performed significantly better. It reduced the total "pain" (cost) of the system by up to 70% compared to the naive approach.

Key Takeaways for the Everyday Person

Don't just trust the AI's label: If your AI sorter makes mistakes, you need a rule that accounts for those mistakes, not one that ignores them.
Accuracy isn't everything: A model that is "perfect" at predicting might not be the best for running a busy system. You need a model that plays well with your scheduling rules.
Simple is often better: The authors found that their simple, math-based rule worked better than complex, "black box" AI learning methods that required massive amounts of tuning and often failed when conditions changed slightly.

In short, the paper teaches us that when managing a chaotic, busy system with a fallible AI helper, the secret to success isn't just having a smarter AI—it's having a smarter manager who knows how to interpret the AI's mistakes.

Technical Summary: Design and Scheduling of an AI-based Queueing System

1. Problem Statement

The paper addresses the challenge of scheduling jobs in service systems where job classes (which determine service times and delay costs) are not known a priori but must be estimated using machine learning prediction models. In applications such as content moderation, an AI model classifies incoming items (e.g., "toxic" vs. "safe" or specific demographic targets), but these predictions are imperfect.

The core problem is that mispredictions introduce negative externalities. Prioritizing a job based on a predicted class may inadvertently delay jobs from other true classes that are mixed into the same predicted queue. Standard scheduling policies, such as the naive adaptation of the $Gc\mu$ -rule (which prioritizes based on predicted class parameters), fail to account for these misclassification errors, leading to suboptimal congestion costs. The authors seek to design a scheduling policy that is asymptotically optimal in heavy traffic while explicitly incorporating the confusion matrix of the prediction model.

2. Methodology

2.1 Modeling Framework

The authors model the system as a sequence of single-server, multi-class queueing systems indexed by $n$ operating in a heavy-traffic regime.

Arrival Process: Jobs arrive via a single common exogenous stream with i.i.d. interarrival times.
Classification: Before entering the queue, each job is assigned a predicted class $\tilde{l}$ by a fixed classifier $f_\theta$ . The relationship between the true class $k$ and predicted class $\tilde{l}$ is governed by a confusion matrix $Q$ .
Service and Cost: Service times and delay costs depend on the true class $k$ , which is unobservable to the scheduler. The scheduler only observes the predicted class and the age of jobs.
Scaling: The system is analyzed using diffusion scaling ( $n^{-1/2}$ ) as $n \to \infty$ , where the traffic intensity $\rho_n \to 1$ .

2.2 Theoretical Analysis

The analysis proceeds in two main stages:

Lower Bound Derivation: The authors derive an asymptotic lower bound for the cumulative queueing cost. They characterize the diffusion limits of the predicted-class arrival and service processes, showing how the confusion matrix $Q$ aggregates the fluctuations of unobservable true classes. The optimal cost is formulated as a convex optimization problem (Opt) that minimizes the weighted sum of true-class costs subject to the total workload constraint.
Policy Design ( $Pc\mu$ -rule): Motivated by the KKT conditions of the optimal workload allocation, the authors propose the $Pc\mu$ -rule. Unlike the naive $Gc\mu$ -rule, the $Pc\mu$ -rule uses a confusion-weighted cost function ( $\tilde{C}_l$ ) for each predicted class. This cost is a weighted average of the true-class costs, where weights are the posterior probabilities of the true class given the predicted class.

2.3 Optimality Proof

Proving the heavy-traffic optimality of the $Pc\mu$ -rule presents significant analytical challenges:

Target Identification: Unlike classical settings where the target workload allocation is transparent, misclassification obscures the relationship between predicted queues and true costs. The authors show the optimal policy must align the predicted-class workloads with the solution to the convex optimization problem derived from the lower bound.
Index Convergence: The proof requires showing that the difference between the indices of different predicted classes vanishes in the limit. The authors establish this via an induction argument over diffusion-scaled time intervals of size $O(n^{-1/2})$ .
Technical Conditions: The proof relies on the strong convexity of the delay cost functions (a stronger condition than the strict convexity assumed in prior literature like Van Mieghem [66]) to ensure the argument closes.

3. Key Contributions

3.1 The $Pc\mu$ -Rule

The paper introduces a simple, index-based scheduling policy that is asymptotically optimal in heavy traffic. The rule prioritizes the predicted class with the highest marginal cost of delay, where the cost is adjusted by the classifier's confusion matrix. It effectively corrects for the "noise" introduced by the prediction model.

3.2 Rigorous Heavy-Traffic Theory

The authors provide the first rigorous proof of heavy-traffic optimality for an age-based $Gc\mu$ -rule (and its extension to misclassification).

They fill gaps in classical proofs (Van Mieghem [66], Mandelbaum and Stolyar [40]) regarding the convergence of index differences and the equivalence between age-based and sojourn-time-based indices.
They demonstrate that strong convexity of cost functions is a sufficient condition for the vanishing of index gaps, a condition not previously explicitly stated in the classical literature.

3.3 Model Selection and System Design

The theoretical results provide a framework for model selection and system design:

Model Selection: The authors propose using the relative regret ( $J^*(t; Q) / J^*(t; I)$ ) as a metric for selecting prediction models. They demonstrate that models with identical predictive accuracy (e.g., precision/recall) can yield vastly different queueing costs, and their metric correctly identifies the superior model for downstream scheduling.
Triage System Design: The framework is extended to design AI-based triage systems (filtering + human review). The authors show how to jointly optimize filtering thresholds, hiring levels, and scheduling to minimize a total cost function comprising filtering, hiring, misclassification, and queueing costs, using a simple simulation of reflected Brownian motion rather than expensive queueing simulations.

4. Empirical Results

The authors validate their framework using a content moderation task based on real online comments (CivilComments dataset).

Setup: They fine-tuned large language models (DistilBERT) to classify toxicity across different demographic groups, creating 10 job classes.
Comparison: The $Pc\mu$ $P c μ$ -rule was compared against:
- Oracle $Gc\mu$ : The theoretical lower bound (knowing true classes).
- Naive $Gc\mu$ : Treating predictions as ground truth.
- Deep Reinforcement Learning (DRL): A black-box approach using Q-learning.
Findings:
- The $Pc\mu$ -rule significantly outperformed the Naive $Gc\mu$ -rule (reducing cost gap to Oracle by ~30%) and DRL (reducing cost gap by 60–70%).
- DRL Instability: Deep Q-learning exhibited substantial performance variance across hyperparameter configurations, even with identical training seeds, highlighting the engineering difficulty of applying RL in this domain.
- Model Multiplicity: Experiments confirmed that models with similar accuracy levels produced different queueing costs. The proposed theoretical criteria successfully ranked models by their actual queueing performance, outperforming traditional accuracy-based selection.
- Robustness: The $Pc\mu$ -rule maintained performance gains under distribution shifts (non-stationary arrival rates).

5. Significance and Claims

The paper claims that its primary significance lies in bridging the gap between predictive modeling and operational decision-making in service systems.

Beyond Prediction Accuracy: It argues that optimizing for standard predictive metrics (accuracy, F1-score) is insufficient for systems where predictions drive resource allocation. The "downstream" queueing cost is the true objective.
Practicality: The $Pc\mu$ -rule offers a simple, implementable alternative to complex, unstable, and data-hungry reinforcement learning approaches. It requires only the confusion matrix and arrival/service rates, which are estimable from historical data.
Theoretical Completeness: By rigorously proving the optimality of age-based indices in the presence of misclassification, the paper strengthens the theoretical foundation of heavy-traffic queueing theory, addressing specific gaps left by seminal works in the field.
Design Guidance: The framework provides a tractable method (via Brownian motion simulation) for designing end-to-end AI-assisted service systems (e.g., content moderation pipelines) that balance filtering, staffing, and scheduling costs without resorting to computationally prohibitive simulations.

The authors remain modest, noting that the framework assumes i.i.d. arrivals and a fixed classifier, and that extending these results to multi-server settings with complex stability constraints or dynamic learning environments remains an open area for future research.