19

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

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

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

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

耶复合问题！

4

6 回答 6

24

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

  • A教授早上起不来，他参加了很多委员会，但没有人会告诉时间表办公室这种限制
  • 部门 1 需要在学期开始前的时间表，然而，使用相同房间的部门 2 不愿意在所有学生都到齐之后决定将要运行的课程
  • ETC

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

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

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

于 2010-01-29T16:51:40.040 回答
4

对于像调度这样的 NP 难/完全优化问题，通常有很好的近似算法。您可能会浏览 Ahmed Abu Safia 的课程笔记，关于用于调度的近似算法或各种论文。

从某种意义上说，所有公钥密码术都是通过“不那么难”的问题完成的，例如部分因式分解，因为 NP-hard 问题提供了太多简单的情况。正是同样的 NP 完备性使它们“在道德上很难”，这也给它们带来了太多简单的问题，这些问题通常落在最优的一些错误范围内。

不过，有一个更深层次的近似硬度理论讨论了近似算法的局限性。

于 2012-06-25T13:52:21.427 回答
3

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

于 2010-01-29T14:17:49.157 回答
2

startBy 是什么意思？

使用 startAfter 并且如果只有一个资源，那么一个快速的解决方案可能是使用拓扑排序。示例算法以线性时间运行，但如果图形包含循环，则不包括错误情况。

于 2010-01-29T16:20:10.490 回答
2

这是一个不是。

在一台机器上安排一组作业 i= 1,2...n，每个作业都需要时间 t(i)，以便最小化平均等待时间。

解决方案：按 t(i) 的升序排序。O(n log n)

好清单在这里

于 2010-02-15T20:36:19.827 回答
1

考虑 P 类中的调度问题：

输入：活动列表，包括开始时间和结束时间。

按完成时间排序。

选择此排序列表的前 N ​​个元素，以查找您可以在给定时间内安排的最大活动量。

您可以添加一些警告，例如：所有活动必须在下午 5 点结束，在这种情况下，当您完成列表时，一旦您到达在此时间之后结束的活动，就停止。

于 2016-12-13T09:53:02.213 回答