1

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

  • 没有 RA 安排在他或她列为不可用的晚上。
  • 没有 RA 待命的时间超过每月指定的夜数。
  • 在任何给定的三晚范围内，没有 RA 两次待命。
  • 每晚都有两个 RA 待命。
  • 如果可能，每晚都有一名男性和一名女性 RA 随叫随到。

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

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

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

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

4

2 回答 2

0

使用提到的二进制变量，您的问题可以表述为整数线性规划(ILP)。如果变量不超过几千个，则可以通过GLPK之类的求解器最佳地求解。除最后一个之外的所有约束都已经是线性的。对于“如果可能，每晚都有一名男性和一名女性 RA 待命”，您可以为每晚引入另一个布尔变量“x”，有一个约束“待命女性 RA 的总和 <= 1 + x”，并且然后最小化 x 的总和，从而允许以一定的代价违反约束。如果您以文本格式向求解器提供数据，这也应该不太难实现。

于 2013-04-24T16:30:31.397 回答
0

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

问题是当您到达最后几个晚上并发现没有可用的 RA 时您会做什么。此时，您将进行本地搜索以尝试找到可行的解决方案，例如您为 NightA 选择了 RA1，但当晚 RA2 和 RA3 也可用，因此您选择 RA2 或 RA3 以查看是否可以释放 RA1对于您没有可用 RA 的那晚。

于 2013-04-19T23:49:16.417 回答