Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms

This paper studies the classical online scheduling problem of minimizing total flow time for n jobs on m identical machines. Prior work often cites the $Ω(n)$ lower bound for non-preemptive algorithms to argue for the necessity of preemption or resource augmentation, which shows the trivial $O(n)$-competitive greedy algorithm is tight. However, this lower bound applies only to deterministic algorithms in the single-machine case, leaving several fundamental questions unanswered. Can randomness help in the non-preemptive setting, and what is the optimal online deterministic algorithm when m ≥ 2? We resolve both questions. We present a polynomial-time randomized algorithm with competitive ratio Θ(√n/m) and prove a matching randomized lower bound, settling the randomized non-preemptive setting for every m. This also improves the best-known offline approximation ratio from O(√n/mlog(n/m)) to O(√n/m). On the deterministic side, we present a non-preemptive algorithm with competitive ratio O(n/m²+√n/mlog m) and prove a nearly matching lower bound. Our framework also extends to the kill-and-restart model, where we reveal a sharp transition of deterministic algorithms: we design an asymptotically optimal algorithm with the competitive ratio O(√n/m) for m≥ 2, yet establish a strong Ω(n/log n) lower bound for $m=1$. Moreover, we show that randomization provides no further advantage, as the lower bound coincides with that of the non-preemptive setting. While our main results assume prior knowledge of n, we also investigate the setting where n is unknown. We show kill-and-restart is powerful enough to break the $O(n)$ barrier for m ≥ 2 even without knowing n. Conversely, we prove randomization alone is insufficient, as no algorithm can achieve an $o(n)$ competitive ratio in this setting.