Δ(i)/GI/1: A New Queueing Model For Transitory Queueing Systems

Harsha Honnappa, Rahul Jain, Amy R. WardarXiv 2012 · arXiv · OpenReview

Abstract: We introduce the Δ(i)/GI/1 queue, a new queueing model. In this model, customers from a given population independently sample a time to arrive from some given distribution F. Thus, the arrival times are an ordered statistics, and the inter-arrival times are differences of consecutive ordered statistics. They are served by a single server which provides service according to a general distribution G, with independent service times. The exact model is analytically intractable. Thus, we develop fluid and diffusion limits for the various stochastic processes, and performance metrics. The fluid limit of the queue length is observed to be a reflected process, while the diffusion limit is observed to be a function of a Brownian motion and a Brownian bridge process, and is given by a 'netput' process and a directional derivative of the Skorokhod reflected fluid netput in the direction of a diffusion refinement of the netput process. We also observe what may be interpreted as a transient Little's law. Sample path analysis reveals various operating regimes where the diffusion limit switches between a free diffusion, a reflected diffusion process and the zero process, with possible discontinuities during regime switches. The weak convergence is established in the M1 topology, and it is also shown that this is not possible in the J1 topology.

Introduction

Most classical queueing theory assumes systems are "stationary and ergodic," meaning they run indefinitely and eventually settle into a predictable steady state. However, many real-world scenarios—such as product launches, emergency room surges, or morning commutes—are inherently transitory. In these cases, a finite population of customers arrives over a specific window, and the system never reaches a steady state before the event concludes.

This paper introduces the $\Delta_{(i)}/GI/1$ queueing model to address these "one-off" queueing events. By treating arrival times as order statistics from a fixed population, the model captures the dependencies inherent in finite-population systems that standard Poisson models miss.

The Δ(i)/GI/1 Model

In the $\Delta_{(i)}/GI/1$ model, a population of $n$ customers independently chooses an arrival time from a distribution $F$. The actual arrival times are the ordered statistics $X_{(1)} \le X_{(2)} \le \dots \le X_{(n)}$. These customers are served by a single server with independent and identically distributed (i.i.d.) service times following a general distribution $G$ with mean $1/\mu$.

Because the inter-arrival times are differences of consecutive order statistics, they are not i.i.d., rendering the model analytically intractable for exact discrete-event solutions. To overcome this, we employ asymptotic analysis, considering the limit as the population size $n \to \infty$ and the service rate scales proportionally.

Fluid and Diffusion Limits

To analyze the system's behavior, we derive fluid and diffusion limits that approximate the stochastic queue length process $Q_n(t)$.

Fluid Limits

Using the Glivenko-Cantelli theorem, we show that as $n$ grows, the random queue length converges to a deterministic "fluid" process $\bar{Q}(t)$. This process is the Skorokhod reflection of the "netput"—the difference between the cumulative arrival distribution $F(t)$ and the cumulative service capacity $\mu t$.

Extracted figure from page 7 of Δ(i)/GI/1: A New Queueing Model For Transitory Queueing Systems

As shown in Figure 1, the system transitions through different regimes. When the arrival rate $f(t)$ exceeds the service rate $\mu$, the queue builds up (overloaded regime). When the service rate catches up, the queue depletes until it hits zero (underloaded regime).

Diffusion Limits

To capture the variance around the fluid average, we develop diffusion approximations. A key finding is that the arrival process converges to a Brownian bridge rather than standard Brownian motion. This occurs because the total number of arrivals is fixed at $n$; the process is "tied down" at the end of the arrival window. The resulting diffusion limit is a complex function involving this Brownian bridge and the Brownian motion of the service process.

Key Insights and Regime Switching

The model reveals that the system's stochastic behavior changes abruptly depending on the fluid state:

  1. Overloaded: The diffusion behaves like a free (unrestricted) diffusion process.
  2. Underloaded: The diffusion is essentially zero, as the server quickly clears any small fluctuations.
  3. Critically Loaded: The diffusion behaves like a reflected process at the boundary.

The transitions between these states can cause discontinuities in the diffusion limit. To handle these jumps mathematically, we establish convergence in the $M_1$ topology, proving that the more common $J_1$ topology is insufficient for this model.

Conclusion

The $\Delta_{(i)}/GI/1$ model provides a robust mathematical framework for managing transitory crowds. By relating queue lengths to arrival distributions through fluid and diffusion limits, it allows for better resource planning in systems where steady-state assumptions fail. Furthermore, the discovery of a transient version of Little's Law provides a path for real-time waiting time estimation during peak surge events.

Summary updated

Abstract

We introduce the {\Delta}(i)/GI/1 queue, a new queueing model. In this model, customers from a given population independently sample a time to arrive from some given distribution F. Thus, the arrival times are an ordered statistics, and the inter-arrival times are differences of consecutive ordered statistics. They are served by a single server which provides service according to a general distribution G, with independent service times. The exact model is analytically intractable. Thus, we develop fluid and diffusion limits for the various stochastic processes, and performance metrics. The fluid limit of the queue length is observed to be a reflected process, while the diffusion limit is observed to be a function of a Brownian motion and a Brownian bridge process, and is given by a 'netput' process and a directional derivative of the Skorokhod reflected fluid netput in the direction of a diffusion refinement of the netput process. We also observe what may be interpreted as a transient Little's law. Sample path analysis reveals various operating regimes where the diffusion limit switches between a free diffusion, a reflected diffusion process and the zero process, with possible discontinuities during regime switches. The weak convergence is established in the M1 topology, and it is also shown that this is not possible in the J1 topology.
BibTeX
@misc{honnappa2012i,
  author = {Harsha Honnappa and Rahul Jain and Amy R. Ward},
  title = {{Δ(i)/GI/1: A New Queueing Model For Transitory Queueing Systems}},
  year = {2012},
  eprint = {1206.0720},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1206.0720},
}
Figure