2

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

领域

我有一个月的“日历”。每天全天 2 个，整晚 2 个（长 12 小时服务）。还有，只有周一至周五 10 名以上的工人工作 8 小时（短期服务）。

显然，域约束是：

  1. 没有连续的服务（没有日后夜，反之亦然，没有短日夜后的服务）
  2. On worker 最多可以连续提供 2 次夜间服务
  3. 每个工人一个月的工作时间有限
  4. 有 19 名工人可用

我的方法如下：

变量

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

  • 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.

约束

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

笔记

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

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

但是，我对目前的状态并不完全满意。让我解释一下为什么。

问题

  1. 我阅读了一些关于建模调度问题的文章，其中一些使用了一些不同的方法——只为我的变量（日历字段）和 worker 的每个组合引入布尔变量，以标记是否将 worker 分配给特定的日历字段。这是更好的方法吗？
  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选项标记需要很长时间。

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

4

1 回答 1

2

有很多问题，让我尝试解决一些问题。

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

这通常在使用 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]

那么简单地最小化列表元素的最大值已经给你（结合总和约束）一个平衡的解决方案：

?- 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) 一些不完全搜索。搜索树或搜索进度的可视化有助于定制启发式方法。您可以在本在线课程的第 6 章中找到有关这些问题的一些讨论。

于 2019-04-12T13:07:34.700 回答