SkipPredict: When to Invest in Predictions for Scheduling
Rana Shahout Michael Mitzenmacher
In light of recent work on scheduling with predicted job sizes, we consider
the effect of the cost of predictions in queueing systems, removing the
assumption in prior research that predictions are external to the system's
resources and/or cost-free. In particular, we introduce a novel approach to
utilizing predictions, SkipPredict, designed to address their inherent cost.
Rather than uniformly applying predictions to all jobs, we propose a tailored
approach that categorizes jobs based on their prediction requirements. To
achieve this, we employ one-bit "cheap predictions" to classify jobs as either
short or long. SkipPredict prioritizes predicted short jobs over long jobs, and
for the latter, SkipPredict applies a second round of more detailed "expensive
predictions" to approximate Shortest Remaining Processing Time for these jobs.
Our analysis takes into account the cost of prediction. We examine the effect
of this cost for two distinct models. In the external cost model, predictions
are generated by some external method without impacting job service times but
incur a cost. In the server time cost model, predictions themselves require
server processing time, and are scheduled on the same server as the jobs.