Help Privacy Policy Disclaimer
  Advanced SearchBrowse





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


Węgrzycki,  Karol       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available

Nederlof, J., Swennenhuis, C. M. F., & Węgrzycki, K. (2022). Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995n) time. Retrieved from https://arxiv.org/abs/2208.02664.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1F35-7
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|\text{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^\ast(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.