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

preprint2022arXivOpen access

Abstract

In a classical scheduling problem, we are given a set of nn jobs of unit length along with precedence constraints and the goal is to find a schedule of these jobs on mm 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⁡P|\text{prec}, p_j=1|C_{\max}. We present an algorithm for this problem that runs in O(1.995n)O(1.995^n) time. Before our work, even for m=3m=3 machines the best known algorithms ran in O∗(2n)O^\ast(2^n) time. In contrast, our algorithm works when the number of machines mm 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.