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.
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)$:
- Free Diffusion (B.M.): Occurs when the system is heavily overloaded.
- Reflected Diffusion (R.B.M.): Occurs when the system is near the boundary of being empty.
- Zero Process: Occurs when the system is underloaded and the queue is empty.
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