Preprint
Oct 2026
Non-Clairvoyant Scheduling is Hard Even for Trees
We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vertices are unit-time subjobs and whose edges specify precedence constraints. We consider non-clairvoyant algorithms: the DAG is not known when...
Kunal Agrawal, Owen Druzgal, M. Prabhu et al.
· 0 citations