SWI Prolog CLP(FD) scheduling



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

我有一个月的"日历"。每天全天有2个,整晚有2个(长12小时服务)。还有,只有周一至周五 10 多名工人 8 小时(短期服务)。

显然,域约束是:

  1. 没有连续的服务(没有昼夜,反之亦然,晚上后没有短日服务)
  2. 上班工人最多可连续提供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_XSSUM_X-Long 或Short 服务中工人X的出现次数
  • 每个工作人员的SUM_X #= 12*LSUM_X + 8*SSUM_X
  • DxN_y #= Dx+1D_z- 避免在一夜之后长时间的白天服务
    • 一堆类似的约束,如上面一个,涵盖了所有的领域约束
  • DxNy #= Dx+1Ny #==> DxNy #= Dx+2Ny- 为避免连续三次夜间服务,每种组合都有xy
  • 的限制

笔记

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

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

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

问题

  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过程将以updown以外的其他顺序(以某种伪随机方式)获取值。
  3. 我应该如何对约束进行排序?我认为约束的顺序对标签的效率很重要。
  4. 如何调试/优化标签性能?我希望解决这种类型的任务需要几秒钟或最多几分钟,以防总和条件非常紧张。例如,使用bisect选项进行标记需要很长时间。

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

这是很多问题,让我尝试解决一些问题。

。如果工作人员被分配到特定的日历字段,则只为我的变量(日历字段)和工作人员的每个组合引入布尔变量,以标记该工作人员。这是更好的方法吗?

这通常在使用 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 章中找到有关这些问题的一些讨论。

相关内容

  • 没有找到相关文章

最新更新