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.

arXiv comment14 pages, submitted; version 2 has updated references, some corrections

References in corpus (3)

• SATzilla: Portfolio-based Algorithm Selection for SAT
• Improving Online Algorithms via ML Predictions
• A Model for Learned Bloom Filters, and Optimizing by Sandwiching

Cited by in corpus (7)

• The Primal-Dual method for Learning Augmented Algorithms
• Customizing ML Predictions for Online Algorithms
• The Supermarket Model with Known and Predicted Service Times
• Contextual Pandora's Box
• Optimizing Redundancy Levels in Master-Worker Compute Clusters for Straggler Mitigation
• SEH: Size Estimate Hedging for Single-Server Queues
• Can Q-Learning be Improved with Advice?