Non-Clairvoyant Scheduling with Predictions
Non-Clairvoyant Scheduling with Predictions
复制标题
带预测的非透视调度
DOI：
10.1145/3409964.3461790
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Purohit, Manish
中科院分区：
文献类型：
--
作者：
Im, Sungjin;Kumar, Ravi;Montazer Qaem, Mahshid;Purohit, Manish
在单机无透视调度问题中，目标是最小化先验加工时间未知的作业的总完工时间。我们重新讨论了这个研究得很好的问题，并考虑了如何有效地使用(可能是错误的)处理时间预测的问题。我们从零开始研究这个问题，首先问什么是好的预测；然后我们提出了一种新的预测质量衡量标准，并在此标准下设计了具有强大保证的调度算法。我们基于自然期望值推导预测误差度量的方法也可以应用于其他在线问题。
In the single-machinenon-clairvoyantscheduling problem, the goal is to minimize the total completion time of jobs whose processing times areunknowna priori. We revisit this well-studied problem and consider the question of how to effectively use (possibly erroneous) predictions of the processing times. We study this question from ground zero by first asking what constitutes a good prediction; we then propose a new measure to gauge prediction quality and design scheduling algorithms with strong guarantees under this measure. Our approach to derive a prediction error measure based on natural desiderata could find applications for other online problems.
登录
查看更多内容
DOI：
10.4230/lipics.esa.2021.59
发表时间：
2020-11
期刊：
ArXiv
影响因子：
--
作者：
Thomas Lavastida;Benjamin Moseley;R. Ravi;Chenyang Xu
通讯作者：
Thomas Lavastida;Benjamin Moseley;R. Ravi;Chenyang Xu
DOI：
--
发表时间：
2020-06
期刊：
ArXiv
影响因子：
--
作者：
Kapil Vaidya;Eric R. Knorr;Tim Kraska;M. Mitzenmacher
通讯作者：
Kapil Vaidya;Eric R. Knorr;Tim Kraska;M. Mitzenmacher
DOI：
10.1109/works.2014.12
发表时间：
2014-11
期刊：
2014 9th Workshop on Workflows in Support of Large-Scale Science
影响因子：
--
作者：
Ilia Pietri;G. Juve;E. Deelman;R. Sakellariou
通讯作者：
Ilia Pietri;G. Juve;E. Deelman;R. Sakellariou
DOI：
10.1016/j.disopt.2023.100778
发表时间：
2020-06
期刊：
ArXiv
影响因子：
--
作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev
通讯作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev