recursion - 所有的调度问题都是 NP-Hard 吗？

Question

我知道那里有一些调度问题是 NP-hard/NP-complete ......但是，没有一个是这样说明的，以表明这种情况也是 NP。

如果您有一组任务受限于 startAfter、startBy 和 duration 都试图使用 单一资源 ...您能否解决计划或确定如果不进行详尽搜索就无法解决？

如果答案是“对不起， friend ，但这是 NP 完全的”，那么最好的启发式方法是什么？有没有办法减少 a) 解决计划和 b) 确定无法解决的时间日程。

我已经(在序言中)通过实现“最小窗口优先”启发式的递归实现了基本的冲突解决目标。这实际上很快就能找到解决方案，但在寻找无效时间表方面却异常缓慢。有没有办法克服这个问题？

耶复合问题!

Answer 1

中大多数调度问题中最难的部分现实生活正在掌握可靠性和完整的约束集。如果我们以创建大学时间表为例:

A教授早上起不来，他参加了很多委员会，但没有人会告诉时间表办公室这种约束

部门 1 需要在学期开始前的时间表，但是使用相同房间的部门 2 不愿意决定将要运行的类(class)，直到所有学生都到达

等

然后你需要一个可以应对变化的调度系统，所以当一个约束在最后一分钟发生变化时，你不必更改完整的时间表。

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

见 http://www.asap.cs.nott.ac.uk/watt/resources/university.html获取可以帮助您入门的论文列表；在调度软件方面还有很多 PHD 需要。