SWI Prolog CLP(FD)调度

Question

我正在使用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。现在，为了简化它，每个X都要使用X。

约束条件

• 同一天的每个变量的all_distinct() -每个工作人员只能提供一个服务/天
• global_cardinality()用于计算每个数字1..19在短服务和长服务列表中出现的次数--这定义了变量LSUM_X和SSUM_X -- Long或Short服务中员工X出现的次数
• 每个工人的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标记。这是一个更好的方法吗？
2. 如果你在日历中计算出总工作量限制和总工时，你会发现工人并没有百分之百地被利用。但求解者最有可能以这种方式创建解决方案：utilize the first worker for 100% and then grab the next one。因此，解中的和看起来像[200,200,200...200,160,140,80,50,0,]。如果工人多少能得到平等的利用，我会很高兴的。是否有一些简单有效的方法来实现这一点？我考虑了一些定义，比如定义工人之间的差异并将其最小化，但对我来说，这听起来非常复杂，恐怕我需要很长时间才能计算出来。我使用labeling([random_variable(29)], Vars)，但它只是重新排序变量，所以仍然存在这些差距，只是顺序不同。可能我希望labeling过程以up或down以外的其他顺序(以某种伪随机的方式)接受这些值。
3. 我应该如何排序约束？我认为约束的顺序关系到标签的效率。
4. 如何调试/优化标签的性能？我希望解决这种类型的任务将花费几秒钟或最多几分钟，以防非常紧张的条件和。例如，使用bisect选项进行标记需要很长时间。

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

Answer 1

这是很多问题，让我试着回答一些。

..。只为我的变量(日历字段)的每个组合引入布尔变量，如果员工被分配到特定的日历字段，则为worker设置标记。这是一个更好的方法吗？

这通常是在使用混合整数线性规划( MILP )求解器时完成的，其中较高层次的概念(如alldifferent等)必须表示为线性不等式。这样的公式通常需要大量布尔变量。约束编程在这里更灵活，提供了更多的建模选择，但不幸的是，没有简单的答案，这取决于问题。变量的选择既会影响表达问题约束的难度，也会影响问题解决的效率。

因此，溶液中的和出现在200,200,200,160,140，80，50，0，0。如果工人多少能得到平等的利用，我会很高兴的。是否有一些简单有效的方法来实现这一点？

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

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

然后，只要最小化list元素的最大值，就可以(结合sum约束)给出一个平衡的解决方案：

?- 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)一些不完全搜索。可视化搜索树或搜索进度可以帮助裁剪启发式。您可以在本网上课程第六章中找到对这些问题的一些讨论。