Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995^n) time

08/04/2022
by   Jesper Nederlof, et al.
0

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, 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^∗(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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset