最适合的调度算法

Question

我正在写一个编程难度很大的调度程序。有几个事件，每个都有多个会议时间。我需要找到一个安排会议时间，使每个时间表包含任何给定的事件一次，使用每个事件的多个会议时间之一。

显然我可以使用蛮力，但这很少是最好的解决方案。我猜这是一个相对基本的计算机科学问题，一旦我能够开始参加计算机科学课程，我将会了解到这个问题。与此同时，我更喜欢任何可以阅读的链接，甚至只是一个可以让Google知名的链接。

Answer 1

我认为你应该使用遗传算法，因为：

• 它是最适合于大问题的情况。
• 它产生于
• 您可以通过调整适应的惩罚不能满足那些喜好&轻松指定约束不准确答案的价格（不是最终的最好的）降低时间复杂度。
• 您可以指定程序执行的时间限制。

• 溶液的质量取决于你打算多少时间花在解决方案..

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

Answer 2

您的问题描述并不完全清楚，但如果您所要做的只是找到一个没有重叠事件的计划，那么这是一个直接的bipartite matching问题。

您有两组节点：事件和时间。从每个事件到每个可能的会议时间画一条边。然后，您可以使用augmented paths有效地构建匹配（节点之间最大可能的一组边）。这是有效的，因为你总是可以将二部图转换为等价的流图。

这样做的代码示例是BIM。标准图形库，如GOBLIN和NetworkX也有双边匹配的实现。

Answer 3

这听起来像这可能是一个dynamic programming解决方案，特别是类似于interval scheduling问题的一个很好的候选人。

对于区间调度问题，有一些视觉here具体，这可能会使概念更清晰。 Here是一个关于整体动态编程的好教程。

Answer 4

有几种方法可以做到这

一种方法是做约束编程。这是feanor建议的动态编程的特例。使用可以为你做边界和分支的专门库是很有帮助的。 （谷歌的“gecode”或“彗星在线”来找到库）

如果你是数学上的倾向，那么你也可以使用整数编程来解决这个问题。这里的基本思想是将你的问题转化为一组线性不等式。 （谷歌的“整数编程调度”，以找到许多现实生活中的例子和谷歌“算盘COIN-OR”为一个有用的库）

我的猜测是约束编程是最简单的方法，但整数编程是有用的，如果你想要在某个时候在你的问题中包含实际变量。