License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.14
URN: urn:nbn:de:0030-drops-116996
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11699/
Go to the corresponding LIPIcs Volume Portal

Mitzenmacher, Michael

Scheduling with Predictions and the Price of Misprediction

pdf-format:
LIPIcs-ITCS-2020-14.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{mitzenmacher:LIPIcs:2020:11699,
  author =	{Michael Mitzenmacher},
  title =	{{Scheduling with Predictions and the Price of Misprediction}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11699},
  URN =		{urn:nbn:de:0030-drops-116996},
  doi =		{10.4230/LIPIcs.ITCS.2020.14},
  annote =	{Keywords: Queues, shortest remaining processing time, algorithms with predictions, scheduling}
}

Keywords: Queues, shortest remaining processing time, algorithms with predictions, scheduling
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI