Paper Info
Title
Scheduling with Predictions and the Price of Misprediction.
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.
Year
DOI
Venue
2019
10.4230/LIPIcs.ITCS.2020.14
arXiv: Data Structures and Algorithms
Field
DocType
Volume
Discrete mathematics,Scheduling (computing),Operations research,Shortest job next,Queueing theory,Job scheduler,Service time,Mathematics
Journal
abs/1902.00732
Citations 
PageRank 
References 
0
0.34
15
Authors
1
Name
Order
Citations
PageRank
Michael Mitzenmacher17386730.89