skip to main content


Title: Time-Varying Queues
Service systems abound with queues, but the most natural direct models are often time-varying queues, which may require nonstandard analysis methods beyond stochastic textbooks. This paper provides an overview of time-varying queues. Most of the recent literature concerns many-server queues, which arise in large-scale service systems, such as in customer contact centers and hospital emergency departments, but there also has been some new work on single-server queues with time-varying arrivals, which arise in some settings, such as airplanes coming to land at an airport, cars coming to a traffic intersection and medical staff waiting for the availability of special operating rooms in a hospital. The understanding of many-server queues and single-server queues is enhanced by heavy-traffic limits, which have been extended to time-varying models as well as stationary models.  more » « less
Award ID(s):
1634133
NSF-PAR ID:
10120248
Author(s) / Creator(s):
Date Published:
Journal Name:
Queueing models and service management
Volume:
1
Issue:
2
ISSN:
2616-2679
Page Range / eLocation ID:
79-164
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Queueing models that are used to capture various service settings typically assume that customers require a single unit of resource (server) to be processed. However, there are many service settings where such an assumption may fail to capture the heterogeneity in resource requirements of different customers. We propose a multiserver queueing model with multiple customer classes in which customers from different classes may require different amounts of resources to be served. We study the optimal scheduling policy for such systems. To balance holding costs, service rates, resource requirement, and priority-induced idleness, we develop an index-based policy that we refer to as the idle-avoid [Formula: see text] rule. For a two-class two-server model, where policy-induced idleness can have a big impact on system performance, we characterize cases where the idle-avoid [Formula: see text] rule is optimal. In other cases, we establish a uniform performance bound on the amount of suboptimality incurred by the idle-avoid [Formula: see text] rule. For general multiclass multiserver queues, we establish the asymptotic optimality of the idle-avoid [Formula: see text] rule in the many-server regime. For long-time horizons, we show that the idle-avoid [Formula: see text] is throughput optimal. Our theoretical results, along with numerical experiments, provide support for the good and robust performance of the proposed policy. 
    more » « less
  2. The shortest-remaining-processing-time (SRPT) scheduling policy has been extensively studied, for more than 50 years, in single-server queues with infinitely patient jobs. Yet, much less is known about its performance in multiserver queues. In this paper, we present the first theoretical analysis of SRPT in multiserver queues with abandonment. In particular, we consider the M/GI/s+GI queue and demonstrate that, in the many-sever overloaded regime, performance in the SRPT queue is equivalent, asymptotically in steady state, to a preemptive two-class priority queue where customers with short service times (below a threshold) are served without wait, and customers with long service times (above a threshold) eventually abandon without service. We prove that the SRPT discipline maximizes, asymptotically, the system throughput, among all scheduling disciplines. We also compare the performance of the SRPT policy to blind policies and study the effects of the patience-time and service-time distributions. This paper was accepted by Baris Ata, stochastic models & simulation. 
    more » « less
  3. We study the ergodic properties of a class of controlled stochastic differential equations (SDEs) driven by a-stable processes which arise as the limiting equations of multiclass queueing models in the Halfin–Whitt regime that have heavy–tailed arrival processes. When the safety staffing parameter is positive, we show that the SDEs are uniformly ergodic and enjoy a polynomial rate of convergence to the invariant probability measure in total variation, which is uniform over all stationary Markov controls resulting in a locally Lipschitz continuous drift. We also derive a matching lower bound on the rate of convergence (under no abandonment). On the other hand, when all abandonment rates are positive, we show that the SDEs are exponentially ergodic uniformly over the above-mentioned class of controls. Analogous results are obtained for Lévy–driven SDEs arising from multiclass many-server queues under asymptotically negligible service interruptions. For these equations, we show that the aforementioned ergodic properties are uniform over all stationary Markov controls. We also extend a key functional central limit theorem concerning diffusion approximations so as to make it applicable to the models studied here. 
    more » « less
  4. Abstract

    We develop a robust queueing network analyzer algorithm to approximate the steady‐state performance of a single‐class open queueing network of single‐server queues with Markovian routing. The algorithm allows nonrenewal external arrival processes, general service‐time distributions and customer feedback. The algorithm is based on a decomposition approximation, where each flow is partially characterized by its rate and a continuous function that measures the stochastic variability over time. This function is a scaled version of the variance‐time curve, called the index of dispersion for counts (IDC). The required IDC functions for the external arrival processes can be calculated from the model primitives or estimated from data. Approximations for the IDC functions of the internal flows are calculated by solving a set of linear equations. The theoretical basis is provided by heavy‐traffic limits for the flows established in our previous papers. A robust queueing technique is used to generate approximations of the mean steady‐state performance at each queue from the IDC of the total arrival flow and the service specification at that queue. The algorithm's effectiveness is supported by extensive simulation studies.

     
    more » « less
  5. Many service systems provide queue length information to customers, thereby allowing customers to choose among many options of service. However, queue length information is often delayed, and it is often not provided in real time. Recent work by Dong et al. [Dong J, Yom-Tov E, Yom-Tov GB (2018) The impact of delay announcements on hospital network coordination and waiting times. Management Sci. 65(5):1969–1994.] explores the impact of these delays in an empirical study in U.S. hospitals. Work by Pender et al. [Pender J, Rand RH, Wesson E (2017) Queues with choice via delay differential equations. Internat. J. Bifurcation Chaos Appl. Sci. Engrg. 27(4):1730016-1–1730016-20.] uses a two-dimensional fluid model to study the impact of delayed information and determine the exact threshold under which delayed information can cause oscillations in the dynamics of the queue length. In this work, we confirm that the fluid model analyzed by Pender et al. [Pender J, Rand RH, Wesson E (2017) Queues with choice via delay differential equations. Internat. J. Bifurcation Chaos Appl. Sci. Engrg. 27(4):1730016-1–1730016-20.] can be rigorously obtained as a functional law of large numbers limit of a stochastic queueing process, and we generalize their threshold analysis to arbitrary dimensions. Moreover, we prove a functional central limit theorem for the queue length process and show that the scaled queue length converges to a stochastic delay differential equation. Thus, our analysis sheds new insight on how delayed information can produce unexpected system dynamics. 
    more » « less