文章基本信息

标题：Scheduling with Predictions and the Price of Misprediction
本地全文：下载
作者：Michael Mitzenmacher
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-18
DOI：10.4230/LIPIcs.ITCS.2020.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In many traditional job scheduling settings, it is assumed that one knows the time it will take for a job to complete service. In such cases, strategies such as shortest job first can be used to improve performance in terms of measures such as the average time a job waits in the system. We consider the setting where the service time is not known, but is predicted by for example a machine learning algorithm. Our main result is the derivation, under natural assumptions, of formulae for the performance of several strategies for queueing systems that use predictions for service times in order to schedule jobs. As part of our analysis, we suggest the framework of the "price of misprediction," which offers a measure of the cost of using predicted information.
关键词：Queues; shortest remaining processing time; algorithms with predictions; scheduling