SWI Prolog CLP（FD）调度

Question

我正在使用CLPFD库在SWI Prolog中解决调度任务。由于这是我第一次解决比sendmory更严重的问题，我可能需要一些来自更有经验的用户的好建议。让我简要描述域/任务。

域

我有一个月的“日历”。每天有2个一整天，2个整夜（长12小时服务）。此外，周一至周五还有10名工人需要8小时（短期服务）。

域限制显然是：

1. 没有连续的服务（没有一夜又一夜，反之亦然，晚上没有短日服务）
2. 工人可连续提供连续2晚的服务
3. 每个工人一个月的工作时间有限
4. 有19名工人可用

我的方法如下：

Variables

对于日历中的每个字段，我都定义了一个变量：

• DxD_y，其中x是当天的数字，y是1或2的长日服务
• DxN_y，其中x是当天的数字，y是1或2的长夜服务
• DxA_y，其中x是当天的数字，而y是0 .. 9的短日服务
• SUM_x，其中x是工人号码（1..19），表示工人的小时数

每个D变量都有一个域1..19。为了简化它现在，SUM_X #=< 200为每个X。

Constraints

• all_distinct()为同一天的每个变量 - 每个工人每天只能服务一次
• global_cardinality()计算每个数字1..19的出现次数，用于短服务和长服务的列表 - 这定义变量LSUM_X和SSUM_X - Xong或Lhort服务中工人S的出现次数
• SUM_X #= 12*LSUM_X + 8*SSUM_X为每个工人
• DxN_y #\= Dx+1D_z - 避免一夜之后的长时间服务 一堆类似的约束，如上所述，以涵盖所有域约束
• DxNy #= Dx+1Ny #==> DxNy #\= Dx+2Ny - 为避免连续三次夜间服务，x和y的每个组合都有限制

Notes

所有变量和约束都直接在pl脚本中说明。我不使用prolog谓词来生成约束 - 因为我在.NET应用程序（前端）中有一个模型，我可以轻松地从.NET代码生成所有内容到prolog代码。

我认为我的方法总体上是好的。在一些较小的示例上运行调度程序运行良好（7天，4个长服务，1个短服务，8个工作）。此外，我还能够在完整的案例中得到一些有效的结果 - 每天30天，19名工人，4个长期和10个短期服务。

但是，我对目前的状况并不完全满意。让我解释一下原因。

Questions

1. 我阅读了一些关于建模调度问题的文章，其中一些使用了一种不同的方法 - 仅为我的变量（日历字段）的每个组合引入布尔变量，并且如果将工作者分配给特定日历字段，则标记工作者。这是一种更好的方法吗？
2. 如果您计算总体工作量限制和日历中的总小时数，则会发现工人未被100％利用。但解算器最有可能以这种方式创建解决方案：utilize the first worker for 100% and then grab the next one。所以解决方案中的SUM看起来像[200,200,200...200,160,140,80,50,0,]。如果工人的利用率或多或少得多，我会很高兴的。有一些简单/有效的方法如何实现这一目标？我认为定义有点像定义工人之间的差异并将其最小化，但对我来说这听起来非常复杂，我担心我需要花费很长时间才能计算出来。我使用labeling([random_variable(29)], Vars)，但它只重新排序变量，所以仍然存在这些差距，只是顺序不同。可能我希望labeling程序将采用除up或down之外的其他顺序的值（以某种伪随机方式）。
3. 我该如何订购约束？我认为约束的顺序与标签的效率有关。
4. 如何调试/优化标签的性能？我希望解决这类任务需要几秒钟或最多几分钟，以防万一的条件非常紧张。例如，使用bisect选项进行标记需要很长时间。

如果需要，我可以提供更多代码示例。

Answer 1

这是很多问题，让我试着解决一些问题。

...仅为我的变量（日历字段）和工作人员的每个组合引入布尔变量，如果将工作人员分配给特定日历字段则标记。这是一种更好的方法吗？

这通常在使用MILP（混合整数线性规划）求解器时完成，其中更高级别的概念（例如alldifferent等）必须表示为线性不等式。这样的配方通常需要许多布尔变量。约束编程在这里更灵活，并提供更多的建模选择，但不幸的是没有简单的答案，它取决于问题。您选择的变量会影响表达问题约束的难度以及解决问题的效率。

所以解决方案中的SUM看起来像[200,200,200 ... 200,160,140,​​80,50,0，]。如果工人的利用率或多或少得多，我会很高兴的。有一些简单/有效的方法如何实现这一目标？

您已经提到了最小化差异的想法，这就是通常如何实现这种平衡要求。它不需要复杂。如果最初我们有这个不平衡的第一个解决方案：

?- length(Xs,5), Xs#::0..9, sum(Xs)#=20, labeling(Xs).
Xs = [0, 0, 2, 9, 9]

那么简单地最小化列表元素的最大值就会给你（与sum-constraint结合）一个平衡的解决方案：

?- length(Xs,5), Xs#::0..9, sum(Xs)#=20, Cost#=max(Xs), minimize(labeling(Xs),Cost).
Xs = [4, 4, 4, 4, 4]
Cost = 4

您还可以最小化最小值和最大值之间的差异：

?- length(Xs,5), Xs#::0..9, sum(Xs)#=20, Cost#=max(Xs)-min(Xs), minimize(labeling(Xs),Cost).
Xs = [4, 4, 4, 4, 4]
Cost = 0

甚至是平方和。 [对不起，我的例子是针对ECLiPSe而不是SWI / clpfd，但应该显示一般的想法。]

我该如何订购约束？我认为约束的顺序与标签的效率有关。

你不应该担心这个。虽然它可能会产生一些影响，但它太不可预测，并且过分依赖于实现细节以允许任何一般性建议。这实际上是求解器实现者的工作。

如何调试/优化标签的性能？

对于现实问题，您通常需要（a）特定于问题的标签启发式，以及（b）各种不完整的搜索。搜索树的可视化或搜索进度可以帮助定制启发式。你可以在chapter 6 of this online course找到一些关于这些问题的讨论。