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 with precedence constraints, and the goal is to find a schedule of these jobs on \(m\) identical machines that minimizes the makespan. In standard 3-field notation, it is denoted as \(Pm|\text{prec},p_{j}=1|C_{\max}\) . For \(m=2\) machines, the problem can be solved in polynomial time. Settling the complexity for any constant \(m\geq 3\) is a longstanding open question in the field, asked by Lenstra and Rinnooy Kan [OR 1978] in the late 70s and prominently featured in the textbook of Garey and Johnson. Since then, the problem has been thoroughly investigated, but nontrivial solutions had been found only in special cases or relaxed settings. For example, despite the possibility of the problem being polynomially solvable in the exact setting, just the existence of an approximation-scheme is widely regarded as a major open problem (see the survey of Bansal [MAPS 2017]), but so far, only superpolynomial approximations are known. In this paper, we make the first progress on the exact complexity of \(Pm|\text{prec},p_{j}=1|C_{\max}\) . We present an algorithm that runs in \(2^{\mathcal{O}(\sqrt{n}\log{n})}\) time for \(m=\mathcal{O}(1)\) . Before our work, only a \(2^{\mathcal{O}(n)}\) time exact algorithm was known by Held and Karp [ACM 1961]. We introduce a notion of proper decomposition of the schedule. With this decomposition in hand, our approach can be presented in three parts. In the branch part, we branch on possible subschedules generated by proper decomposition. In the reconstruct part, we compute the schedule based on the partial answer. Interestingly, despite the fact that the depth of the branching may be linear, by memoization we can show that the total number of different subproblems is bounded by \(2^{\mathcal{O}(\sqrt{n}\log{n})}\) .