Dynamic Scheduling with Expert Predictions

We consider a non-clairvoyant scheduling problem in which the algorithm has access to a set of experts and must learn in order to identify the useful experts. In particular, each expert predicts a job size for each incoming job, and the objective is to minimize total flow time in the M/G/1 setting. With access to an empirical risk minimization oracle over the experts, we are able to discover a good predictor from a large set, rather than assuming we have a good predictor from the beginning.