所有的调度问题都是NP难问题吗？

Question

我知道有一些关于任务调度的问题是NP-hard/NP-complete的...然而，它们没有被陈述得足够清楚以展示该情况也属于NP。

如果您有一组受到“startAfter”、“startBy”和“duration”限制的任务，并且它们都试图使用单个资源...你能否解决一个时间表或确定需要进行详尽搜索才能解决它？

如果答案是"对不起，但这是NP-complete"，最好的启发式算法是什么？有没有方法可以缩短a)解决时间表和b)识别无法解决的时间表所需的时间。

我已经在Prolog中实现了一个基本的冲突解决目标，通过递归实现了“最小窗口优先”启发式算法。它实际上可以快速找到解决方案，但在查找无效时间表方面非常慢。有没有办法克服这个问题？

好耶，这是复合问题！

- Reed Debaets

---

你认为会给这个问题增加更多的限制条件吗？如果是这样，它看起来像是一个时间表问题，通常可以通过约束编程来解决。http://en.wikipedia.org/wiki/Constraint_programming甚至可以使用线性规划http://en.wikipedia.org/wiki/Linear_programming看一下名为unitime.org（约束编程）的开源项目和ilog的约束求解器（非常昂贵，但非常快速）。 - Karussell

Answer 1

大多数实际生活中的调度问题最难的部分在于获取可靠和完整的约束集。以创建大学课程表为例：

• 教授A不会早上起床，他在许多委员会中任职，但没有人会告诉课程表办公室这种约束条件
• 系1需要在学期开始前得到课程表，然而，使用相同教室的系2不愿意在所有学生到达后决定将开设哪些课程。
• 等等

因此，您需要一个可以应对变化的调度系统，这样当一个约束条件在最后一刻更改时，您就不必更改整个课程表。

研究论文通常忽略上述所有内容。至于给定调度问题的NP完备性，在现实生活中你并不关心，因为即使它不是NP完全的，你也不太可能定义出什么是“最佳解决方案”，所以“好了就行”。

参见http://www.asap.cs.nott.ac.uk/watt/resources/university.html以获取可能有助于启动的论文列表；在调度软件领域仍有许多博士学位可供获得。

- Ian Ringrose

---

太棒了的链接！谢谢。像那样的链接几乎属于http://lambda-the-ultimate.org。 - Reed Debaets

市场领先的大学排课系统仍然使用列表编写，并且大量使用lambda函数。 - Ian Ringrose

“通常在有关调度系统的研究论文中，上述所有内容都被忽略了。”顺便说一句：这并不是真的。至少在最新的研究中，他们试图使其更贴近实际生活。例如，请参阅2007年国际时间表竞赛轨道的要求。” - Karussell

好的观点。此外，对于小N而言，NP完全问题是可以完美解决的，而且很多现实场景都涉及到小N。 - dsimcha

有趣的是，在我们的个人和职业生活中，我们都能在不确定性环境下隐式地解决动态调度问题，但实时计算研究社区几乎没有人认识到这一普遍的调度问题，更不用说解决了。当然，在实时计算之外，这个问题是众所周知的，并得到广泛的关注和解决。 - E. Douglas Jensen

Answer 2

您可以使用动态规划来解决其中一些问题。贪心算法也是一个不错的选择。调度理论既深刻又美丽，但我发现前两者已经能够解决我遇到的大部分问题了，或许我很幸运。

- wheaties

---

贪心算法并不总是能得到结果，即使存在一个解，对吗？对于我的目的，如果存在一种安排所有任务的解决方案，我必须找到它。"接近"的解决方案行不通 =/我会在互联网上寻找一些动态规划调度算法...谢谢！ - Reed Debaets

没问题。然而，从技术上讲，你只能接近一定程度。一个好的启发式方法总比没有好，有时也是你所能达到的最远距离。调度，它的根源在于优化，是一个非常深入的领域。从简单的开始，逐步提高。 - wheaties

最小化窗口首先帮助我们找到解决方案... 我需要找出如何修剪我的搜索空间，以便更快地返回“false”结果。 - Reed Debaets

Answer 3

通常，像调度这样的NP-hard / complete优化问题往往有良好的近似算法。您可以浏览Ahmed Abu Safia关于调度近似算法或各种论文的课程笔记。

从某种意义上说，所有公钥加密都是使用“不那么困难”的问题（例如部分因子分解），因为NP-hard问题提供了太多容易的情况。正是同样的NP完备性使它们“道德上困难”，也给它们带来了太多容易的问题，这些问题通常落在某些最优误差范围内。

虽然有近似难度理论探讨近似算法的局限性。

- Jeff Burdges

Answer 4

这里有一个与编程无关的例子。

对于一台机器，调度一组作业i=1,2...n，每个作业执行时间为t(i)，以便最小化平均等待时间。

解决方案：按t(i)升序排序。O(n log n)

好的列表在这里。

- Grembo

---

很棒的列表...看起来我的smallestWindowFirst与EarliestDueDate密切相关。 - Reed Debaets

Answer 5

“startBy”是什么意思？

如果使用“startAfter”，并且只有一个资源，则可以使用拓扑排序来快速解决。该示例算法运行时间为线性时间，但不包括图形包含循环的错误情况。

- Karussell

---

一些 Java 源代码可以从我的 timefinder 项目中获取： https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk/timefinder-algo/src/main/java/de/timefinder/algo/graph/ - Karussell

startBy和startAfter是指任务必须在...之间开始的时间窗口，即任务a必须在2:00之后开始，并在2:30之前开始，给予了30分钟的“机会窗口”。感谢提供链接，我现在会去查看它 :-D - Reed Debaets

乍一看，它似乎只考虑了任务的顺序，而没有考虑任务的约束条件...然而...在进行O(n^n)全面扫描之前，创建可能的“有序”列表并检查这些解决方案的有效性可能也不是一个坏主意。 - Reed Debaets

啊，好的。我以为你是指像事件A在事件B之后开始等关系。 - Karussell

Answer 6

考虑属于类P的调度问题：

输入：包括开始时间和结束时间的活动列表。

按结束时间排序。

选择此排序列表的前N个元素，以找到在给定时间内可以安排的最大活动量。

您可以添加诸如：所有活动必须在下午5点结束的附加条件，那么在处理列表时，一旦到达结束时间在此之后的活动，请停止。

- Logan Leland