论文标题
非列表计划的排列预测
Permutation Predictions for Non-Clairvoyant Scheduling
论文作者
论文摘要
在非顾问计划中，任务是找到一个在线策略，以安排具有先验未知的处理要求的作业，以最大程度地减少总（加权）完成时间。我们在最近受欢迎的学习调节设置中重新审视了这个经过充分研究的问题，该设置集成了在线算法设计中的（不信任）预测。尽管以前的作品使用了对处理要求的预测，但我们提出了一个新的预测模型，该模型提供了相对的作业顺序，可以看作是预测算法动作而不是未知输入的一部分。我们表明，这些预测具有所需的属性，承认具有强大绩效保证的自然误差度量以及算法，并且在理论和实践中都可以学习。我们概括了Kumar等人在开创性论文中提出的算法框架。 （Neurips'18），并为加权工作和无关机器提供了第一个学习淘汰的调度结果。我们在经验实验中证明了与先前建议的单机算法相比的实用性和卓越性能。
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.
