Non-Clairvoyant Scheduling is Hard Even for Trees
It is shown that First-In-First-Out (FIFO) has competitive ratio $\Omega(\log m)$ even when every job is an out-tree, and a lower bound is proved of $\Omega(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule.