Flow time scheduling with uncertain processing time

DOI10.1145/3406325.3451023MaRDI QIDQ6065232zbMATH OpenOpenAlexFDO

Authors Yossi Azar, Stefano Leonardi, Noam Touitou

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.05604

zbMATH Keywords

onlineschedulingflow timepredictions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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(logP),O(logD)$ and $O(logW)$, 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.

Cited in

(12)

• Scheduling with speed predictions
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Online delay management on a single train line with predictions
• Canadian traveller problem with predictions
• Scheduling with speed predictions
• Online interval scheduling with predictions
• Online unit profit knapsack with predictions
• Online interval scheduling with predictions
• Online simple knapsack with bounded predictions
• Tighter bounds on non-clairvoyant parallel machine scheduling with prediction to minimize makespan
• Minimizing total completion time for flowshop scheduling problem with uncertain processing times
• Online time-windows TSP with predictions

This page was built for publication: Flow time scheduling with uncertain processing time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065232)