Non-clairvoyant scheduling on trees is inherently hard to optimize
Non-Clairvoyant Scheduling is Hard Even for Trees
Data Structures and Algorithms
Summary
Scheduling tasks that depend on each other can be tricky, especially when you don't know the whole task ahead of time. The authors studied this problem where tasks arrive as tree-like structures with steps that must happen in order. They found that no method can always schedule these tasks efficiently without knowing the full details beforehand, even in simple tree cases. They also designed an algorithm that performs as well as any possible approach can in the worst cases. This means some scheduling problems are fundamentally difficult without extra knowledge.
What this means in practice
- •For parallel system schedulers: Understand fundamental limits when scheduling complex dependent jobs without full knowledge, guiding design choices for real-world task schedulers.
- •For cloud resource managers: Identify when non-clairvoyant scheduling can lead to poor performance under dependency constraints, informing resource allocation policies.
A theory result. No direct application yet.
Authors
Kunal Agrawal, Owen Druzgal, Milind Prabhu, Jinhao Zhao
Abstract
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 a job arrives, and each subjob is revealed only when it becomes ready. Agrawal, Moseley, Newman, and Pruhs (SPAA 2024) showed that First-In-First-Out (FIFO) has competitive ratio $Ω(\log m)$ even when every job is an out-tree. They also proved that FIFO is $O(\log m)$-competitive in several natural settings and asked whether this guarantee extends to general instances. More broadly, they asked whether any non-clairvoyant algorithm can be $O(1)$-competitive. We answer both questions in the negative by proving a lower bound of $Ω(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule. In particular, every non-clairvoyant algorithm has competitive ratio $Ω(m)$ on some instance with $\mathrm{OPT} \ge m$. The lower bound holds even when every job is an out-forest. We complement these lower bounds with an asymptotically optimal non-clairvoyant algorithm. FIFO is $O(m)$-competitive, but can have competitive ratio $Ω(m)$ even when $\mathrm{OPT}=O(1)$. For instances with small $\mathrm{OPT}$, we design a Small-Frontier-First algorithm that is $O(\mathrm{OPT})$-competitive. Combining the two algorithms yields an $O(\min\{m,\mathrm{OPT}\})$-competitive non-clairvoyant algorithm.