algorithm - on-call夜间调度算法

Question

我作为一名 RA 在我大学的宿舍工作，每天晚上我们需要两名 RA 待命(能够应对事件和紧急情况)。每个月，RA 都会提交他们无法值类的夜晚(由于某种冲突)。有男性和女性 RA。我正在尝试提出一种有效的算法来为满足以下要求的任何特定月份找到最佳的待命之夜安排:

• 没有 RA 被安排在他或她列为不可用的晚上。
• 每个 RA 的值类夜数都没有超过指定的数量。
• 没有 RA 在任何给定的三晚时间跨度内两次随叫随到。
• 每晚恰好有两个 RA 值类。
• 如果可能的话，每晚都有一名男性和一名女性 RA 值类。

经过一些研究，我发现这是一个资源受限的调度问题，它被认为是 NP 完全问题。因此，我不需要找到最佳解决方案，只需找到任何可行的解决方案即可。

到目前为止，我已经考虑了以下方法:

• 一个简单的二维数组，其中每个单元格包含一个 bool 值，用于回答该 RA 是否在当晚待命。我可以将 RA 排在两个优先队列中(一男一女)，按照他们到目前为止已经过了多少个晚上，自上次待命之夜以来已经过了多长时间，然后简单地遍历夜晚，选择一个 RA来自每个队列，然后如果我遇到死胡同，在某个特定的晚上没有人可以工作，则回溯。
• 三方图，一侧是男性 RA，另一侧是女性 RA，最后一侧是夜晚。在解决方案中，每个晚上都会有一名男性和一名女性 RA 的优势。我将从连接所有边开始，然后移除边，直到找到解决方案。
• 使用上述结构的某种遗传方法。

您建议我使用哪种方法？有什么我没有想到的可能会更好吗？这不是作业问题；我正在尝试开发一个网站，让我的员工和校园里的其他员工可以轻松提交日期偏好，然后生成适合所有人的时间表。

Answer 1

我推荐二维数组，但不是按照从头到尾的顺序遍历夜晚，而是按照从最多到最少约束的顺序遍历夜晚——换句话说，从到期时可用 RA 最少的夜晚开始冲突。如果您采用这种方法，这种启发式也可以应用于三方图 - 这基本上是域表示的问题，算法本身此时不受影响。

问题是，当您到达最后几个晚上并发现没有可用的 RA 时，您会怎么做。此时你会做 local search尝试找到一个可行的解决方案，例如，您为 NightA 选择了 RA1，但当晚 RA2 和 RA3 也可用，因此您选择 RA2 或 RA3 以查看是否可以为您没有的夜晚腾出 RA1一个可用的 RA。