2024 Theses Doctoral

Scheduling and Routing under Uncertainty with Predictions

Wei, Hao-Ting

Uncertainty surrounds us daily, indicating the need for effective decision-making strategies. In recent years, the large amount of available data has accelerated the development of novel methods for decision-making and optimization. This thesis studies this inquiry, centering on a framework that employs predictions to enhance decision-making in various optimization problems.

We investigate scheduling and routing problems, which are fundamental in the field of sequential decision-making and optimization, within the framework of algorithms with predictions. Our goal is to improve performance by integrating predictions of unknown input parameters. The central question is: “Can we design algorithms that use predictions to enhance performance when the prediction is accurate while still maintaining worst-case guarantees, even when the predictions are inaccurate?”

Through theoretical and experimental analyses, we demonstrate that by incorporating appropriate predictions of unknown input parameters, we design algorithms to outperform existing results when predictions are accurate while maintaining worst-case guarantees even when the predictions are significantly erroneous.