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

Yutong Geng, Enze Sun, Zonghan Yang +1

This paper studies the online scheduling problem of minimizing total flow time for $n$ jobs on $m$ identical machines. A classical $\hat{I}\text{c◯}(n)$ lower bound shows that no deterministic s…