The Cost of Accurate Predictions in Learning-Augmented Scheduling

This paper considers non-clairvoyant scheduling with predictions to minimize total completion time, with a focus on the often-overlooked impact of prediction costs. Prior works assume ideal settings where predictions are cost-free at inference, but quality predictions require time, which is critical when optimizing a time-sensitive metric. We investigate the trade-off between prediction accuracy and inference time in learning-augmented scheduling by simulating datasets with models of varying accuracy and inference times. Using Gaussian Processes to model this relationship, we find that highly accurate predictions with long inference times are suboptimal, whereas moderately accurate models with fast inference times yield empirically optimal performance.