🔢 mathematics

Near-optimal scheduling with general service times and IHR abandonment times

This paper addresses the dynamic scheduling problem in an M/G/N queue with general service times and IHR abandonment times by proving the indexability of the associated discrete-time problem, deriving an explicit Whittle index, and demonstrating through simulations that the resulting policy systematically outperforms the standard $c\mu/\theta$ -rule.

Original authors: Samuli Aalto

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Samuli Aalto

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 a busy coffee shop where customers are lining up to get their drinks, but there's a twist: every customer has a secret timer. If they wait too long, they get frustrated and leave without buying anything. The baristas (the servers) have to decide who to serve next. Should they serve the person who has been waiting the longest? The person who only needs a quick espresso? Or the person who is about to give up and walk away? This is the heart of a problem called "scheduling," a branch of math and computer science that figures out the best way to organize tasks when resources are limited and time is ticking.

In the world of scheduling, there are two main types of costs to worry about. First, there's the "holding cost," which is like the energy and patience lost while a customer waits in line. Second, there's the "abandonment penalty," which is the lost sale and bad reputation when a customer leaves angry. For decades, mathematicians have tried to solve this puzzle, but they usually made a big simplification: they assumed that service times (how long a drink takes) and patience times (how long a customer waits) followed a simple, predictable pattern called an "exponential distribution." Think of this like assuming every coin flip is perfectly random and independent. While this makes the math easier, it doesn't reflect real life, where some tasks take a very long time and some people are incredibly patient or incredibly impatient.

This paper, written by Samuli Aalto, tackles the messy, real-world version of this problem. Instead of assuming simple, predictable patterns, the author allows for any kind of service time (like a complex latte that takes forever) and a specific type of impatience called "IHR" (Increasing Hazard Rate). IHR is a fancy way of saying that the longer you wait, the more likely you are to get fed up and leave—just like a real human getting angrier the longer the line moves slowly. The paper uses a clever mathematical tool called the "Whittle index" to figure out the best order to serve people. The main finding is that this new method, which handles these complex, real-world scenarios, consistently beats the old, standard rule of thumb (called the $c\mu/\theta$ -rule) in computer simulations. The author proves that their new formula is mathematically sound for a simplified version of the problem and then shows through simulations that it saves more money and keeps more customers happy than the previous best methods.

The Story of the Impatient Line

Picture a chaotic airport security line. You have a team of security officers (the servers) and a stream of travelers (the customers). Each traveler has two invisible clocks running. One clock counts down their service time—how long it takes to scan their bag and check their ID. The other clock counts down their patience time—how long they are willing to stand there before they decide to skip the flight and go home.

In the old days, mathematicians modeling this line assumed that both clocks ticked down in a very specific, "memoryless" way. It was like saying that no matter how long you've been standing there, your chance of leaving in the next minute is exactly the same as it was when you first arrived. This is the "exponential" assumption. It's a neat trick for math, but it's not how real people behave. In reality, if you've been waiting for 20 minutes, you are much more likely to storm off in the next minute than if you had just arrived. This is what the paper calls IHR (Increasing Hazard Rate): the longer you wait, the higher the risk you'll quit.

The author also realized that real service times aren't always simple. Sometimes a bag scan is instant; other times, it takes forever because of a weird lock on a suitcase. The paper allows for general service times, meaning the math can handle any shape of waiting time, from quick and easy to long and complicated.

The Magic Formula: The Whittle Index

So, how do you decide who to serve? The paper introduces a "Whittle index" as a scorecard for every single person in line. This score isn't just about who has been waiting the longest. It's a complex calculation that looks at:

How long they've already waited (x).
How much service they've already received (y).
How much it costs to keep them waiting (holding cost).
How much it costs if they leave (abandonment penalty).

The author proves that for a simplified version of this problem (a "closed" system where no new people arrive), this scorecard is mathematically perfect. It's "indexable," which is a fancy way of saying you can rank everyone from "serve me now!" to "I'll wait a bit."

The paper then takes this scorecard and adapts it for the real, continuous world where people are constantly arriving. The resulting formula, $W_k(x, y)$ , is a bit intimidating to look at, but it essentially asks: "If I serve this person for a tiny bit of time, how much money will I save compared to the risk of them leaving?"

The Showdown: New vs. Old

To see if this new "Whittle Index Policy" (WHI) actually works, the author ran thousands of computer simulations. They set up a virtual airport with two types of travelers:

Class 1: Short jobs (quick scans) but varying levels of patience.
Class 2: Long jobs (complex scans) with different patience levels.

They tested four different scenarios by mixing up the types of service times (some were uniform, some were "Pareto" which means a few people take forever) and the cost of abandonment (sometimes it's cheap to lose a customer, sometimes it's a huge loss).

The results were clear. The new Whittle Index policy systematically outperformed the old standard, known as the $c\mu/\theta$ -rule.

In the "Uniform-Uniform" scenario (where everyone is somewhat predictable), the new policy saved about 12% to 19% more in costs than the old rule.
In the "Uniform-Pareto" scenario (where some people have very long, unpredictable service times), the gap widened. The new policy saved 33% to 42% more than the old rule.
Even in the trickiest scenarios, the new policy was consistently better, sometimes by as much as 52%.

The paper also compared the new method to other common strategies like "First-Come-First-Served" (serving the oldest person first) and "Processor-Sharing" (splitting the server's time equally among everyone). The new Whittle Index beat them all.

Why This Matters

The key takeaway is that by letting go of the "perfectly random" assumptions and embracing the messy reality of how people actually get impatient, we can build much better systems. Whether it's a coffee shop, a call center, or a computer network processing data, using this new formula means fewer angry customers leaving, less wasted time, and more money saved. The author didn't just guess this; they proved the math works for the simplified version and showed through rigorous simulations that it works wonders in the complex, real-world version. It's a reminder that sometimes, the best way to solve a problem is to stop pretending the world is simpler than it really is.

Technical Summary: Near-optimal scheduling with general service times and IHR abandonment times

Problem Statement
This paper addresses the dynamic scheduling problem within a multi-class $M/G/N$ queueing system featuring impatient customers. The system consists of $N$ homogeneous parallel servers and multiple customer classes. Each customer possesses a random service time and a random abandonment time; if a customer remains in the system (waiting or in service) beyond their abandonment time, they leave without completing service.

The objective is to determine a non-anticipating scheduling policy (allowing preemption) that minimizes the total expected cost. This cost function comprises two components:

Holding costs: Accrued at a rate $h_k$ for class- $k$ customers while they remain in the system.
Abandonment penalties: A lump-sum penalty $d_k$ incurred if a class- $k$ customer abandons the system before service completion.

While existing literature often assumes exponential distributions for both service and abandonment times, exact solutions remain elusive except for special cases. Previous near-optimal approaches, such as fluid-scaling methods yielding the $c\mu/\theta$ -rule, rely heavily on these restrictive exponential assumptions. This paper aims to generalize the problem by allowing general service time distributions and Increasing Hazard Rate (IHR) abandonment times, a natural assumption where the probability of abandonment increases with the time spent in the system.

Methodology
The authors employ the Whittle index approach, a heuristic method originally designed for restless bandit problems, which are generally mathematically intractable. The methodology proceeds through the following stages:

Discrete-Time Formulation: The problem is first modeled in discrete time with discounted costs. The system is treated as a closed version (finite number of customers, no new arrivals) to facilitate analysis. The state of a customer is defined by a two-dimensional pair $(x, y)$ , where $x$ is the total time spent in the system and $y$ is the attained service.
Relaxation and Indexability: The strict capacity constraint (serving at most $N$ customers) is relaxed to a time-averaged constraint. This transforms the problem into a set of separable subproblems (one per customer). The authors prove that this relaxed problem is indexable, meaning there exists a threshold (the Whittle index) for the "price of work" $\nu$ such that it is optimal to serve a customer if and only if their index exceeds $\nu$ .
Derivation of the Index: A significant theoretical challenge is the two-dimensional state space, which lacks the natural ordering found in one-dimensional problems. The authors derive an explicit expression for the Whittle index in the discrete-time setting, denoted as $W_{k,\beta}(x, y)$ , involving a maximization over a time horizon $\Delta$ .
Continuous-Time Limit: The discrete-time results are extended to the original continuous-time open system. By letting the time slot approach zero and scaling probabilities, the authors derive the continuous-time Whittle index $W_k(x, y)$ .

Key Contributions

Generalization of Assumptions: The paper removes the restrictive assumption of exponential service times, accommodating general distributions, while assuming IHR for abandonment times.
Theoretical Proof of Indexability: The authors prove that the closed discrete-time version of the problem is indexable. This is a non-trivial result given the two-dimensional state space $(x, y)$ , which complicates standard proofs that rely on state ordering.
Explicit Index Formula: An explicit expression for the Whittle index is derived for the general case:
$W_k(x, y) = \sup_{\Delta>0} \frac{E\left[ (h_k((D_k - x) - (S_k - y)) + d_k) \mathbb{1}_{\{S_k - y < \min\{D_k - x, \Delta\}\}} \mid D_k > x, S_k > y \right]}{E[\min\{D_k - x, S_k - y, \Delta\} \mid D_k > x, S_k > y]}$
The paper also identifies specific conditions under which this index simplifies to known forms (e.g., when service times are Decreasing Hazard Rate (DHR) or when abandonment times are exponential).
Policy Definition: A Whittle index policy (WHI) is defined for the continuous-time setting: at any time $t$ , the scheduler serves the $N$ customers with the highest Whittle indices.

Results
The performance of the proposed Whittle index policy (WHI) is evaluated against the well-known $c\mu/\theta$ -rule (CMTH) and other standard policies (FCFS, Processor-Sharing, Forward-Backward) via numerical simulations in a two-class $M/G/1$ queue.

Systematic Outperformance: Across various experimental setups involving different combinations of service time distributions (Uniform/IHR and Pareto/DHR) and cost structures, the WHI policy systematically outperforms the $c\mu/\theta$ -rule and other baseline policies.
Sensitivity to Distribution Shape: The simulations demonstrate that the performance gap between WHI and CMTH widens significantly when service times follow heavy-tailed (DHR) distributions (e.g., Pareto). In these scenarios, the $c\mu/\theta$ -rule, which assumes exponential service times, can perform substantially worse (e.g., relative cost differences exceeding 40-50% in some heavy-load scenarios).
Robustness: The WHI policy maintains superior performance regardless of whether the abandonment costs or holding costs are emphasized, and across varying system loads ( $\rho \in [1.0, 2.0]$ ).

Significance
The paper claims that its primary significance lies in extending the applicability of the Whittle index approach to a more realistic and complex scheduling environment. By proving indexability and deriving the index for general service times and IHR abandonment, the work provides a theoretically grounded heuristic for problems where exact solutions are unavailable. The numerical results suggest that relying on exponential assumptions (as in the $c\mu/\theta$ -rule) can lead to suboptimal scheduling decisions, particularly when service times are non-exponential, and that the derived Whittle index policy offers a robust, near-optimal alternative.

The Story of the Impatient Line

The Magic Formula: The Whittle Index

The Showdown: New vs. Old

Why This Matters

Technical Summary: Near-optimal scheduling with general service times and IHR abandonment times

More like this