如何在具有微不足道的重叠约束的同时加快施工阶段

Question

我们正在尝试使用 OptaPlanner 组合一个概念验证规划约束求解器。然而，即使是一组微不足道的约束，构建阶段似乎也很慢，即分配给一个用户，该用户没有重叠任务。

问题概述：

我们正在向用户分配任务只能将一项任务分配给用户任务可以是可变长度：1-16 小时用户一次只能执行一项任务用户每天有 8 小时我们正在使用时间颗粒模式 - 1 颗粒 = 1 小时。请参阅下面的约束配置。

对于少数用户和任务，这很好（returns 在 20 秒内），例如30 个用户/1000 个任务，但是当我们开始扩展时，性能会迅速下降。简单地增加用户数量而不增加任务数量（300 个用户/1000 个任务）将解决时间增加到 120 秒。

但我们希望扩展到 300 个用户/10000 个任务，并纳入更精细的约束。

有没有办法优化constraints/configuration？

Constraint constraint1 = constraintFactory.forEach(Task.class)
                            .filter(st -> st.getUser() == null)
                            .penalize("Assign Task", HardSoftLongScore.ONE_HARD);

Constraint constraint2 = constraintFactory.forEach(Task.class)
                            .filter(st -> st.getStartDate() == null)
                            .penalize("Assign Start Date", HardSoftLongScore.ONE_HARD);      

Constraint constraint3 = constraintFactory
                            .forEachUniquePair(Task.class,
                                                equal(Task::getUser), 
                                                overlapping(st -> st.getStartDate().getId(), 
                                                                st -> st.getStartDate().getId() + st.getDurationInHours()))
                            .penalizeLong("Crew conflict", HardSoftLongScore.ONE_HARD,
                            (st1, st2) -> {
                                int x1 = st1.getStartDate().getId() > st2.getStartDate().getId() ? st1.getStartDate().getId(): st2.getStartDate().getId();
                                int x2 = st1.getStartDate().getId() + st1.getDurationInHours()  < st2.getStartDate().getId() + st2.getDurationInHours() ? 
                                            st1.getStartDate().getId() + st1.getDurationInHours(): st2.getStartDate().getId() + + st2.getDurationInHours();
                                
                                return Math.abs(x2-x1);
                                
                            });

Answer 1

constraint1 和 constraint2 对我来说似乎是多余的。构造启发式阶段将初始化所有规划变量（自动，不会因为不这样做而受到惩罚）并且本地搜索永远不会将规划变量设置为 null（除非您正在优化过度约束的问题）。

您应该能够删除 constraint1 和 constraint2 而不会影响解决方案的质量。

除此之外，您似乎还有两个计划变量（Task.user 和 Task.startDate）。默认情况下，在每个 CH 步骤中，所选实体的两个变量都“一起”初始化。这意味着 OptaPlanner 在所有用户和所有时间粒度的笛卡尔积中寻找该实体的最佳初始值对。这很难扩展。

请参阅 Scaling construction heuristics 章节以了解如何更改该默认行为以及如何使构造启发式算法更好地扩展的其他方式。

如何在具有微不足道的重叠约束的同时加快施工阶段

How to speed up construction phase whilst having an trivial overlapping constraint

optaplanner