2022/08/04 by Jesper Nederlof, Nederlof, Jesper, Céline M. F. Swennenhuis +3
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Search Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2208.02664
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|prec, pj=1|Cmax. We present an algorithm for this problem that runs in O(1.995n) time. Before our work, even for m=3 machines the best known algorithms ran in O^∗(2n) 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.