SWI Prolog CLP(FD) 调度 [英] SWI Prolog CLP(FD) scheduling

问题描述

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

I am solving a scheduling task in SWI Prolog using the CLPFD library. Since it is the first time I solve something more serious than was the sendmory I probably need some good advices from more experienced users. Let me briefly describe the domain/the task.

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

I have a "calendar" for a month. Everyday there are 2 for the whole day, 2 for the whole night (long 12h service). There are also, only Mon-Fri 10 more workers for 8 hours (short service).

域约束显然是:

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

我的方法如下:

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

For every field in the calendar I have a variable defined:

• DxD_y 其中 x 是日数，y 是 1 或 2 表示长日服务
• DxN_y 其中 x 是一天的编号，y 是 1 或 2 表示长夜服务
• DxA_y 其中 x 是当天的编号，y 是 0 .. 9 对于短日服务
• SUM_x 其中 x 是工人编号 (1..19)，表示工人的总小时数

• DxD_y where x is number of the day and y is 1 or 2 for the long day service
• DxN_y where x is number of the day and y is 1 or 2 for the long night service
• DxA_y where x is number of the day and y is 0 .. 9 for the short day service
• SUM_x where x is a worker number (1..19) denoting sum of hours for a worker

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

Each of the D variables has a domain 1..19. To simplify it for now, SUM_X #=< 200 for each X.

• all_distinct() 用于同一天的每个变量 - 每个工作人员每天只能提供一项服务
• global_cardinality() 计算每个数字 1..19 的出现次数，用于短服务和长服务列表 - 这定义了变量 LSUM_X 和 SSUM_X - Long 或 Short services
中工人 X 的出现次数
• SUM_X #= 12*LSUM_X + 8*SSUM_X 每个工人
• DxN_y #\= Dx+1D_z - 避免一夜之间的长时间服务
  • 一堆类似的约束，如上面的一个，涵盖了所有领域的约束
  • all_distinct() for each variable for the same day - each worker can serve only one service/day
  • global_cardinality() to count number of occurrences for each number 1..19 for list with short services and long services - this defines variables LSUM_X and SSUM_X - number of occurrences of worker X in Long or Short services
  • SUM_X #= 12*LSUM_X + 8*SSUM_X for each worker
  • DxN_y #\= Dx+1D_z - to avoid long day service after a night one
    • bunch of similar constraints like the one above to cover all the domain constraints

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

    All the variables and constraints are directly stated in the pl script. I do not use prolog predicates to generate constraint - because I have a model in a .NET application (frontend) and I can easily generate all the stuff from the .NET code into a prolog code.

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

    I think my approach is overall good. Running the scheduler on some smaller example works well (7 days, 4 long services, 1 short service, 8 workers). Also I was able to get some valid results on the full blown case - 30 days, 19 workers, 4 long and 10 short services per day.

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

    However, I am not completely satisfied with the current status. Let me explain why.

    1. 我阅读了一些关于建模调度问题的文章，其中一些使用了一些不同的方法 - 只为我的变量(日历字段)和工作人员的每个组合引入布尔变量，以标记工作人员是否被分配到特定的日历字段.这是更好的方法吗?
    2. 如果您计算日历中的总工作量限制和总小时数，您会发现工作人员未被 100% 使用.但是求解器最有可能以这种方式创建解决方案:100% 使用第一个 worker，然后获取下一个 .所以解决方案中的 SUM 看起来像 [200,200,200...200,160,140,​​80,50,0,].如果工人或多或少地得到平等利用，我会很高兴.有没有一些简单/有效的方法来实现这一目标?我考虑过定义有点像定义工人之间的差异并将其最小化，但这对我来说听起来很复杂，恐怕我需要很长时间才能计算出来.我使用labeling([random_variable(29)], Vars)，但它只是对变量重新排序，所以仍然存在这些差距，只是顺序不同.可能我希望 labeling 过程将采用不同于 up 或 down(以某种伪随机方式)的其他顺序取值.
    3. 我应该如何对约束进行排序?我认为约束的顺序对标签的效率很重要.
    4. 如何调试/优化标签性能?我希望解决此类任务需要几秒钟或最多几分钟，以防总和条件非常紧张.例如，使用 bisect 选项标记需要很长时间.
    1. I read some articles about modelling scheduling problems and some of them uses a bit different approach - introducing only boolean variables for each combination of my variable (calendar field) and worker to flag if the worker is assigned to a particular calendar field. Is this a better approach?
    2. If you calculate the overall amount-of-work limits and overall hour in calendar you find out that the workers are not 100% utilized. But the solver creates the solution most likely in this way: utilize the first worker for 100% and then grab the next one. So the SUMs in the solution appears like [200,200,200...200,160,140,80,50,0,]. I would be glad if the workers will be more or less equally utilized. Is there some simple/efficient way how to achieve that? I considered defining somewhat like define the differences between workers and minimize it, but it sound very complex for me and I am afraid I would take ages to compute that. I use labeling([random_variable(29)], Vars), but it only reorders the variables, so there are still these gaps, only in different order. Probably I want the labeling procedure will take the values in some other order than up or down (in some pseudo-random way).
    3. How should I order the constraints? I think the order of constraints matters with respect to efficiency of the labeling.
    4. How to debug/optimize performance of labeling? I hoped solving this type of task will take some seconds or maximally a couple of minutes in case very tight conditions for sums. For example labeling with the the bisect option took ages.

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

    I can provide some more code examples if needed.

    推荐答案

    问题很多，让我试着解决一些.

    That's a lot of questions, let me try to address some.

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

    ... introducing only boolean variables for each combination of my variable (calendar field) and worker to flag if the worker is assigned to a particular calendar field. Is this a better approach?

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

    This is typically done when a MILP (Mixed Integer Linear Programming) solver is used, where higher-level concepts (such as alldifferent etc) have to be expressed as linear inequalities. Such formulations then usually require lots of boolean variables. Constraint Programming is more flexible here and offers more modelling choices, but unfortunately there is no simple answer, it depends on the problem. Your choice of variables influences both how hard it is to express your problem constraints, and how efficiently it solves.

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

    So the SUMs in the solution appears like [200,200,200...200,160,140,80,50,0,]. I would be glad if the workers will be more or less equally utilized. Is there some simple/efficient way how to achieve that?

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

    You already mention the idea of minimizing differences, and this is how such a balancing requirement would usually be implemented. It does not need to be complicated. If originally we have this unbalanced first solution:

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

    然后简单地最小化列表元素的最大值已经给你(结合总和约束)一个平衡的解决方案:

    then simply minimizing the maximum of list elements will already give you (in combination with the sum-constraint) a balanced solution:

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

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

    You could also minimize the difference between minimum and maximum:

    ?- 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，但应该显示总体思路.]

    or even the sum of squares. [Sorry, my examples are for ECLiPSe rather than SWI/clpfd, but should show the general idea.]

    我应该如何对约束进行排序?我认为约束的顺序对标签的效率很重要.

    How should I order the constraints? I think the order of constraints matters with respect to efficiency of the labeling.

    你不必担心这个.虽然它可能会产生一些影响，但它太不可预测，而且过于依赖于实施细节，以至于无法提出任何一般性建议.这确实是求解器实现者的工作.

    You should not worry about this. While it might have some influence, it is too unpredictable and depends too much on implementation details to allow for any general recommendations. This is really the job of the solver implementer.

    如何调试/优化标签性能?

    How to debug/optimize performance of labeling?

    对于实际问题，您通常需要 (a) 特定于问题的标记启发式，以及 (b) 各种不完整搜索.搜索树或搜索进度的可视化有助于定制启发式方法.您可以在本在线课程第 6 章中找到对这些问题的一些讨论.

    For realistic problems, you will often need (a) a problem-specific labeling heuristic, and (b) some variety of incomplete search. Visualization of the search tree or the search progress can help with tailoring heuristics. You can find some discussion of these issues in chapter 6 of this online course.

    这篇关于SWI Prolog CLP(FD) 调度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！