Online Scheduling with Predictions

Abstract

Online scheduling is the process of allocating resources to tasks to achieve objectives with uncertain information about future conditions or task characteristics. This thesis presents a new online scheduling framework named online scheduling with predictions. The framework uses predictions about unknowns to manage uncertainty in decision-making. It considers that the predictions may be imperfect and include errors, surpassing the traditional assumptions of either complete information in online clairvoyant scheduling or zero information in online non-clairvoyant scheduling. The goal is to create algorithms with predictions that perform better with quality predictions while having bounded performance with poor predictions. The framework includes metrics such as consistency, robustness, and smoothness to evaluate algorithm performance. We prove the fundamental theorems that give tight lower bounds for these metrics. We apply the framework to central scheduling problems and cyber-physical system applications, including minimizing makespan in uniform machine scheduling with job size predictions, minimizing mean response time in single and parallel identical machine scheduling with job size predictions, and maximizing energy output in pulsed power load scheduling with normal load predictions. Analysis and simulations show that this framework outperforms state-of-the-art methods by leveraging predictions.