Uniform Bounds for Scheduling with Job Size Estimates
We consider the problem of scheduling to minimize mean response time in queues where only estimated job sizes (processing times) are known to the scheduler. We study this problem from a stochastic perspective, assuming random arrival times, job sizes, and job size estimates (specifically, an M/G/1 queueing model). We study the question: how well can simple scheduling policies perform? How close can we get to the performance of Shortest Remaining Processing Time (SRPT), the optimal policy when true job sizes are known? Do we need to know how noisy the estimates are to achieve good performance? We answer these questions by studying several simple scheduling policies. We show that two policies, including one novel policy, perform comparably to SRPT under low estimation noise, with graceful degredation as noise increases. The policies achieve this without knowedge of the job size distribution or estimation noise.
Based on joint work with Isaac Grosof and Michael Mitzenmacher.