Non-Clairvoyant Scheduling is Hard Even for Trees

Kunal Agrawal, Owen Druzgal, Milind Prabhu +1

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 vert…