A Little Clairvoyance Is All You Need

We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Shortest Remaining Processing Time (SRPT) algorithm is optimal (i.e., 1-competitive) when the job sizes are known upfront [Schrage, 1968]. But in the non-clairvoyant setting where job sizes are revealed only when the job finishes, no algorithm can be constant-competitive [Motwani, Phillips, and Torng, 1994]. We consider the $\varepsilon$-clairvoyant setting, where $\varepsilon \in[0,1]$, and each job’s processing time becomes known once its remaining processing time equals an $\varepsilon$ fraction of its processing time. This captures settings where the system user uses the initial $(1-\varepsilon)$ fraction of a job’s processing time to learn its true length, which it can then reveal to the algorithm. The model was proposed by Yingchareonthawornchai and Torng (2017), and it smoothly interpolates between the clairvoyant setting (when $\varepsilon=1$) and the non-clairvoyant setting (when $\varepsilon=0$). In a concrete sense, we are asking: how much knowledge is required to circumvent the hardness of this problem? We show that a little knowledge is enough, and that a constant competitive algorithm exists for every constant $\varepsilon\gt 0$. More precisely, for all $\varepsilon \in(0,1)$, we present a deterministic $\left\lceil\frac{1}{\varepsilon}\right\rceil$-competitive algorithm, which is optimal for deterministic algorithms. We also present a matching lower bound (up to a constant factor) for randomized algorithms. Our algorithm to achieve this bound is remarkably simple and applies the “optimism in the face of uncertainty” principle. For each job, we form an optimistic estimate of its length, based on the information revealed thus far and run SRPT on these optimistic estimates. The proof relies on maintaining a matching between the jobs in OPT’s queue and the algorithm’s queue, with small prefix expansion. We achieve this by carefully choosing a set of jobs to arrive earlier than their release times without changing the algorithm, and possibly helping the adversary. These early arrivals allow us to maintain structural properties inductively, giving us the tight guarantee.