
本文深入探讨了optaplanner在调度问题中,当没有可行解时仍强制分配规划实体的问题。我们将介绍如何通过引入“过约束规划”概念和配置“可空规划变量”,来确保只有当存在有效方案时才进行分配。教程将通过详细的示例代码和约束定义,指导读者实现更智能、更符合业务需求的资源调度,避免生成不切实际的解决方案。
在使用OptaPlanner解决资源调度问题时,一个常见且令人困扰的场景是:即使在没有销售代表可以被分配给某个预约的情况下,OptaPlanner仍然会尝试强制分配一个销售代表。这种“随机”或“不合理”的分配会导致最终解决方案无法使用,因为它违反了实际业务逻辑——如果一个任务无法被任何人执行,它就不应该被分配。默认情况下,OptaPlanner倾向于为所有规划实体找到一个分配,即使这意味着违反某些约束或生成一个次优解。
为了防止销售代表在同一时间处理多个预约,我们通常会定义一个硬约束。例如,以下是一个常见的冲突约束:
Constraint repConflict(ConstraintFactory constraintFactory) {
// 确保销售代表在任何给定时间只能处理一个预约
return constraintFactory
// 选择每个销售代表的预约对
.forEachUniquePair(Appointment.class,
Joiners.equal(Appointment::getRepUuid)) // 根据销售代表UUID分组
.filter((appt1, appt2) -> {
// 检查两个预约是否有时间重叠
// 如果 appt1 的开始时间在 appt2 结束时间之前,并且 appt2 的开始时间在 appt1 结束时间之前,则存在重叠
return appt1.getStartTime().isBefore(appt2.getEndTime())
&& appt2.getStartTime().isBefore(appt1.getEndTime());
})
// 如果存在重叠,施加一个硬性惩罚
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("SalesRep conflict");
}这个repConflict约束旨在确保销售代表的时间表不会重叠。当一个销售代表被分配了两个时间重叠的预约时,这个约束会施加一个硬性惩罚,从而指导求解器避免此类分配。然而,它的局限性在于:它只在已经存在分配时才发挥作用。它无法阻止OptaPlanner为那些根本找不到合适销售代表的预约“凭空”分配一个。
尝试通过SolverConfig中的withBestScoreFeasible(true)来配置求解器,虽然能确保最终解决方案不包含任何硬约束冲突,但这并不意味着未分配的实体会被自动置空。它仅仅是告诉求解器,如果无法找到一个完全没有硬约束的解决方案,它就不应该停止,而是继续寻找一个最佳的“可行”解决方案。对于那些无法满足任何硬约束的实体,它仍然会尝试找到一个“最佳”的、但可能不合理的分配。
要解决OptaPlanner在无可行解时强制分配的问题,我们需要引入“过约束规划”的概念,并利用“可空规划变量”来实现。
过约束规划是指在某些调度问题中,由于资源限制或任务冲突,可能无法为所有规划实体找到一个完美的、满足所有约束的解决方案。在这种情况下,我们允许一些实体不被分配,并对这些未分配的实体施加软性惩罚,而不是硬性惩罚。这使得求解器能够在无法满足所有需求时,找到一个“次优”但可接受的解决方案,而不是一个“完美”但实际上不可能实现的方案。
实现过约束规划的关键在于允许规划变量为null。这意味着一个规划实体(例如,一个预约)可以不被分配给任何一个规划值(例如,一个销售代表)。
在您的规划实体类(例如Appointment)中,您可以将代表分配的字段声明为可空规划变量:
import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.variable.PlanningVariable;
// ... 其他导入
@PlanningEntity
public class Appointment {
private String uuid; // 预约唯一标识
private Date startTime;
private Date endTime;
// salesRep 是一个规划变量,它会从 salesRepRange 中选择一个 SalesRep 对象
// nullable = true 允许这个规划变量的值为 null,表示该预约未被分配
@PlanningVariable(valueRangeProviderRefs = "salesRepRange", nullable = true)
private SalesRep salesRep; // 被分配的销售代表
// ... 构造函数, getter 和 setter
// 确保 getRepUuid() 方法返回 salesRep 的 UUID,如果 salesRep 为 null,则返回 null
public String getRepUuid() {
return (salesRep != null) ? salesRep.getUuid() : null;
}
}在上述代码中,@PlanningVariable(valueRangeProviderRefs = "salesRepRange", nullable = true)是核心。nullable = true明确告诉OptaPlanner,salesRep这个规划变量可以被设置为null。当一个预约的salesRep为null时,就表示该预约没有被分配给任何销售代表。
仅仅允许nullable = true是不够的。如果一个预约被设置为null可以避免硬约束,OptaPlanner可能会倾向于将所有预约都置为null,因为这能得到一个“无硬约束冲突”的解决方案。为了确保在有可行解时优先进行分配,我们需要定义一个软约束来惩罚那些未被分配的预约。
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
import org.optaplanner.core.api.score.stream.Constraint;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
// ... 其他导入
public class RepSchedulerConstraintProvider implements ConstraintProvider {
@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
return new Constraint[] {
repConflict(constraintFactory),
penalizeUnassignedAppointment(constraintFactory)
};
}
Constraint repConflict(ConstraintFactory constraintFactory) {
// ... (与上面相同的 repConflict 约束)
return constraintFactory
.forEachUniquePair(Appointment.class,
// 注意:如果 getRepUuid() 返回 null,Joiners.equal 将不会匹配,
// 这意味着未分配的预约不会参与此冲突检查,这是期望的行为。
Joiners.equal(Appointment::getRepUuid))
.filter((appt1, appt2) -> {
return appt1.getStartTime().isBefore(appt2.getEndTime())
&& appt2.getStartTime().isBefore(appt1.getEndTime());
})
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("SalesRep conflict");
}
Constraint penalizeUnassignedAppointment(ConstraintFactory constraintFactory) {
// 惩罚所有未被分配销售代表的预约
return constraintFactory.forEach(Appointment.class)
.filter(appointment -> appointment.getSalesRep() == null)
.penalize(HardSoftScore.ONE_SOFT) // 施加一个软性惩罚
.asConstraint("Penalize unassigned appointment");
}
}通过penalizeUnassignedAppointment这个软约束,OptaPlanner在发现无法在不违反硬约束的情况下分配一个预约时,会将其salesRep设置为null,并因此承担一个软性惩罚。这使得求解器能够优先满足硬约束(不冲突),其次是尽量多地进行分配(避免软惩罚)。
至于您在问题中提到的repRewardForAppointment约束,它奖励的是销售代表之间没有时间冲突的预约对。虽然这可以作为一种优化策略来鼓励更紧凑或更合理的调度,但它并非解决“不分配”问题的核心机制。在引入nullable变量和penalizeUnassignedAppointment软约束后,这个奖励约束可以作为额外的优化目标(例如,使用HardMediumSoftScore.ONE_MEDIUM)来进一步引导解决方案,但它不是强制性的。
为了完整地展示这一解决方案,我们来看一下相关的规划模型和配置。
SalesRep (规划值)
public class SalesRep {
private String uuid;
private String name;
// ... 构造函数, getter 和 setter
}Appointment (规划实体)
import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.variable.PlanningVariable;
import java.util.Date;
@PlanningEntity
public class Appointment {
private String uuid;
private Date startTime;
private Date endTime;
@PlanningVariable(valueRangeProviderRefs = "salesRepRange", nullable = true)
private SalesRep salesRep;
public Appointment() {} // OptaPlanner需要无参构造函数
public Appointment(String uuid, Date startTime, Date endTime) {
this.uuid = uuid;
this.startTime = startTime;
this.endTime = endTime;以上就是OptaPlanner高级调度:处理无可行解的规划变量与过约束规划的详细内容,更多请关注php中文网其它相关文章!
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号