Permutation Predictions for Non-Clairvoyant Scheduling
  In non-clairvoyant scheduling, the task is to find an online strategy for
scheduling jobs with a priori unknown processing requirements with the
objective to minimize the total (weighted) completion time. We revisit this
well-studied problem in a recently popular learning-augmented setting that
integrates (untrusted) predictions in online algorithm design. While previous
works used predictions on processing requirements, we propose a new prediction
model, which provides a relative order of jobs which could be seen as
predicting algorithmic actions rather than parts of the unknown input. We show
that these predictions have desired properties, admit a natural error measure
as well as algorithms with strong performance guarantees and that they are
learnable in both, theory and practice. We generalize the algorithmic framework
proposed in the seminal paper by Kumar et al. (NeurIPS'18) and present the
first learning-augmented scheduling results for weighted jobs and unrelated
machines. We demonstrate in empirical experiments the practicability and
superior performance compared to the previously suggested single-machine
algorithms.
