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

Question

我知道有一些调度问题是NP-hard/NP-complete ...但是,没有一个以这样的方式表明这种情况也是NP.

如果您有一组约束到startAfter,startBy和duration的任务,所有尝试使用单个资源 ...您是否可以解决计划或确定无法在没有详尽搜索的情况下解决它？

如果答案是"对不起,但这是NP完全",那么最好的启发式(s？)是什么,并且有办法减少a)解决时间表和b)识别无法解决的时间时间表.

我通过实现"最小窗口优先"启发式的递归实现了(在prolog中)一个基本的冲突解决目标.这实际上很快找到了解决方案,但在查找无效的计划时非常慢.有办法克服这个问题吗？

耶和复合问题!

Answer 1

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

• A教授早上不上床,他在很多委员会工作,但没有人会告诉时间表办公室这种约束
• 部门1在学期开始时需要时间表,但是,使用相同房间的部门2不愿意决定将在所有学生到达之前运行的课程
• 等等

然后,您需要一个可以应对更改的计划系统,因此当最后一分钟更改一个约束时,您不必更改完整的时间表.

关于调度系统的研究论文通常会忽略以上所有内容.至于给定调度问题的NP完整性,在现实生活中你不关心,即使它不是NP完全你甚至不可能定义什么是"最佳解决方案",所以足够好就足够了.

请参阅http://www.asap.cs.nott.ac.uk/watt/resources/university.html以获取可能有助于您入门的论文列表; 调度软件中仍有许多PHD.

Answer 2

您可以使用动态规划来解决其中一些问题。贪婪算法也浮现在脑海中。调度理论既深刻又美丽，但我发现这两个理论可以解决我遇到的大部分问题。也许我很幸运。