A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints

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. Using the standard 3-field notation, it is known as $Pm|\text{prec},p_j=1|C_{\max }$. Settling the complexity of $Pm|\text{prec},p_j=1|C_{\max }$ even for $m=3$ machines is the last open problem from the book of Garey and Johnson [GJ79] for which both upper and lower bounds on the worst-case running times of exact algorithms solving them remain essentially unchanged since the publication of [GJ79]. We present an algorithm for this problem that runs in $(1+\frac{n}{m}{)}^{\mathcal{O}(\sqrt{nm})}$ time. This algorithm is subexponential when $m=o(n)$. In the regime of $m=\Theta (n)$ we show an algorithm that runs in$\mathcal{O}(1.997^n)$ time. Before our work, even for $m=3$ machines there were no algorithms known that run in $\mathcal{O}((2-\epsilon {)}^n)$ time for some $\epsilon >0$.