1

使用 Django 开发一个小型调度 Web 应用程序，在该应用程序中，人们被分配特定时间与他们的上级会面。员工被存储为模型，与表示时间范围和一周中空闲时间的模型的 OneToMany 关系。例如：

Bob: (W 9:00, 9:15), (W 9:15, 9:30), ... (W 15:00, 15:20)
Sarah: (Th 9:05, 9:20), (F 9:20, 9:30), ... (Th 16:00, 16:05)
...
Mary: (W 8:55, 9:00), (F 13:00, 13:35), ... etc

我的程序允许设置基本的日程安排，雇主可以选择查看前 N 个可能的日程安排，条件是他们在那周至少与所有员工会面一次。我目前正在生成所有可能的会议排列，并过滤掉会议时间重叠的时间表。有没有一种方法可以从 M 个可能的时间表中生成前 N 个时间表，而无需经历所有 M 个可能性？

澄清：我们试图获得任何一天的最小差距总和，所有天的总和。

4

2 回答 2

0

我会使用搜索算法，比如A-star来做到这一点。图中的每个节点代表一个人的可用时间段，并且从一个节点到另一个节点的路径意味着node_a并且node_b在部分时间表中。

另一种解决方案是创建一个图，其中节点是每个人的可用时间，如果与 node_a 关联的人与与 node_b 关联的人不同，则存在从 node_a 到 node_b 的边。每个节点的权重是与两个节点相关联的时间之间的时间量。

创建此图后，您可以从图中生成最小生成树的变体。该变体与 MST 的不同之处在于：

  1. 如果与节点关联的人员尚未在 MST 中，您将仅将节点添加到 MST。
  2. 当所有人都在 MST 中时，您完成了 MST 的创建。

生成的最小生成树将代表单个调度。

要生成其他计划，请从图中删除您刚刚创建的计划中找到的所有边，然后从已删除边的图中创建一个新的最小生成树。

于 2013-01-02T03:17:57.410 回答
0

一般来说，调度问题是 NP 难的，虽然我想不出这个问题的简化来证明这一点，但它与许多其他著名的 NP 完全问题非常相似。可能有一个多项式时间的解决方案可以找到一天的最小差距（尽管我也不知道），但我不太希望需要多天来解决它。不幸的是，这是一个复杂的问题，可能没有一个完美优雅的答案。（或者，当有人稍后发布时，我会踢自己。）

首先，我想说，如果您的数据集相当小，并且您已经能够相当快地计算所有可能的时间表，您可能只想坚持使用该解决方案，因为所有其他解决方案都是近似值，并且可能最终运行速度较慢，如果它们运行时间的常数因子很大。（意味着它不会随着数据集的大小而增长，因此对于大型数据集它会相对较小。）

最简单的近似是只使用贪心启发式。它几乎肯定不会找到最佳时间表，如果大多数时间表重叠，可能需要很长时间才能找到解决方案，而且只有少数甚至是有效的解决方案 - 但我会假设这是员工时间并非如此。

从任意时间表开始，为每位员工随机选择一个时间段。对于每次迭代，选择一名员工并将他的时间段更改为相对于当前计划的其余部分的最佳时间。重复此过程，直到您对结果感到满意 - 当它不再足够快或花费太长时间时。您可能不想重复，直到您无法进行任何改进计划的更改，因为此过程可能会循环处理大多数数据。

这不是一个很好的启发式方法，但它应该产生一些合理的时间表，并且有很大的调整空间。您可能希望始终先尝试切换重叠时间，或者您可能希望尝试调换当前造成最大差距的员工，或者可能消除您已经尝试过的某些时段。您有时可能希望允许转向不太理想的解决方案，希望您处于局部最小值并想要摆脱它 - 一些随机性也可以帮助解决这个问题。确保您始终跟踪您迄今为止看到的最佳解决方案。

要生成更多时间表，最明显的做法是使用不同的随机时间表重新开始该过程。或者，可能从您找到的上一个解决方案中任意翻转几次，然后从那里重复。

编辑：这都与遗传算法相当相关，您可能想要使用我在 GA 中提出的一些想法。

于 2013-01-02T04:24:31.163 回答