我知道那里有些NP-hard/NP-complete的调度问题......但是，他们中没有一个用这种方式表示这种情况也是NP。是否所有调度问题NP-Hard？
如果你有一组约束为startAfter，startBy任务，并时间都试图用一个单个资源 ...你可以解决的时间表或者确定它不能得到解决没有详尽的搜索？
如果答案是“sorry pal，但这是NP-complete”什么是最好的启发式（s？）使用，并且有办法减少花费的时间a）解决计划和b）确定一个无法解决的时间表。
我已经通过实现“最小窗口优先”启发式的递归实现（在序言中）基本的冲突解决目标。这实际上很快找到解决方案，但发现无效的时间表非常缓慢。有没有办法解决这个问题？
Yay for compound questions！
大多数调度问题中最难的部分正在掌握可靠性和完整的约束条件。如果我们把创建一所大学的时间表，例如：早上
那么你需要一个可以应付变化的时间表系统，所以当一个约束在最后一刻发生变化时，您不必更改完整的时间表。
上述所有内容在有关调度系统的研究论文中通常都会被忽略。对于给定调度问题的NP完整性，在现实生活中，你并不关心，因为即使它不是NP完整的，你也不可能定义什么是“最佳解决方案”，这么好就是好足够。
查看http://www.asap.cs.nott.ac.uk/watt/resources/university.html了解可能帮助您入门的论文列表;调度软件中仍然有许多PHD。
伟大的链接！ .. 谢谢。像这样的链接几乎属于http://lambda-the-ultimate.org – 2010-01-29 17:01:59
市场领先的大学调度系统仍然在列表中，并且使用lambda很多。 – 2010-01-29 17:09:18
“”上述所有内容在有关调度系统的研究论文中通常都被忽略了“” 就像旁注：那不是真的。至少在最新的研究中，他们试图让它更真实。例如。请参阅2007年国际时间表竞赛赛道的要求。 – Karussell 2010-01-29 22:19:23
您可以使用动态编程来解决其中的一些问题。贪婪的算法也浮现在脑海。调度理论既深刻又美观，但我发现的那两个将解决我所面临的大多数问题。也许我很幸运。
贪婪算法不会总是产生一个结果时，虽然存在，是否正确？就我的目的而言，如果存在安排所有任务的解决方案，我必须找到它。 “关闭”的解决方案将无法正常工作=/ 我会在interwebz上寻找一些动态编程调度算法...谢谢！ – 2010-01-29 14:25:18
没问题。但是，从技术上讲，你只能这么靠近。一个好的启发式比没有好，有时甚至可以。调度是优化的基础，是一个非常深入的领域。从简单开始，继续前进。 – wheaties 2010-01-29 14:33:08
最小的窗口第一次真的帮助很多找到解决方案......我需要弄清楚如何修剪我的搜索空间，以便“错误”返回来得快。 – 2010-01-29 14:36:10
startBy是什么意思？
随着startAfter和如果只有一个资源，那么一个快速的解决方案可能是使用topological sorting。示例算法以线性时间运行，但如果图形包含循环，则不包括错误情况。
Java中的一些源代码可以从我的timefinder项目中获得： https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk/timefinder-algo/src/main/java/de/timefinder/algo/graph/ – Karussell 2010-01-29 16:22:03
startBy和startAfter之后引用任务必须在其中开始的窗口...即任务a必须在2:00之后开始，并在2:30之后开始30分钟的“机会窗口”。感谢您的链接..我会研究它...现在：-D – 2010-01-29 16:39:39
乍一看，它似乎只考虑到任务的顺序，而不考虑该任务的限制......不过......创建可能的“有序”列表并在启动到O（n^n）完整扫描之前检查这些解决方案的有效性可能不是一个坏主意。 – 2010-01-29 16:51:13
伟大的列表...看起来像我最小的WindowFirst是一个与EarliestDueDate紧密相关的 – 2010-02-23 03:19:15
经常有像调度NP硬/完整的优化问题好approximation algorithms。您可以浏览Ahmed Abu Safia的课程笔记Approximation Algorithms for scheduling或各种papers。
从某种意义上说，所有公钥密码术都是用“较难”的问题完成的，比如因子分解，部分原因是因为NP难题提供了太多简单的情况。这种NP完全性使得它们在“道德上很难”，这也给它们带来了太多简单的问题，而这些问题往往属于最优化的误差范围。
hardness of approximation有一个更深入的理论讨论了近似算法的局限性。
考虑调度问题，那就是在P类：
输入：其中包括开始时间和结束时间的活动列表。
按结束时间排序。
选择此排序列表的前N个元素以查找您可以在给定时间内排定的最大活动量。
您可以添加如下警告：所有活动必须在下午5点结束，在这种情况下，当您处理列表时，停止一次到达此时间结束的活动。
你认为你会为这个问题添加更多约束吗？如果是这样，它看起来像一个时间表问题，这是'通常'通过约束编程解决 http://en.wikipedia.org/wiki/Constraint_programming 甚至线性编程 http://en.wikipedia.org/ wiki/Linear_programming 看一看名为unitime.org（约束编程）和ilog的约束求解器（非常昂贵，但非常快）的开源项目。 – Karussell 2010-01-29 22:13:32