A new transitory queueing model and its process limits

Harsha Honnappa, Rahul Jain, Amy R. Ward

Authors: Harsha Honnappa, Rahul Jain, and Amy Ward

Introduction

Classical queueing theory, exemplified by models like $M/M/1$ or $M/G/1$, typically focuses on systems operating in a steady state. These models assume that arrival and service rates eventually balance out over an infinite horizon. However, many practical scenarios—such as product launches, concert entries, or lunch rushes—are inherently "transitory." In these cases, a finite population arrives within a specific time window, and the system clears once all customers are served. This paper addresses the gap in modeling such systems by introducing the $\Delta_{(i)}/GI/1$ queue.

The $\Delta_{(i)}/GI/1$ Queue Model

In the $\Delta_{(i)}/GI/1$ model, $n$ customers independently choose their arrival times from a common distribution $F$. The actual arrival process is defined by the ordered sequence of these times—the order statistics. Service times are independent and identically distributed (i.e.d.) following a general distribution $G$. Unlike standard renewal processes where inter-arrival times are independent, the use of order statistics introduces dependencies between arrivals, necessitating new analytical techniques to describe the system's evolution.

Fluid Limits and System Behavior

To understand the system's macroscopic behavior as the population $n$ grows large, the authors derive fluid limits using the Functional Strong Law of Large Numbers (FSLLN) and the Glivenko-Cantelli theorem. The scaled queue length process converges to a deterministic fluid limit, $\bar{Q}(t)$, which can be visualized as a reflected process. This limit captures the "average" trajectory of the queue, showing how it builds up during peak arrival periods and eventually dissipates.

The fluid limit $\bar{Q}(t)$ represented as the reflection of the net-input process.

Diffusion Limits and Regime Switching

While fluid limits describe the average behavior, diffusion limits provide insight into the stochastic fluctuations or "noise" around that average. Using the Functional Central Limit Theorem (FCLT), the authors show that the arrival process converges to a Brownian Bridge—a stochastic process tied down at both ends, reflecting the constraint that all $n$ customers must arrive by the end of the observation period.

A significant finding is that the diffusion limit $\hat{Q}(t)$ is not static. Instead, it switches between different regimes based on the instantaneous traffic intensity $\rho(t)$:

  1. Free Diffusion (B.M.): Occurs when the system is heavily overloaded.
  2. Reflected Diffusion (R.B.M.): Occurs when the system is near the boundary of being empty.
  3. Zero Process: Occurs when the system is underloaded and the queue is empty.
Regime switching in the diffusion limit $\hat{Q}(t)$.

Key Insights and Results

  • Transient Little’s Law: The authors establish a version of Little’s Law ($L = \lambda W$) applicable to these non-steady-state systems, providing a fundamental relationship between queue length and waiting times in transitory contexts.
  • Discontinuities: The research reveals that the diffusion limit can exhibit jumps when transitioning between overloaded and underloaded states, a phenomenon not typically seen in steady-state models.
  • Convergence and Accuracy: Numerical simulations with population sizes up to $n=1000$ demonstrate that the theoretical fluid and diffusion limits accurately predict the mean queue length and variance of the simulated systems, validating the mathematical framework.

Conclusion and Future Directions

The $\Delta_{(i)}/GI/1$ model provides a robust framework for analyzing finite-population, time-constrained queueing systems. Future work aims to extend these results to non-smooth arrival distributions and different service disciplines beyond First-Come-First-Served (FCFS). Additionally, validating the model against empirical data from real-world service centers—such as DMV offices or enterprise call centers—remains a key objective to refine its predictive power in human-centric environments.

Summary updated

BibTeX
@inproceedings{honnappa2012new,
  author = {Harsha Honnappa and Rahul Jain and Amy R. Ward},
  title = {{A new transitory queueing model and its process limits}},
  booktitle = {VALUETOOLS},
  year = {2012},
  doi = {10.4108/valuetools.2012.250299},
}

Loading related content...

Figure