🔢 mathematics

Tandem Queues with Hybrid Abandonment in Heavy Traffic

This paper provides the first heavy-traffic characterization of a two-stage tandem queue with abandonment only in the first stage, proving that the second-stage queue length is asymptotically exponentially distributed and independent of the first stage by extending Markovian arrival process techniques to hybrid-abandonment systems.

Original authors: Cameron Curtis, Izzy Grosof, Seyed Iravani

Published 2026-10-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Cameron Curtis, Izzy Grosof, Seyed Iravani

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

In the world of service and logistics, systems are often designed as a series of steps, where a customer or a piece of work moves from one station to the next. Think of a coffee shop where you first wait in line to order, and then wait again for your drink to be prepared. In many real-world situations, people or items do not wait forever; if the line is too long or the wait too tedious, they may leave the system entirely before receiving service. This act of leaving is known as abandonment. For decades, researchers studying these systems have mostly focused on two extreme scenarios: either no one ever leaves the line, or everyone is allowed to leave at every single stage. However, reality is often more nuanced. In many systems, the ability to leave changes depending on where you are in the process. A customer might be willing to walk away while waiting to order, but once the barista has started making the drink, they are unlikely to leave. Similarly, a patient might cancel an appointment while on a waiting list, but once surgery is scheduled, they rarely abandon the follow-up care. Understanding how these mixed systems behave, especially when they are under heavy pressure, has remained a difficult puzzle for mathematicians and engineers.

A team of researchers at Northwestern University has finally solved this puzzle for a specific, common type of system. They focused on a two-stage process where items can abandon the first stage but are locked in once they reach the second. To understand what happens when such a system is overwhelmed, the researchers looked at what occurs when the arrival of new items is so high that the servers are busy almost all the time. In this state of heavy traffic, the system behaves in a way that is surprisingly simple and predictable. The team discovered that the number of items waiting in the second stage follows a specific pattern: it is distributed in a way that is mathematically identical to a random process where the likelihood of having a certain number of items drops off steadily, much like how the chance of flipping a coin and getting heads many times in a row decreases with each flip. More importantly, they found that the length of the first queue and the length of the second queue become completely independent of each other. Even though the first queue feeds the second, once the system is under heavy load, the number of people waiting to order tells you nothing about how many people are waiting for their drinks.

To reach this conclusion, the researchers had to develop new mathematical tools because existing methods could not handle the complexity of a system where the "phase" of the arrival process—the state of the first queue—has an infinite number of possibilities. They treated the first queue not just as a waiting line, but as a complex machine that controls the flow of items into the second queue. By analyzing this machine, they proved that as the system gets busier, the behavior of the second queue stabilizes into a predictable shape. They showed that the average number of items in the second queue can be estimated with a simple formula that depends only on how close the system is to being completely full. This formula works because the chaotic fluctuations of the first queue effectively wash out, leaving the second queue to behave on its own.

The researchers did not stop at theoretical proof; they tested their findings against real-world simulations to see if the math held up in practice. They ran thousands of computer experiments with different speeds of service and different rates of abandonment. The results were striking. Even when the system was not at the extreme limit of being fully loaded, but rather at a high but manageable level of traffic, their simple formula provided an incredibly accurate estimate of the average wait. In their tests, when the system was busy eighty percent of the time, the difference between their predicted average and the actual average was less than one customer. As the system got busier, the relative error shrank to less than one percent. Furthermore, the simulations confirmed that the two queues were indeed behaving independently, with the correlation between them dropping to near zero as the load increased.

This discovery offers a powerful new tool for managers and engineers who design these systems. Because the second queue behaves independently and predictably, it becomes much easier to decide how much capacity to build. For example, a manager trying to determine how many servers to hire for the second stage of a process can now use a straightforward calculation to balance the cost of hiring more staff against the cost of customers waiting. The researchers found that using their simplified formula to make these decisions resulted in a cost that was virtually identical to the cost of using a perfect, complex simulation. The only difference was that the simplified method slightly overestimated the cost, leading to a tiny bit of extra capacity, but this overestimation was so small—less than one percent of the total cost—that it is negligible in practice.

The work represents a significant step forward in understanding how complex, multi-stage systems function under pressure. By proving that a hybrid system with mixed abandonment rules behaves with such regularity, the researchers have provided a clear path for designing more efficient service networks. Whether it is a hospital managing patient flow, a factory processing raw materials, or a bank handling transactions, the insight that the second stage can be analyzed on its own terms offers a way to simplify complex problems. The study confirms that even in systems where people or items can leave at different points, the chaos of the first stage does not necessarily cascade into the second. Instead, under heavy traffic, the system settles into a state of calm predictability, allowing for better planning and more reliable service.

Technical Summary: Tandem Queues with Hybrid Abandonment in Heavy Traffic

Problem Statement
The paper addresses a gap in the existing literature regarding tandem queueing systems with abandonment. While prior heavy-traffic analyses have largely focused on systems where jobs abandon from either no stages or all stages, real-world systems often exhibit "hybrid-abandonment," where jobs may abandon at early stages but not at later stages. Examples include customers abandoning a coffee shop line before ordering but not after, or surgical patients leaving a waitlist before surgery but not after. The authors specifically investigate a two-stage tandem queue where abandonment occurs only in the first stage. The challenge is that existing heavy-traffic techniques for tandem queues (e.g., Jackson networks or networks with abandonment at all stations) do not easily generalize to this hybrid structure, particularly because the second queue's arrival process is driven by the departure process of the first queue, which is itself a complex stochastic process involving abandonment.

Methodology
To analyze this system, the authors generalize the hybrid-abandonment tandem queue into a broader class of models: Infinite-Phase Markovian Arrival Process (IMAP) queues. In this framework, the length of the first queue serves as the "phase process" ( $Y$ ) that modulates the arrivals to the second queue ( $Q$ ). Since the first queue can theoretically grow infinitely, the phase process has a countably infinite state space.

The analysis proceeds through the following methodological steps:

Heavy-Traffic Regime: The authors consider a sequence of systems where the arrival rate approaches a critical threshold such that the idleness of the second queue ( $\epsilon$ ) approaches zero.
Near-Inverse Matrix: They introduce a "near-inverse" matrix $R$ for the generator matrix of the phase process. This matrix allows them to "undo" the effects of the generator in balance equations, facilitating the derivation of asymptotic results.
Z-Transform Analysis: The authors utilize partial z-transforms to characterize the joint distribution of the phase process and the queue length. They derive "near-independence" and "near-exponential" equations that relate the system's state to the near-inverse matrix.
Light-Tailed Conditions: They define a set of sufficient conditions (termed "light-tailed phase process") under which the near-independence and near-exponential equations converge to true asymptotic independence and exponentiality.
Specialization to Birth-Death Processes: For the specific case of birth-death phase processes (which includes the hybrid-abandonment model), they prove that "rate-boundedness" and "uniform stability" are sufficient to satisfy the light-tailed conditions.
Empirical Validation: The authors conduct numerical simulations to test the accuracy of their heavy-traffic approximations outside the asymptotic regime, specifically examining mean queue length accuracy, correlation between stages, distributional fit, and application to capacity planning.

Key Contributions and Results
The paper provides the first heavy-traffic characterization of the second queue length in a two-stage tandem queue with abandonment only in the first stage. The primary theoretical results are:

Asymptotic Independence and Exponentiality: The authors prove that in the heavy-traffic limit ( $\epsilon \to 0$ ), the scaled second queue length ( $\epsilon Q$ ) is asymptotically exponentially distributed and is asymptotically independent of the first queue length (the phase process).
General IMAP Results: They establish Theorem 1, showing that for general IMAP queues with a "light-tailed" phase process, the scaled queue length converges to an exponential distribution with a specific mean $M(0)$ .
Birth-Death Conditions: Theorem 2 provides easier-to-check sufficient conditions (uniform stability and rate-boundedness) for birth-death phase processes to satisfy the light-tailed requirements.
Hybrid-Abandonment Application: Theorem 3 applies these general results to the hybrid-abandonment tandem queue, proving it satisfies the necessary conditions. Consequently, the scaled second queue length has a mean of $M(0)$ and follows an exponential distribution, independent of the first queue.

Empirical Findings
The numerical study in Section 6 demonstrates that these heavy-traffic approximations are useful even when the system is not in the strict asymptotic limit (i.e., for loads $\rho \ge 0.8$ ):

Mean Accuracy: The approximation for the mean second queue length, $E[Q_2] \approx M(0)/(1-\rho)$ , is highly accurate. While the absolute error remains roughly constant (around -0.75 jobs), the relative error shrinks significantly as load increases (from -17% at $\rho=0.8$ to -0.9% at $\rho=0.99$ ).
Independence: The empirical correlation between the first and second queue lengths is negligible (magnitude < 0.1) and decreases as load increases, supporting the asymptotic independence claim.
Distributional Fit: The scaled queue length $(1-\rho)Q_2$ is well-approximated by an exponential distribution, though the unscaled queue length $Q_2$ is better approximated by a geometric distribution.
Capacity Management: When applied to an optimal capacity selection problem, the heavy-traffic approximation yields a capacity level very close to the true optimum, resulting in an extremely low relative excess cost (below 0.6%), despite the approximation consistently overestimating the total system cost.

Significance
The paper claims significance primarily for providing the first rigorous heavy-traffic analysis of hybrid-abandonment systems, a class of models prevalent in medical, service, and computing systems but previously unanalyzed in this regime. By extending techniques from Markovian arrival processes to infinite-phase systems, the authors offer a structural characterization (asymptotic exponentiality and independence) that simplifies the understanding of complex tandem networks. Furthermore, the empirical results suggest that these asymptotic formulas serve as practical, accurate tools for managerial decision-making (such as capacity planning) in high-load settings, even before the system reaches the theoretical limit. The work also opens avenues for future research into infinite Markovian service processes and more complex queueing networks.

More like this