3

我正在研究医生调度应用程序，我们正在使用线性规划和像 cplex/lindo 这样的求解器来求解我们的模型。由于一些建模限制，我们需要为夜班生成二进制模式。

通常我们会生成一个月的时间表，所以让我们考虑一下我们需要为夜班生成 30 天的模式。

夜班有一些限制，比如如果一个人连续上夜班，那么医生接下来五天都不能工作。下面是一些约束的例子。

111000001111100000111110000011 Valid
111000001100000000111110000011 Valid
111010001111101000111110000011 Invalid

还有其他约束，例如模式中的数量应该小于某个定义的值，连续的数量应该小于某个定义的值等。

首先，我尝试了简单的算法，该算法从 0 开始并使用按位运算符并添加一个以获得下一个排列，如果无效则检查所有约束的下一个排列是否有效，获取下一个排列并忽略无效模式。由于此模式的长度为 30 位（2 30 = 1073741824），因此模式的数量很大，需要检查我的简单算法。我想找出所有有效模式需要超过 24 小时。

现在我的问题是

  1. 对于给定的问题，我应该使用哪种算法来找到所有排列并以时间有效的方式应用约束？

  2. 这个问题是一个精确的覆盖问题吗？我可以将诸如跳舞链接之类的算法应用于我面临的问题吗？

  3. 请提供一些链接以阅读您针对此问题提出的解决方案？

4

1 回答 1

0

在 11101 结束时不符合夜班规则，则不要添加值为 1 的 5 级节点。继续添加子节点，直到我们有根节点。所以最终我们将只有可行区域，因为我们绕过了不需要的块。这样我就永远不会触及不可行的区域。

于 2013-06-12T05:19:02.867 回答