Papers for

parallel system schedulers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Non-clairvoyant scheduling on trees is inherently hard to optimize

Non-Clairvoyant Scheduling is Hard Even for Trees

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.

Wed 7 OctData Structures and Algorithms
The gist
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.
Open → 2610.11006v1