More Like this

1. SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers

   https://doi.org/10.1287/mnsc.2021.4110  

   Dong, Jing; Ibrahim, Rouba (October 2021, Management Science)

   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
2. Managing Queues with Different Resource Requirements

   https://doi.org/10.1287/opre.2022.2284  

   Zychlinski, Noa; Chan, Carri W.; Dong, Jing (July 2022, Operations Research)

   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
3. Heavy-Traffic Optimal Size- and State-Aware Dispatching

   https://doi.org/10.1145/3639035  

   Xie, Runhan; Grosof, Isaac; Scully, Ziv (February 2024, Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   Dispatching systems, where arriving jobs are immediately assigned to one of multiple queues, are ubiquitous in computer systems and service systems. A natural and practically relevant model is one in which each queue serves jobs in FCFS (First-Come First-Served) order. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. A major obstacle is that no nontrivial lower bound on mean delay is known, even in heavy traffic (i.e. the limit as load approaches capacity). This makes it difficult to prove that any given policy is optimal, or even heavy-traffic optimal. In this work, we propose the first size- and state-aware dispatching policy that provably minimizes mean delay in heavy traffic. Our policy, called CARD (Controlled Asymmetry Reduces Delay), keeps all but one of the queues short, then routes as few jobs as possible to the one long queue. We prove an upper bound on CARD's mean delay, and we prove the first nontrivial lower bound on the mean delay of any size- and state-aware dispatching policy. Both results apply to any number of servers. Our bounds match in heavy traffic, implying CARD's heavy-traffic optimality. In particular, CARD's heavy-traffic performance improves upon that of LWL (Least Work Left), SITA (Size Interval Task Assignment), and other policies from the literature whose heavy-traffic performance is known. 

   more » « less
4. Invariant States of Hydrodynamic Limits of Randomized Load-Balancing Networks

   https://doi.org/10.1287/moor.2020.0282  

   Agarwal, Pooja; Ramanan, Kavita (June 2025, Mathematics of Operations Research)

   Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of N parallel queues in which incoming jobs with independent and identically distributed service times are routed on arrival using the join-the-shortest-of-d-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as the size of the system goes to infinity, the state dynamics converge to the unique solution of a countable system of coupled deterministic measure-valued equations called the hydrodynamic equations. In this article, a characterization of invariant states of these hydrodynamic equations is obtained and, when d=2, used to construct a numerical algorithm to compute the queue length distribution and mean virtual waiting time in the invariant state. Additionally, it is also shown that under a suitable tail condition on the service distribution, the queue length distribution of the invariant state exhibits a doubly exponential tail decay, thus demonstrating a vast improvement in performance over the case [Formula: see text], which corresponds to random routing, when the tail decay could even be polynomial. Furthermore, numerical evidence is provided to support the conjecture that the invariant state is the limit of the steady-state distributions of the N-server models. The proof methodology, which entails analysis of a coupled system of measure-valued equations, can potentially be applied to other many-server systems with general service distributions, where measure-valued representations are useful. 

   more » « less
5. How Useful is Delayed Feedback in AoI Minimization - A Study on Systems With Queues in Both Forward and Backward Directions

   https://doi.org/10.1109/ISIT50566.2022.9834697  

   Wang, Chih-Chun (July 2022, Proc. IEEE International Symposium on Information Theory)

   One canonical example of Age-Of-Information (AoI) minimization is the update-through-queues models. Existing results fall into two categories: The open-loop setting for which the sender is oblivious of the actual packet departure time, versus the closed-loop setting for which the decision is based on instantaneous Acknowledgement (ACK). Neither setting perfectly reflects modern networked systems, which almost always rely on feedback that experiences some delay. Motivated by this observation, this work subjects the ACK traffic to an independent queue so that the closed-loop decision is made based on delayed feedback. Near-optimal schedulers have been devised, which smoothly transition from the instantaneous-ACK to the open loop schemes depending on how long the feedback delay is. The results thus quantify the benefits of delayed feedback for AoI minimization in the update-through-queues systems. 

   more » « less