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.

翻译：我们考虑的是在单一机器上在线排期以尽量减少加权流时的问题。 这个问题的现有算法( STOC '01, SPA'03, FOSS'18) 都要求准确了解每项工作的处理时间。 这一假设至关重要, 因为即使对处理时间略为扰动, 也会导致多面性竞争比率。 但是, 在现实生活中,这种假设很少能维持在现实生活中。 在本文中, 我们提出了第一种加权流时的算法, 它不需要确切了解工作处理时间。 具体地说, 我们引入了与预测处理时间( SPPT) 挂钩的算法问题( SPPT), 即对每项工作的处理时间进行预测, 而不是对实际处理时间进行预测。 对于预测与实际处理时间之间的持续因素扭曲, 我们的算法匹配了所有已知的加权流时的最佳竞争界限 -- 即$O( log P)、 O( log D) $ 和 $O( log W) $( $) $( log) $, 其中, $P, D, W$是我们处理时间、 w$ 是优度的最大比率、 和重量 。