所有的调度问题都是NP-Hard吗？
我知道有一些调度问题是 NP 难/NP 完全的……但是，没有一个问题以这样的方式表述来表明这种情况也是 NP。
如果您有一组任务限制在startAfter、startBy和持续时间，并且全部尝试使用单一资源 ...您能否解决一个时间表或确定如果不进行详尽的搜索就无法解决该问题？
如果答案是“对不起，朋友，但是这是 NP 完全的”，那么最好使用的启发式是什么？有没有办法减少 a) 解决时间表所需的时间b) 确定无法解决的时间表。
我（在序言中）通过递归实现了基本的冲突解决目标，该递归实现了“最小窗口优先”启发式。这实际上可以相当快地找到解决方案，但在找到无效时间表方面却异常缓慢。有办法克服这个问题吗？
复合问题耶！
I know there are some scheduling problems out there that are NP-hard/NP-complete ... however, none of them are stated in such a way to show this situation is also NP.
If you have a set of tasks constrained to a startAfter, startBy, and duration all trying to use a single resource ... can you resolve a schedule or identify that it cannot be resolved without an exhaustive search?
If the answer is "sorry pal, but this is NP-complete" what would be the best heuristic(s?) to use and are there ways to decrease the time it takes to a) resolve a schedule and b) to identify an unresolvable schedule.
I've implemented (in prolog) a basic conflict resolution goal through recursion that implements a "smallest window first" heuristic. This actually finds solutions rather quickly, but is exceptionally slow at finding invalid schedules. Is there a way to overcome this?
Yay for compound questions!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
现实生活中大多数调度问题最难的部分是掌握可靠性和完整的约束集。如果我们以创建大学时间表为例：
那么您需要一个可以应对变化的时间表系统，因此当一个约束发生变化时在最后一刻您不必更改完整的时间表。
在有关调度系统的研究论文中，上述所有内容通常都被忽略。至于给定调度问题的 NP 完整性，在现实生活中你并不关心，因为即使它不是 NP 完全的，你也不太可能定义什么是“最佳解决方案”，所以足够好就足够了。
请参阅http://www.asap.cs.nott.ac。 uk/watt/resources/university.html 获取可能帮助您入门的论文列表；调度软件方面还有很多PHD需要。
The hardest part of most scheduling problems in real life is getting hold of a reliability and complete set of constraints. If we take the example of creating a university timetable:
Then you need a schedule system that can cope with changes, so when one constraint is changed at the last minute you don’t have to change the complete timetable.
All of the above is normally ignored in research papers about scheduling systems. As to NP completeness of a given scheduling problem, in real life you don’t care as even if it is not NP complete you are unlikely to even be able to define what the “best solution” is, so good enough is good enough.
See http://www.asap.cs.nott.ac.uk/watt/resources/university.html for a list of papers that may help get you started; there are still many PHDs to be had in scheduling software.
您可以使用动态规划来解决其中一些问题。贪婪算法也浮现在脑海中。调度理论既深刻又美丽，但我发现这两个理论可以解决我遇到的大部分问题。也许我很幸运。
You can use dynamic programming to solve some of these things. Greedy algorithms also come to mind. Scheduling theory is both deep and beautiful but those two I find will solve most of the problems I've faced. Perhaps I've been lucky.
对于诸如调度之类的 NP 难/完全优化问题，通常有很好的近似算法。您可以浏览 Ahmed Abu Safia 关于调度近似算法 或各种论文。
从某种意义上说，所有公钥密码学都是通过“不太困难”的问题（例如分解）来完成的，部分原因是 NP 困难问题提供了太多简单的情况。同样的 NP 完备性使它们“道德上困难”，这也给它们带来了太多简单的问题，这些问题通常落在某些最优错误范围内。
有一个更深入的近似硬度理论，讨论了近似算法的局限性。
There are often good approximation algorithms for NP-hard/complete optimization problems like scheduling. You might skim the course notes by Ahmed Abu Safia on Approximation Algorithms for scheduling or various papers.
In a sense, all public key cryptography is done with "less hard" problems like factoring partially because NP-hard problems offer up too many easy cases. It's the same NP-completeness that makes them "morally hard" which also gives them too many easy problems, which often fall within some error bound of optimal.
There is a deeper theory of hardness of approximation that discusses the limitations of approximation algorithms though.
你说的 startBy 是什么意思？
使用 startAfter 并且如果只有一个资源，那么一种快速解决方案可能是使用拓扑排序 。示例算法以线性时间运行，但如果图形包含循环，则不包括错误情况。
What do you mean with startBy?
With startAfter and if there is only one resource, then a fast solution could be to use topological sorting. The example algorithm runs in linear time, but does not include the error case if the graph contains cycles.
这是一个不是的。
在一台机器上安排一组作业 i= 1,2...n，每个作业花费时间 t(i)，以便最小化平均等待时间。
解决方案：按t(i)的升序排序。 O(n log n)
好列表此处
Here's one that isn't.
Schedule a set of jobs i= 1,2...n on a single machine which each take time t(i) so that the average waiting time is minimized.
Solution: Sort in increasing order of t(i). O(n log n)
Good list here
考虑 P 类中的调度问题：
输入：包括开始时间和结束时间的活动列表。
按完成时间排序。
选择此排序列表的前 N 个元素，以查找您可以在给定时间内安排的最大活动量。
您可以添加一些警告，例如：所有活动必须在下午 5 点结束，在这种情况下，当您完成列表时，一旦到达在此时间之后结束的活动，就停止。
Consider the scheduling problem that is in the class P:
Input: list of activities which include the start time and finish time.
Sort by finish time.
Select the first N elements of this sorted list to find the maximum amount of activities you can schedule in a given time.
You can add caveats like: all activities must end at 5pm, well in this case as you work through the list, stop once you reach an activity which ends after this time.