⚡ electrical engineering

Dynamic Scheduling of a Parallel-Server Queueing System: A Computational Method for High-Dimensional Problems

This paper presents a scalable, simulation-based computational method leveraging deep neural networks to solve high-dimensional skill-based routing problems in call centers by approximating them as diffusion control problems in the Halfin-Whitt heavy-traffic regime, demonstrating superior or comparable performance to existing benchmarks on real-world data up to 100 customer classes.

Original authors: Baris Ata, Ebru Kasikaralar

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Baris Ata, Ebru Kasikaralar

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 a massive call center as a busy airport terminal. You have thousands of travelers (customers) arriving with different destinations (service needs), and you have hundreds of pilots and ground crews (agents) with different skill sets. Some agents can only fly to London, others only to Tokyo, and some can handle both.

The big problem is: Who gets on which plane, and when?

If you send a traveler to a pilot who can't fly their route, or if you leave a pilot sitting idle while a traveler waits, you lose money and frustrate customers. In a small airport, a manager can look at the board and make these decisions easily. But in a giant hub with 100 different types of travelers and 70 different pilot teams, the number of possible combinations is so huge that even the smartest supercomputers get stuck trying to figure out the perfect plan. This is what the paper calls the "curse of dimensionality."

Here is how the authors solved this puzzle, explained simply:

1. The "Heavy Traffic" Shortcut

The authors realized that when a call center is super busy (like a rush hour at the airport), the chaos starts to look like a smooth, flowing river rather than a jagged, bumpy road. They used a mathematical trick called the Halfin-Whitt regime to zoom out and view the system as a smooth flow. This allowed them to turn a messy, complex scheduling problem into a cleaner, continuous one that is easier to study.

2. The "Deep Learning" Coach

Even with the smooth river view, the math required to find the perfect schedule is still incredibly hard to solve with traditional methods. It's like trying to calculate the exact wind speed for every single leaf on a tree to predict the weather.

So, the authors brought in a Deep Neural Network (a type of AI). Think of this AI as a super-smart coach. Instead of trying to solve the math equations directly, the coach:

Watches the game: It simulates millions of scenarios of the call center running.
Learns the pattern: It uses a special mathematical "loss function" (a scorecard) to learn the relationship between the current state of the line and the best possible move.
Becomes the expert: After training, this AI knows the "value" of every situation. It knows, "If there are 50 people waiting for Tech Support and 10 for Billing, here is exactly who should be called next to save the most money."

3. The "Real-World" Test

To make sure their AI coach wasn't just guessing, they didn't use fake data. They used real data from a large U.S. bank's call center.

They looked at millions of real calls.
They built a digital twin of that specific bank's call center.
They tested their AI coach against standard rules that managers currently use (like "always serve the most expensive customer first" or "always send to the fastest agent").

4. The Results: Beating the Best

The paper tested this method on three types of problems:

Small problems: Where they could calculate the perfect answer by hand. The AI coach performed just as well as the perfect answer.
Medium problems (13 customer types): The AI coach beat the best existing rules by a small but significant margin.
Huge problems (100 customer types): This is where the magic happened. Traditional math methods completely fail here. The AI coach didn't just work; it crushed the competition, outperforming the best existing rules by about 7%. In the world of call centers, a 7% improvement in efficiency is a massive win.

5. A Surprising Discovery

The authors also found something interesting about how the agents should work.

Old Theory: Many experts thought agents should never sit idle if there is anyone waiting in the entire system (a rule called "Joint Work Conservation").
The Reality: The AI coach discovered that sometimes, it is actually better to let an agent sit idle, even if someone is waiting, because that agent might be the only one who can help a specific, high-priority customer later. The AI learned to break the "never idle" rule when the network structure (who can talk to whom) made it necessary.

The Bottom Line

This paper provides a new "GPS" for managing complex service systems. Just as a GPS finds the fastest route through a chaotic city by looking at traffic patterns in real-time, this method uses AI to find the best way to route customers to agents in massive, busy call centers. It proves that with the right computational tools, we can manage systems that are too big for humans or old math to handle, leading to faster service and lower costs.

Technical Summary: Dynamic Scheduling of a Parallel-Server Queueing System

Problem Definition
The paper addresses the operational challenge of skill-based routing in large-scale parallel-server queueing systems, such as call centers. The core problem involves making real-time decisions on which waiting customer class should be served by which available agent. In systems with many customer classes and service stations, the state space becomes high-dimensional, rendering standard dynamic programming methods computationally intractable due to the "curse of dimensionality." The authors focus on the Halfin–Whitt heavy-traffic regime and an infinite-horizon discounted cost criterion, aiming to develop a scalable computational method for these high-dimensional settings.

Methodology
The proposed approach bridges the gap between theoretical heavy-traffic limits and practical computation through the following steps:

Diffusion Approximation: The authors formulate an approximating Brownian control problem (BCP) derived from the original discrete-flow queueing model under the Halfin–Whitt asymptotic regime. This involves scaling the system state and control processes to derive a limiting diffusion process governed by a stochastic differential equation.
Hamilton-Jacobi-Bellman (HJB) Formulation: The optimal control problem for the BCP is characterized by a semilinear partial differential equation (PDE), specifically the HJB equation. The solution to this PDE provides the value function and its gradient, which are necessary to construct an optimal policy.
Deep Learning-Based Solution: Recognizing that traditional numerical methods (e.g., finite-element methods) fail in high dimensions, the authors adapt the deep learning framework of Han et al. (2018) for solving semilinear PDEs.
- Stochastic Identity: They derive a specific stochastic identity (Proposition 1) equivalent to the HJB equation. This identity links the value function and its gradient to the system's drift, diffusion, and cost terms via a backward stochastic differential equation (BSDE) representation.
- Neural Network Approximation: The value function $V(x)$ and its gradient $\nabla V(x)$ are approximated by deep neural networks.
- Loss Function: A loss function is constructed based on the discrepancy in the derived stochastic identity over simulated sample paths of a reference policy. The network parameters are optimized using stochastic gradient descent to minimize this loss.
- Policy Construction: Once the gradient network is trained, the policy for the original (prelimit) system is constructed by solving a linear program at each state. This linear program maximizes a term derived from the HJB equation's supremum, utilizing the learned gradient values as coefficients.

Key Contributions

Scalable Computational Framework: The primary contribution is a computational method capable of solving dynamic scheduling problems in high-dimensional parallel-server systems (up to 100 customer classes), a regime where standard MDP techniques are infeasible.
Handling Nonbasic Activities: Unlike prior theoretical works (e.g., Atar, 2005a) that often restrict analysis to "basic" activities and assume joint work conservation (JWC), this method accommodates general parallel-server networks where nonbasic activities may be utilized and JWC may not hold.
Data-Driven Calibration: The method is calibrated and tested using real-world data from a large U.S. bank call center, ensuring the test instances reflect realistic operational parameters, including arrival rates, service rates, abandonment rates, and cost structures.
Integration of Domain Knowledge: The approach incorporates domain-specific insights, such as generating representative sample paths and imposing shape constraints on the value function and its gradient, to improve solution quality.

Results
The authors evaluate the proposed policy against benchmark policies (including $c\mu$ , $c\mu/\theta$ , Fastest-Server-First, and G- $c\mu$ rules) across several test problems:

Low-Dimensional Problems: For 2-dimensional test problems where optimal policies can be computed via standard MDP techniques, the proposed neural network-based policy performs on par with the optimal policy, with optimality gaps of less than 1%.
High-Dimensional Problems: For the main 13-dimensional test problem (based on the bank data) and a 100-dimensional test problem, where optimal policies are unknown, the proposed policy consistently outperforms the best available benchmarks.
- In the 13-dimensional variant, the proposed policy improves performance by approximately 2% over the best benchmark.
- In the 100-dimensional problem, the improvement is approximately 7% over the best benchmark.
Behavioral Insights: The study reveals that in sparse network topologies, optimal policies may violate the joint work conservation property and utilize nonbasic activities significantly. The proposed method captures these behaviors naturally, whereas restricting policies to basic activities or enforcing JWC might exclude optimal strategies.

Significance and Claims
The paper claims to provide a scalable, data-driven computational framework for managing high-dimensional service systems that are too large for exact methods. It offers managers a tool to improve real-time routing decisions and evaluate policies before implementation. The authors position their work as a significant generalization of existing literature, moving from low-dimensional, restrictive theoretical models to high-dimensional, practical applications. They emphasize that their method does not assume joint work conservation or restrict activities to "basic" sets, thereby offering a more flexible and potentially more accurate representation of complex service systems. The paper concludes that the proposed approach is computationally feasible for systems with 100 or more distinct customer classes, a scale previously unattainable for dynamic optimization in this context.