💻 computer science

Machine Learning-Based Waiting Time Prediction for Priority Queues with Preemptive and Non-Preemptive Service Rules

This paper demonstrates that machine learning models, particularly Recurrent Neural Networks, can accurately predict waiting times in complex, time-varying priority queueing systems using only queue length and customer priority, outperforming tree-based methods across non-preemptive and various preemptive service rules.

Original authors: Sahil Singh Bhandari, T.G. Deepak

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sahil Singh Bhandari, T.G. Deepak

Original paper licensed under CC BY 4.0 (https://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 are standing in a busy line at a theme park. Usually, the rule is "first come, first served." But in this paper, the authors look at a more complicated line where some people are VIPs (Priority 1) and some are regular guests (Priority 2). The VIPs get to cut in front, which changes how long everyone else has to wait.

The big question the authors asked is: Can we use a computer program (Machine Learning) to guess exactly how long a person will wait, even if the line is chaotic and the VIPs keep jumping in?

Here is a simple breakdown of what they did and what they found, using everyday analogies.

The Three Rules of the Line

The authors tested their computer programs under three different "rules of the road" for how the line works:

The "No Interruption" Rule (Non-Preemptive): Imagine a barber cutting a customer's hair. Even if a VIP walks in, the barber finishes the current haircut before switching. The person in the chair stays put.
The "Start Over" Rule (Preemptive-Repeat): Imagine a chef cooking a steak. If a VIP arrives, the chef stops cooking the regular customer's steak, throws it away, and starts a brand new one for the VIP. When the VIP is done, the regular customer has to start their steak from scratch.
The "Resume" Rule (Preemptive-Resume): Imagine a video game character fighting a boss. If a VIP arrives, the fight pauses. The regular customer's "health bar" stays exactly where it was. When the VIP leaves, the fight picks up right where it stopped.

The Data: A 200-Day Simulation

Since they couldn't wait 200 days in a real line to test this, they built a digital simulation. They created a fake world where:

People arrive at random times (sometimes the line is empty, sometimes it's a mob).
There are two types of people: VIPs and Regulars.
They ran this simulation for 200 "days" to generate a massive amount of data on who waited how long.

The Contest: Five Computer Brains

They pitted five different types of "computer brains" (Machine Learning models) against each other to see which one could best predict the wait time.

The "Tree" Brains (GBM & Random Forest): Think of these as a team of detectives asking a series of "Yes/No" questions. "Is the line long? Is the person a VIP?" They build a decision tree to guess the wait time. They also tested a version where they forced the detectives to split into two separate teams (one for VIPs, one for Regulars) to see if that helped.
The "Time-Traveler" Brain (RNN): This is a Recurrent Neural Network. Think of this as a brain that remembers the story of the line. It doesn't just look at the current moment; it remembers the sequence of people who arrived before. It understands that "a VIP arriving right after a long line of Regulars" creates a specific ripple effect.

The Big Findings

1. The "Time-Traveler" Brain Won the Race
The RNN (the one that remembers the sequence of events) was the clear winner. It was the most accurate at predicting wait times, especially in the chaotic "Start Over" and "Resume" rules where interruptions happen.

Why? Because waiting in a priority line isn't just about what's happening right now; it's about what happened just before and what might happen next. The RNN is good at reading that story.

2. The "Tree" Brains Were Good, But Not Perfect
The decision-tree models (GBM and Random Forest) did a decent job, but they weren't as sharp as the RNN. They struggled a bit more when the line was interrupted frequently.

3. Splitting the Team Didn't Help Much
The authors tried forcing the tree models to have separate teams for VIPs and Regulars (the "Forced Priority-Split"). They thought this might help the models focus better.

The Result: It barely made a difference. The standard models were already smart enough to figure out the difference between VIPs and Regulars on their own. Splitting them up was like hiring two separate chefs when one good chef could handle both menus.

4. The "Magic Two" Inputs
This is the most surprising part. Usually, to predict a wait time perfectly, you need to know everything: the exact arrival rate, the service speed, the time of day, etc.

The Discovery: The authors found that the models could predict wait times very accurately using only two pieces of information:
1. How many people are in line right now? (Queue Length)
2. Is the person a VIP or Regular? (Priority)
Even without knowing the time of day or how fast people usually arrive, just knowing the current crowd size and the person's status was enough for the computer to make a great guess.

The Bottom Line

The paper shows that you don't need a super-complex system with a million data points to predict wait times in a priority line.

If you want the best accuracy, use a model that remembers the sequence of events (like the RNN).
If you want simplicity, you can get surprisingly good results just by counting the people in line and checking their priority badge.

This is great news for real-world systems (like hospitals or call centers) because they often don't have perfect data on arrival rates, but they do know how many people are waiting and who is important. They can use these simple inputs to give people accurate wait-time estimates.

Technical Summary: Machine Learning-Based Waiting Time Prediction for Priority Queues

Problem Statement

The paper addresses the challenge of predicting transient waiting times in multi-class priority queuing systems operating under time-varying conditions. While classical queuing theory provides exact analytical results for simple, stationary systems, real-world applications (e.g., healthcare, call centers, logistics) often involve non-stationary arrival rates, complex service-time distributions, and preemption rules. In such environments, a customer's waiting time depends not only on the current queue state but also on future high-priority arrivals, making analytical prediction difficult.

The study specifically investigates whether machine learning (ML) models can accurately predict waiting times using limited, operationally observable data—specifically, the queue length at the moment of arrival and the customer's priority class—without requiring detailed knowledge of underlying arrival rate functions or service-time distributions.

Methodology

Data Generation

The authors generated a synthetic dataset simulating 200 independent days of a two-class priority queue ( $G(t)/G/1$ ) under a time-varying environment.

Arrival Process: Non-stationary arrivals were modeled using piecewise-homogeneous intervals with Phase-Type (PH) distributions to capture variability beyond simple exponential assumptions.
Service Discipline: Three distinct service rules were simulated:
1. Non-Preemptive: Service continues uninterrupted once started.
2. Preemptive-Repeat: A higher-priority arrival interrupts a lower-priority job, which must restart from the beginning upon resumption.
3. Preemptive-Resume: A higher-priority arrival interrupts a lower-priority job, which resumes from the point of interruption.
Features: Two feature configurations were tested:
1. Four-Feature Set: Arrival time, inter-arrival time, priority class, and queue length at arrival.
2. Two-Feature Set: Priority class and queue length at arrival only.

Models Evaluated

Five machine learning models were compared:

Gradient Boosting Machine (GBM): A standard ensemble of decision trees.
Forced Priority-Split GBM (FS-GBM): A variant where the dataset is hard-split by priority class before training separate GBM models.
Random Forest (RF): A standard ensemble of decorrelated decision trees.
Forced Priority-Split RF (FS-RF): A variant with separate RF models trained for each priority class.
Recurrent Neural Network (RNN): An LSTM-based architecture designed to capture temporal dependencies in the sequence of customer arrivals within a day.

Performance was evaluated using Mean Absolute Error (MAE), Mean Squared Error (MSE), Root Mean Squared Error (RMSE), and the coefficient of determination ( $R^2$ ).

Key Contributions

Unified Framework: The study provides a unified simulation framework for generating transient data across non-preemptive, preemptive-repeat, and preemptive-resume disciplines with time-varying arrivals.
Evaluation of Priority-Aware Structures: The paper explicitly tests whether hard-splitting data by priority class (FS-GBM, FS-RF) improves prediction over standard models that treat priority as a feature.
Minimal Information Feasibility: The research demonstrates that accurate waiting-time prediction is achievable using only two inputs (queue length and priority), challenging the assumption that detailed system parameters are necessary for data-driven approaches.
Comparative Analysis: It offers a comprehensive comparison between tree-based ensembles and sequence-based deep learning models in the context of priority queuing.

Results

Model Performance

RNN Superiority: The Recurrent Neural Network (LSTM) consistently achieved the highest accuracy across all three service disciplines and both feature settings. It demonstrated the ability to model complex temporal dynamics, particularly in preemptive settings where service interruptions create intricate dependencies.
- In the non-preemptive setting (4 features), the RNN achieved an $R^2$ of 0.987, compared to ~0.94 for tree-based models.
- In the preemptive-resume setting (the most complex scenario), the RNN maintained an $R^2$ of 0.987, while tree-based models dropped to ~0.927.
Tree-Based Stability: GBM and Random Forest models provided stable and competitive performance, particularly in non-preemptive settings. However, they showed reduced accuracy in preemptive scenarios compared to the RNN.
Ineffectiveness of Forced Splitting: The "Forced Priority-Split" variants (FS-GBM and FS-RF) offered only marginal and inconsistent improvements over their standard counterparts. The authors conclude that standard tree-based models are already capable of implicitly learning priority-specific nonlinearities when priority is included as an input feature, rendering explicit hard-splitting unnecessary.

Feature Reduction

Reducing the input features from four to two (removing arrival time and inter-arrival time) resulted in only a moderate decrease in performance.

The RNN maintained strong predictive power even with minimal inputs, achieving an $R^2$ of 0.974 in the non-preemptive case and 0.972 in the preemptive-resume case with only two features.
Tree-based models also remained stable, suggesting that queue length and priority encode the majority of the predictive information required.

Significance and Claims

The paper claims that machine learning, particularly sequence-based models like RNNs, offers a practical and powerful alternative to traditional analytical methods for real-time waiting-time prediction in priority-based service systems.

Practical Deployability: The finding that accurate predictions are possible using only queue length and priority is highlighted as a major practical advantage. In many real-world systems (e.g., hospitals, call centers), detailed arrival rate functions or service distributions are unknown or difficult to estimate, but queue length and priority are readily observable.
Handling Preemption: The study demonstrates that ML models can effectively capture the complex effects of preemption (both repeat and resume) without explicit modeling of the interruption logic, a task that is analytically challenging.
Model Selection: While RNNs are identified as the most effective for capturing temporal dynamics in preemptive systems, tree-based models are presented as reliable, stable, and computationally efficient alternatives, especially when interpretability or simpler architecture is preferred.
Limitations of Structural Modifications: The paper modestly concludes that explicitly forcing priority splits does not significantly enhance performance, suggesting that modern ensemble methods are robust enough to handle priority heterogeneity through standard feature inclusion.

The authors emphasize that their work bridges classical queuing theory and modern data-driven prediction, offering a framework suitable for systems with limited data availability and dynamic operating conditions.