Item

Abstract

In a classical scheduling problem, we are given a set of $n$ jobs of unit
length along with precedence constraints and the goal is to find a schedule of
these jobs on $m$ identical machines that minimizes the makespan. This problem
is well-known to be NP-hard for an unbounded number of machines. Using standard
3-field notation, it is known as $P|\text{prec}, p_j=1|C_{\max}$.
We present an algorithm for this problem that runs in $O(1.995^n)$ time.
Before our work, even for $m=3$ machines the best known algorithms ran in
$O^\ast(2^n)$ time. In contrast, our algorithm works when the number of
machines $m$ is unbounded. A crucial ingredient of our approach is an algorithm
with a runtime that is only single-exponential in the vertex cover of the
comparability graph of the precedence constraint graph. This heavily relies on
insights from a classical result by Dolev and Warmuth (Journal of Algorithms
1984) for precedence graphs without long chains.