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/m (n/m) ) to O (n/m). On the deterministic side, we present a non-preemptive algorithm with competitive ratio O (n/m^2+n/m 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/ 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.
Geng et al. (Wed,) studied this question.