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

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 P m|prec, p j = 1|C max . Settling the complexity of P m|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 nm) time. This algorithm is subexponential when m = o(n). In the regime of m = Θ(n) we show an algorithm that runs in O(1.997 n ) time. Before our work, even for m = 3 machines there were no algorithms known that run in O((2 -ε) n ) time for some ε > 0. 1