# Flow Time Scheduling with Uncertain Processing Time

arXiv: https://arxiv.org/abs/2103.05604 · HTML: https://mlsanity.com/paper/2103.05604/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2021.

## Built on by (most cited first, 29 of 29)

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)
- [Online Dynamic Acknowledgement with Learned Predictions](https://mlsanity.com/paper/2305.18227/) (2023)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)
- [Scheduling with Predictions](https://mlsanity.com/paper/2212.10433/) (2022)
- [SkipPredict: When to Invest in Predictions for Scheduling](https://mlsanity.com/paper/2402.03564/) (2024)
- [Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams](https://mlsanity.com/paper/2406.16270/) (2024)
- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Capacity Planning and Scheduling for Jobs with Uncertainty in Resource Usage and Duration](https://mlsanity.com/paper/2507.01225/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Learning-Augmented Online Scheduling with Parsimonious Preemption](https://mlsanity.com/paper/2605.23255/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)
- [Robust Non-Clairvoyant Scheduling with Classification Models](https://mlsanity.com/paper/2610.01343/) (2026)

## Abstract (arXiv)

We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC '01, SODA '03, FOCS '18) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time -- namely O(log P), O(log D) and O(log W), where P,D,W are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully.