Fluid approximations of many-server queues with delayed feedback and heterogeneous service and patience times

Weining Kang, Hongyuan Lu, Guodong PangSigmetrics Perform. Evaluation rev 2013 · DOI

TL;DR

This paper introduces a fluid approximation model for complex many-server queueing systems where customers can re-enter the system (feedback) and have different service and patience times. The authors develop a computational algorithm for time-varying scenarios, demonstrating its effectiveness in accurately predicting system behavior compared to simulations.

What Problem Does This Paper Address?

Many real-world service systems, like customer contact centers and hospitals, involve customers who might need to return for additional service after their initial interaction. These "reentrant" customers can have different needs and behaviors than new customers. Specifically, their service times might vary (e.g., due to prior experience) and their patience levels while waiting in queue can also differ. Existing queueing models often struggle to capture these nuances, especially when dealing with a large number of servers and the complexities of feedback loops. This paper tackles the challenge of modeling such systems by developing a fluid approximation that simplifies the complex stochastic dynamics into continuous fluid flows, making analysis and computation more tractable.

Methods

The core of this paper is the development of a two-parameter fluid model. This model represents the system's dynamics using continuous fluid processes that track the amount of "fluid" (representing customers) in different states: in service (with varying service progress) and in queue (with varying waiting times up to patience limits). The authors define a set of differential equations that govern these fluid flows, accounting for new and feedback customers separately, their distinct service and patience times, and the feedback mechanism.

A key contribution is the development of an algorithm to compute solutions for this fluid model, particularly when the customer arrival rate changes over time. This algorithm allows for the prediction of system performance measures without resorting to computationally expensive simulations. The authors validate their approach by comparing the results of their algorithm with direct simulations in various scenarios.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and computational algorithms, with numerical experiments conducted using simulated data based on specified parameter values.

Key Insights and Ideas

  • Fluid Approximation for Complexity: The paper demonstrates that a fluid approximation can effectively capture the essential dynamics of complex many-server queueing systems with reentrant customers and differentiated service/patience times, offering a computationally efficient alternative to detailed simulations.
  • Impact of Differentiation: The study highlights how differences in service times and patience levels between new and feedback customers significantly influence system performance. For instance, increased service differentiation can lead to longer queues and higher abandonment rates.
  • Monotonicity in Overload: Under overloaded conditions, the performance measures exhibit predictable monotonic behavior with respect to service and patience differentiation coefficients, allowing for insights into how system design choices impact outcomes.
  • Algorithm Efficacy: The proposed algorithm for computing time-varying fluid models is shown to be highly effective, providing accurate approximations that closely match simulation results.

Key Results

The paper presents numerical examples in Table 1, comparing simulation results with their fluid model approximations for both Markovian and non-Markovian scenarios. The approximations show excellent agreement with simulations across various performance measures, including:

  • Average number of customers in queue (Q1, Q2)
  • Average number of customers in service (B1, B2)
  • Number of customers in the delay orbit (Z)
  • Abandonment probabilities (P1(ab), P2(ab))
  • Average waiting times in queue (W1, W2)
  • Average waiting time at the front of the queue (X)

For example, in a non-Markovian scenario, the approximated Q1 was 79.51 compared to a simulated value of 79.60 (±0.9222), and W1 was 0.16 compared to 0.14 (±0.0002). Figure 1 further illustrates the close match between simulated and approximated time-varying fluid processes.

Limitations and Future Work

  • Assumptions: The fluid model relies on the assumption of a "many-server regime," where the number of servers and arrival rates are large. The applicability to systems with fewer servers might be limited. The model also assumes independence of various processes (arrival, service, patience, delay).
  • Future Work: The authors suggest characterizing the limiting behavior of performance measures as differentiation coefficients approach zero or infinity. Further exploration of the impact of these differentiation coefficients on system performance and the development of more sophisticated fluid models for even more complex scenarios could be future directions. The paper also mentions that the proofs of the fluid model's existence and uniqueness rely on prior work, implying that extending these proofs to the current model is a significant theoretical undertaking.

Summary updated

BibTeX
@article{kang2013fluid,
  author = {Weining Kang and Hongyuan Lu and Guodong Pang},
  title = {{Fluid approximations of many-server queues with delayed feedback and heterogeneous service and patience times}},
  journal = {Sigmetrics Perform. Evaluation rev},
  year = {2013},
  doi = {10.1145/2567529.2567544},
}
Figure