一种用于具有优先级约束的单件作业完工时间调度的亚指数时间算法

《ACM Transactions on Algorithms》：A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints

调度问题中，当机器数m≥3时，首次提出次指数时间精确算法，通过分解策略将问题转化为可递归求解的子问题，时间复杂度为2^O(√n log n)或(1+n/m)^O(√nm)，并证明该问题比NP完全问题更易处理。

　　

摘要AI总结

摘要

摘要

在一个经典的调度问题中，我们有一组单位长度的作业，这些作业受到优先级约束。目标是找到一种在多台相同机器上安排这些作业的方案，以最小化总完成时间。用标准的三字段符号表示为：

对于两台机器的情况，这个问题可以在多项式时间内解决。确定任何常数m≥3时的复杂度是该领域长期存在的未解问题，Lenstra和Rinnooy Kan在20世纪70年代末提出了这个问题，并在Garey和Johnson的教科书中进行了重点讨论。从那时起，这个问题已经被彻底研究，但只有在特殊情况下或放宽条件后才能找到非平凡的解决方案。例如，尽管在精确设置下问题可能是多项式可解的，但仅存在近似方案就被广泛认为是一个重要的未解问题（参见Bansal的综述[MAPS 2017]），然而到目前为止，只知道超多项式近似算法。

在本文中，我们首次在精确复杂度方面取得了进展。我们提出了一种算法，其运行时间为O(m^(2√n log n))，其中m=n且n≥1。在我们的工作之前，Held和Karp在1961年只知道一个O(2^n)时间的精确算法。

我们引入了“适当分解”的概念。利用这种分解，我们的方法可以分为三个部分：在“分支”部分，我们根据适当分解生成可能的子调度；在“重构”部分，我们根据部分答案计算调度。有趣的是，尽管分支的深度可能是线性的，但通过“记忆化”技术，我们可以证明不同子问题的总数是有界的。

AI总结

AI生成的总结（实验性）

此总结是使用自动化工具生成的，不是由文章作者编写或审阅的。它旨在帮助发现、帮助读者评估相关性，并帮助来自相关研究领域的读者理解本文的工作。它旨在补充作者提供的摘要，后者仍然是论文的主要总结。完整文章仍然是权威版本。点击这里了解更多。

点击这里对总结的准确性、清晰度和实用性进行评论。这将有助于改进和未来生成的版本。

AI生成的总结

该总结是由基于已发表文章文本的自动化系统生成的。

生成日期：2026年1月3日。

这项研究解决了在多台相同机器上分配具有优先级约束的单位长度作业时最小化总完成时间的基本调度问题。这个经典问题被表示为Pm|prec, pj=1|Cmax，自20世纪70年代Lenstra和Rinnooy Kan提出这个问题以来，它基本上仍未解决，即使对于只有三台机器的情况也是如此。虽然当机器数量可变时问题被认为是NP难的，并且可以在多项式时间内解决，但对于三台或更多机器的情况，其复杂度仍然是一个未解问题。

以前的方法取得了各种专门的结果，但未能克服指数时间界限。参数化算法实现了n^O(mh)的运行时间，其中h是最长链的长度，但对于一般情况这仍然是指数级的。近似方案在亚指数时间内提供了接近最优的解决方案，但近似本身并不能保证精确解。对于精确计算，已知最好的算法基于作业子集的动态规划，运行时间为2^O(n)时间。

本文提出了第一个亚指数时间的精确算法。关键创新在于对最优调度进行了适当的分解，这扩展了Dolev和Warmuth之前的工作。这种分解保证了任何最优调度都可以表示为具有特殊结构属性的交替时间段和部分子调度。重要的是，每个部分中的作业完全由最多m个作业的两个反链决定，从而实现了高效的递归分解。

该算法结合了三种主要技术：分支阶段尝试所有可能的分解时间段对，并递归处理子问题；记忆化阶段观察到具有少量汇点作业的子问题相对较少，通过带有查找表的动态规划利用了这一点；重构阶段使用动态规划高效地组合子问题的解决方案。

分析证明，当m=o(n)时，算法运行时间为2^O(√n log n)，实现了亚指数复杂度。更一般地，运行时间为(1+n/m)^O(√nm)。对于机器数量不受限制的情况，一个次要结果表明问题可以在O(1.997^n)时间内解决，打破了适用于许多NP完全问题的O*(2^n)界限。

本文还提供了一个条件性下界，表明2^o(n)时间的算法将与关于最密集κ-子图问题的一个合理难度假设相矛盾。虽然这些结果并不能最终确定问题属于P类还是NP难类，但它们表明这个问题比以前认为的要简单得多，将其明确地置于亚指数复杂度范围内，而不是完全指数复杂度范围内。

此内容由AI生成。了解更多