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.
翻译:在非clairvoyant的日程安排中,我们的任务是找到一个在线战略,用于安排具有先验的未知处理要求的工作,目的是尽量减少总(加权)完成时间。我们在最近一个将(不信任的)预测纳入在线算法设计之中的受欢迎的学习强化环境中,重新审视了这一经过广泛研究的问题。虽然以前的工作使用了对处理要求的预测,但我们提出了一个新的预测模型,该模型提供了相对的工作顺序,可以被视为预测算法行动,而不是未知输入的部分内容。我们显示这些预测具有理想的特性,接受自然错误计量以及具有很强性能保障的算法,并且可以在理论和实践两方面学习。我们概括了Kumar等人(NeurIPS'18)在参考文件中提出的算法框架,并介绍了加权工作和非相关机器的第一个学习强化排程结果。我们在实验中展示了与先前建议的单机算法相比是否可行和高性。