32 citations · 67 across the 9 of their papers we have counts for
5 papers · 1 filter
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…