论文标题
在$ O（1.995^n）$ time的限制优先限制的单位工作计划
Makespan Scheduling of Unit Jobs with Precedence Constraints in $O(1.995^n)$ time
论文作者
论文摘要
在经典的调度问题中，我们为我们提供了一组单位长度的$ n $作业以及优先限制，目标是在$ M $相同的机器上找到这些作业的时间表，以最大程度地减少Makepan。对于无限数量的机器而言，此问题众所周知是NP的NP。使用标准3场符号，它被称为$ p | \ text {prec}，p_j = 1 | c _ {\ max} $。 我们提出了此问题的算法，该算法以$ O（1.995^n）$时间运行。在我们工作之前，即使以$ M = 3 $机器，最著名的算法也以$ o^\ ast（2^n）$时间运行。相比之下，当机器数量$ m $无限时，我们的算法起作用。我们方法的关键要素是一种算法，其运行时仅在优先限制图的可比性图的顶点封面中仅是单个指数。这在很大程度上取决于Dolev和Warmuth（算法杂志1984）的经典结果的见解，用于没有长链的优先级图。
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.
