我正在使用CLPFD库解决SWI Prolog中的调度任务。由于这是我第一次解决比发送更严重的事情,我可能需要更有经验的用户提供一些好的建议。让我简要描述一下域/任务。
域
我有一个月的"日历"。每天全天有2个,整晚有2个(长12小时服务)。还有,只有周一至周五 10 多名工人 8 小时(短期服务)。
显然,域约束是:
- 没有连续的服务(没有昼夜,反之亦然,晚上后没有短日服务)
- 上班工人最多可连续提供2晚服务
- 每个工人一个月的工作时间有限
- 有19位工人可用
我的方法如下:
变量
对于日历中的每个字段,我都定义了一个变量:
DxD_y
其中x
是一天的数字,y
是1或2的长日服务DxN_y
其中x
是白天的数字,长夜服务的y
是 1 或 2DxA_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
和SSUM_X
-L
ong 或S
hort 服务中工人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 个短期服务。
但是,我对目前的状况并不完全满意。让我解释一下原因。
问题
- 我阅读了一些关于建模调度问题的文章,其中一些使用了一种不同的方法 - 只为我的变量(日历字段)和工作人员的每个组合引入布尔变量,以标记工作人员是否被分配到特定的日历字段。这是更好的方法吗?
- 如果您计算日历中的总工作量限制和总工时,您会发现工作人员没有 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
以外的其他顺序(以某种伪随机方式)获取值。 - 我应该如何对约束进行排序?我认为约束的顺序对标签的效率很重要。
- 如何调试/优化标签性能?我希望解决这种类型的任务需要几秒钟或最多几分钟,以防总和条件非常紧张。例如,使用
bisect
选项进行标记需要很长时间。
如果需要,我可以提供更多代码示例。
这是很多问题,让我尝试解决一些问题。
。如果工作人员被分配到特定的日历字段,则只为我的变量(日历字段)和工作人员的每个组合引入布尔变量,以标记该工作人员。这是更好的方法吗?
这通常在使用 MILP(混合整数线性规划)求解器时完成,其中更高层次的概念(如alldifferent
等)必须表示为线性不等式。 这样的公式通常需要大量的布尔变量。 约束规划在这里更加灵活,并提供了更多的建模选择,但不幸的是没有简单的答案,这取决于问题。您对变量的选择会影响表达问题约束的难度以及解决问题的效率。
...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 章中找到有关这些问题的一些讨论。