是所有调度问题NP-很难吗?
-
23-09-2019 - |
题
我知道有一些日程安排问题,那里是NP-硬/NP-完全...然而,他们都表示在这样一种方式来显示这种情况也是NP。
如果你有一定任务的约束到 startAfter, startBy, , 持续时间 所有尝试使用 单资源 ...你可以解决一个时间表或标识,它无法解决而没有一个详尽的搜索?
如果答案是 "对不起伙计,但是这是NP-完整的" 什么是最好的启发(s?) 使用以及是否有办法减少所需的时间一)解决计划和b)确定一个无法解决的时间表。
我已经实施(在序言)的一个基本解决冲突的目标,通过递归于实现一个"最小的窗口中的第一"的试探。这实际上找到解决方案相当快,但是非常缓慢,在寻找无效的时间表。有没有办法克服这个吗?
耶化合物的问题!
解决方案
最难的部分数调度中的问题 现实生活 被抓住的一个可靠性和完整套的约束。如果我们把例如建立一个大学时间表:
- 教授一个不会得到了早上,他是在很多委员会,但没人会告诉我的时间表办公室有关这种约束
- 部门1的需求时间表的开始语,但是,部门2使用相同的房间是不愿意决定的课程,将可以运行,直到后所有的学生都到达
- 等等
然后你需要一个计划系统,该系统能应付变化,因此当一个制约因素是改变了在最后一分钟你不必改变,完成时间表。
所有上述的通常是忽视在研究论文的有关调度系统。为NP完整性的一个给定日程安排问题, 现实生活中,你不在乎 因为即使它不是NP完成你是不太可能甚至能够确定什么是"最好的解决方案",使不够好是不够好。
看看 http://www.asap.cs.nott.ac.uk/watt/resources/university.html 列表的文件,可以帮助你开始;仍有许多博士在调度软件。
其他提示
有良好往往近似算法获得像调度NP硬/完整的优化问题。你可能会通过脱脂艾哈迈德·阿布萨菲亚的课程笔记上近似算法调度一>或各种论文的。
在某种意义上,所有的公共密钥加密与像保理“少难”问题,部分原因是NP难问题提供了过多的情况下,容易做。这是相同的NP完全性,使他们“道德硬”,这也给了他们太多轻松的问题,这往往落在约束优化的一些误差范围内。
有是硬度的近似的更深的理论讨论的近似算法虽然限制。
您可以使用动态编程来解决这些事情。贪心算法也浮现在脑海中。调度理论既深又漂亮,可是这两个我觉得可以解决大部分的我所面临的问题。也许我很幸运。
你是什么意思与startBy?
使用startAfter并且如果只有一个资源,则一个快速的解决方案可以是使用拓扑排序。以线性时间的示例算法运行,但如果图形包含周期不包括错误的情况。
考虑调度问题,即在类,P:
输入:的其中包括开始时间和结束时间的活动列表
排序完成时间。
选择此有序列表的第一个N元素来发现你可以在给定的时间安排的活动的最大金额。
在工作时通过列表,一旦你达到某活动结束这段时间后所有活动必须在下午5点结束,以及在这种情况下,停止:您可以添加类似的警告