32 citations · 92 across the 17 of their papers we have counts for
18 papers
Optimal Scheduling in Generalized Switch in Heavy Traffic
Runhan Xie, Ziv Scully, Rhonda Righter +1
The generalized switch is a highly flexible queueing model, covering multiclass, multiserver, and multiresource queueing systems as well as a wide variety of stochastic networks. A…
Beyond Prediction: Tail-Aware Scheduling for LLM Inference
Yueying Li, Yuanfan Chen, Jiayang Chen +6
LLM serving exhibits extreme length variability, making size-based scheduling difficult in practice. Recent LLM schedulers approximate SJF/SRPT using predicted decode lengths or ra…
Combinatorial Selection with Costly Information
Shuchi Chawla, Dimitris Christou, Amit Harlev +1
We consider a class of optimization problems over stochastic variables where the algorithm can learn information about the value of any variable through a series of costly steps; w…
Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1
George Yu, Ziv Scully
We study the problem of scheduling jobs in a queueing system, specifically an M/G/1 with light-tailed job sizes, to asymptotically optimize the response time tail. This means sched…
Heavy-Traffic Optimal Size- and State-Aware Dispatching
Runhan Xie, Isaac Grosof, Ziv Scully
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 relev…
Performance of the Gittins Policy in the G/G/1 and G/G/k, With and Without Setup Times
Yige Hong, Ziv Scully
How should we schedule jobs to minimize mean queue length? In the preemptive M/G/1 queue, we know the optimal policy is the Gittins policy, which uses any available information abo…
Optimal Scheduling in the Multiserver-job Model under Heavy Traffic
Isaac Grosof, Ziv Scully, Mor Harchol-Balter +1
Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Essentially all of the theoretical work on multiserver-job systems focuses…
The Gittins Policy in the M/G/1 Queue
Ziv Scully, Mor Harchol-Balter
The Gittins policy is a highly general scheduling policy that minimizes a wide variety of mean holding cost metrics in the M/G/1 queue. Perhaps most famously, Gittins minimizes mea…
How to Schedule Near-Optimally under Real-World Constraints
Ziv Scully, Mor Harchol-Balter
Scheduling is a critical part of practical computer systems, and scheduling has also been extensively studied from a theoretical perspective. Unfortunately, there is a gap between…
When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail?
Ziv Scully, Lucas van Kreveld
We consider scheduling in the M/G/1 queue with unknown job sizes. It is known that the Gittins policy minimizes mean response time in this setting. However, the behavior of the tai…
Uniform Bounds for Scheduling with Job Size Estimates
Ziv Scully, Isaac Grosof, Michael Mitzenmacher
We consider the problem of scheduling to minimize mean response time in M/G/1 queues where only estimated job sizes (processing times) are known to the scheduler, where a job of tr…
Nudge: Stochastically Improving upon FCFS
Isaac Grosof, Kunhe Yang, Ziv Scully +1
The First-Come First-Served (FCFS) scheduling policy is the most popular scheduling algorithm used in practice. Furthermore, its usage is theoretically validated: for light-tailed…
Optimal Multiserver Scheduling with Unknown Job Sizes in Heavy Traffic
Ziv Scully, Isaac Grosof, Mor Harchol-Balter
We consider scheduling to minimize mean response time of the M/G/k queue with unknown job sizes. In the single-server case, the optimal policy is the Gittins policy, but it is not…
Simple Near-Optimal Scheduling for the M/G/1
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
We consider the problem of preemptively scheduling jobs to minimize mean response time of an M/G/1 queue. When we know each job's size, the shortest remaining processing time (SRPT…
Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times
Isaac Grosof, Ziv Scully, Mor Harchol-Balter
Load balancing systems, comprising a central dispatcher and a scheduling policy at each server, are widely used in practice, and their response time has been extensively studied in…
SRPT for Multiserver Systems
Isaac Grosof, Ziv Scully, Mor Harchol-Balter
The Shortest Remaining Processing Time (SRPT) scheduling policy and its variants have been extensively studied in both theoretical and practical settings. While beautiful results a…
Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
Scheduling to minimize mean response time in an M/G/1 queue is a classic problem. The problem is usually addressed in one of two scenarios. In the perfect-information scenario, the…
SOAP: One Clean Analysis of All Age-Based Scheduling Policies
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
We consider an extremely broad class of M/G/1 scheduling policies called SOAP: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in t…