是所有调度问题NP-很难吗？

题

我知道有一些日程安排问题，那里是NP-硬/NP-完全...然而，他们都表示在这样一种方式来显示这种情况也是NP。

如果你有一定任务的约束到 startAfter, startBy, ， 持续时间 所有尝试使用 单资源 ...你可以解决一个时间表或标识，它无法解决而没有一个详尽的搜索？

如果答案是 "对不起伙计，但是这是NP-完整的" 什么是最好的启发(s?) 使用以及是否有办法减少所需的时间一)解决计划和b)确定一个无法解决的时间表。

我已经实施(在序言)的一个基本解决冲突的目标，通过递归于实现一个"最小的窗口中的第一"的试探。这实际上找到解决方案相当快，但是非常缓慢，在寻找无效的时间表。有没有办法克服这个吗？

耶化合物的问题！

解决方案

最难的部分数调度中的问题 现实生活 被抓住的一个可靠性和完整套的约束。如果我们把例如建立一个大学时间表：

然后你需要一个计划系统，该系统能应付变化，因此当一个制约因素是改变了在最后一分钟你不必改变，完成时间表。

所有上述的通常是忽视在研究论文的有关调度系统。为NP完整性的一个给定日程安排问题， 现实生活中，你不在乎 因为即使它不是NP完成你是不太可能甚至能够确定什么是"最好的解决方案"，使不够好是不够好。

看看 http://www.asap.cs.nott.ac.uk/watt/resources/university.html 列表的文件，可以帮助你开始；仍有许多博士在调度软件。

其他提示

有良好往往近似算法获得像调度NP硬/完整的优化问题。你可能会通过脱脂艾哈迈德·阿布萨菲亚的课程笔记上近似算法调度或各种论文的。

在某种意义上，所有的公共密钥加密与像保理“少难”问题，部分原因是NP难问题提供了过多的情况下，容易做。这是相同的NP完全性，使他们“道德硬”，这也给了他们太多轻松的问题，这往往落在约束优化的一些误差范围内。

有是硬度的近似的更深的理论讨论的近似算法虽然限制。

您可以使用动态编程来解决这些事情。贪心算法也浮现在脑海中。调度理论既深又漂亮，可是这两个我觉得可以解决大部分的我所面临的问题。也许我很幸运。

你是什么意思与startBy？

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

下面是一个不是。

附表一组作业I = 1,2，...，n中的单台机器上，每个取时间t（ⅰ）使平均等待时间被最小化。

解决方案：排序增加吨的顺序（i）中。为O（n log n）的

好名单这里

考虑调度问题，即在类，P：

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

排序完成时间。

选择此有序列表的第一个N元素来发现你可以在给定的时间安排的活动的最大金额。

在工作时通过列表，一旦你达到某活动结束这段时间后

所有活动必须在下午5点结束，以及在这种情况下，停止：

您可以添加类似的警告

许可以下： CC-BY-SA 和归因