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 $\Omega (n)$ lower bound shows that no deterministic si…