Timefold Solver 员工排程优化指南

最后修改:2025年5月1日

by Geoffrey De Smet

1. 概述

1.1 Timefold Solver 是什么？

Timefold Solver 是一个纯 Java 规划求解 AI 引擎。它专注于优化规划问题，例如车辆路径问题（VRP）、维护调度、车间作业调度和学校课程表。通过生成物流计划，它能显著降低成本、提升服务质量并减少环境足迹——在复杂的现实调度场景中，优化幅度通常可达 25%。

Timefold 是 OptaPlanner 的延续。它属于数学优化范畴（更广泛的运筹学和人工智能领域），支持用代码形式编写约束条件。

1.2 我们将构建什么

本教程将使用 Timefold Solver 优化一个简化的员工排班问题。我们将自动为员工分配班次，需满足以下条件：

  • 同一员工在同一天不能安排两个班次
  • 每个班次必须分配给具备相应技能的员工

具体来说，我们将分配以下五个班次：

  2030-04-01 06:00 - 14:00 (服务员)
  2030-04-01 09:00 - 17:00 (调酒师)
  2030-04-01 14:00 - 22:00 (调酒师)
  2030-04-02 06:00 - 14:00 (服务员)
  2030-04-02 14:00 - 22:00 (调酒师)

给这三名员工：

  Ann (调酒师)
  Beth (服务员, 调酒师)
  Carl (服务员)

这问题比看起来复杂，不妨先在纸上试试手。

2. 依赖项

Timefold Solver 在 Maven Central 上的构件采用 Apache 许可证发布。我们按需引入：

2.1 纯 Java 环境

在 Maven 或 Gradle 中添加核心依赖 timefold-solver-core 和测试依赖 timefold-solver-test：

<dependencyManagement>
    <dependencies>
        <dependency>
            <groupId>ai.timefold.solver</groupId>
            <artifactId>timefold-solver-bom</artifactId>
            <version>...</version>
            <type>pom</type>
            <scope>import</scope>
        </dependency>
    </dependencies>
</dependencyManagement>
<dependencies>
    <dependency>
        <groupId>ai.timefold.solver</groupId>
        <artifactId>timefold-solver-core</artifactId>
    </dependency>
    <dependency>
        <groupId>ai.timefold.solver</groupId>
        <artifactId>timefold-solver-test</artifactId>
        <scope>test</scope>
    </dependency>
</dependencies>

2.2 Spring Boot 环境

在 Spring Boot 中改用 timefold-solver-spring-boot-starter 依赖。它能自动处理大部分求解器配置，并支持在 application.properties 中设置求解时间等参数：

  1. 访问 start.spring.io
  2. 点击 Add dependencies 添加 Timefold Solver 依赖
  3. 生成项目并在你喜欢的 IDE 中打开

2.3 Quarkus 环境

在 Quarkus 中类似，通过 code.quarkus.io 添加 timefold-solver-quarkus 依赖，同样支持自动配置和 application.properties。

3. 领域类

领域类同时表示输入数据和输出数据。我们创建 Employee 和 Shift 类，以及包含特定数据集员工和班次列表的 ShiftSchedule 类。

3.1 Employee 类

员工是可分配班次的对象。每个员工有姓名和一项或多项技能。

Employee 类不需要任何 Timefold 注解，因为它在求解过程中不会改变：

public class Employee {

    private String name;
    private Set<String> skills;

    public Employee(String name, Set<String> skills) {
        this.name = name;
        this.skills = skills;
    }

    @Override
    public String toString() {
        return name;
    }

    // Getters and setters
}

3.2 Shift 类

班次是在特定日期从开始时间到结束时间分配给一名员工的工作。同一时间可能存在多个班次。每个班次有一项必需技能。

Shift 对象在求解过程中会变化：每个班次被分配给员工。Timefold 需要知道这一点。只有 employee 字段在求解中变化，因此我们用 @PlanningEntity 注解类，用 @PlanningVariable 注解 employee 字段：

@PlanningEntity
public class Shift {

    private LocalDateTime start;
    private LocalDateTime end;
    private String requiredSkill;

    @PlanningVariable
    private Employee employee;

    // @PlanningEntity 注解类需要无参构造函数
    public Shift() {
    }

    public Shift(LocalDateTime start, LocalDateTime end, String requiredSkill) {
        this(start, end, requiredSkill, null);
    }

    public Shift(LocalDateTime start, LocalDateTime end, String requiredSkill, Employee employee) {
        this.start = start;
        this.end = end;
        this.requiredSkill = requiredSkill;
        this.employee = employee;
    }

    @Override
    public String toString() {
        return start + " - " + end;
    }

    // Getters and setters
}

3.3 ShiftSchedule 类

排程表表示单个员工和班次数据集。它既是 Timefold 的输入也是输出：

  • 用 @PlanningSolution 注解 ShiftSchedule 类，表示它是输入和输出
  • 用 @ValueRangeProvider 注解 employees 字段，告诉 Timefold 它包含可分配给 Shift.employee 的员工列表
  • 用 @PlanningEntityCollectionProperty 注解 shifts 字段，让 Timefold 找到所有需要分配员工的 Shift 实例
  • 包含带 @PlanningScore 注解的 score 字段，Timefold 会自动填充它。我们使用 HardSoftScore 以便后续区分硬约束和软约束
@PlanningSolution
public class ShiftSchedule {

    @ValueRangeProvider
    private List<Employee> employees;
    @PlanningEntityCollectionProperty
    private List<Shift> shifts;

    @PlanningScore
    private HardSoftScore score;

    // @PlanningSolution 注解类需要无参构造函数
    public ShiftSchedule() {
    }

    public ShiftSchedule(List<Employee> employees, List<Shift> shifts) {
        this.employees = employees;
        this.shifts = shifts;
    }

    // Getters and setters
}

4. 约束条件

没有约束，Timefold 会把所有班次分配给第一个员工——这显然不是可行方案。我们需要添加 两个硬约束 来教会它区分好坏排程：

  • atMostOneShiftPerDay() 约束检查同一天的两个班次是否分配给同一员工。如果是，扣减 1 分硬约束分数
  • requiredSkill() 约束检查班次是否分配给具备所需技能的员工。如果不是，扣减 1 分硬约束分数

单个硬约束优先级高于所有软约束。硬约束通常代表物理或法律上不可违反的规则；软约束则可违反但需最小化，通常代表财务成本、服务质量或员工满意度。硬约束和软约束使用相同的 API 实现。

4.1 ConstraintProvider 实现

首先创建约束实现类：

public class ShiftScheduleConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
          atMostOneShiftPerDay(constraintFactory),
          requiredSkill(constraintFactory)
        };
    }

    // 约束实现方法

}

4.2 单元测试 ConstraintProvider

未测试的约束等于无效代码！创建测试类验证每个约束：

测试范围的 timefold-solver-test 依赖包含 ConstraintVerifier，用于独立测试每个约束。这提升维护性——重构单个约束不会破坏其他约束的测试：

public class ShiftScheduleConstraintProviderTest {

    private static final LocalDate MONDAY = LocalDate.of(2030, 4, 1);
    private static final LocalDate TUESDAY = LocalDate.of(2030, 4, 2);

    ConstraintVerifier<ShiftScheduleConstraintProvider, ShiftSchedule> constraintVerifier
      = ConstraintVerifier.build(new ShiftScheduleConstraintProvider(), ShiftSchedule.class, Shift.class);

    // 每个约束的测试方法

}

我们准备了两个日期供测试复用。下面添加具体约束实现。

4.3 硬约束：每天最多一个班次

遵循 TDD（测试驱动开发），先在测试类中编写约束测试：

@Test
void whenTwoShiftsOnOneDay_thenPenalize() {
    Employee ann = new Employee("Ann", null);
    constraintVerifier.verifyThat(ShiftScheduleConstraintProvider::atMostOneShiftPerDay)
      .given(
        new Shift(MONDAY.atTime(6, 0), MONDAY.atTime(14, 0), null, ann),
        new Shift(MONDAY.atTime(14, 0), MONDAY.atTime(22, 0), null, ann))
      // 惩罚2分，因为 {班次A, 班次B} 和 {班次B, 班次A} 都匹配
      // 避免此问题：在约束中使用 forEachUniquePair() 替代 forEach().join()
      .penalizesBy(2);
}

@Test
void whenTwoShiftsOnDifferentDays_thenDoNotPenalize() {
    Employee ann = new Employee("Ann", null);
    constraintVerifier.verifyThat(ShiftScheduleConstraintProvider::atMostOneShiftPerDay)
      .given(
        new Shift(MONDAY.atTime(6, 0), MONDAY.atTime(14, 0), null, ann),
        new Shift(TUESDAY.atTime(14, 0), TUESDAY.atTime(22, 0), null, ann))
      .penalizesBy(0);
}

然后在 ConstraintProvider 中实现：

public Constraint atMostOneShiftPerDay(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Shift.class)
      .join(Shift.class,
        equal(shift -> shift.getStart().toLocalDate()),
        equal(Shift::getEmployee))
      .filter((shift1, shift2) -> shift1 != shift2)
      .penalize(HardSoftScore.ONE_HARD)
      .asConstraint("At most one shift per day");
}

我们使用 ConstraintStreams API 实现约束：一个类似 Stream/SQL 的 API，底层提供增量分数计算（增量）和索引哈希表查找。这种方法可扩展到包含数十万班次的大型数据集。

运行测试验证通过 ✅。

4.4 硬约束：必需技能

在测试类中编写测试：

@Test
void whenEmployeeLacksRequiredSkill_thenPenalize() {
    Employee ann = new Employee("Ann", Set.of("Waiter"));
    constraintVerifier.verifyThat(ShiftScheduleConstraintProvider::requiredSkill)
      .given(
        new Shift(MONDAY.atTime(6, 0), MONDAY.atTime(14, 0), "Cook", ann))
      .penalizesBy(1);
}

@Test
void whenEmployeeHasRequiredSkill_thenDoNotPenalize() {
    Employee ann = new Employee("Ann", Set.of("Waiter"));
    constraintVerifier.verifyThat(ShiftScheduleConstraintProvider::requiredSkill)
      .given(
        new Shift(MONDAY.atTime(6, 0), MONDAY.atTime(14, 0), "Waiter", ann))
      .penalizesBy(0);
}

在 ConstraintProvider 中实现新约束：

public Constraint requiredSkill(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Shift.class)
      .filter(shift -> !shift.getEmployee().getSkills()
        .contains(shift.getRequiredSkill()))
      .penalize(HardSoftScore.ONE_HARD)
      .asConstraint("Required skill");
}

再次运行测试，全部通过 ✅。

**若要改为软约束，只需将 penalize(HardSoftScore.ONE_HARD) 改为 penalize(HardSoftScore.ONE_SOFT)**。若需根据输入数据动态决策，可改用 penalizeConfigurable() 和 @ConstraintWeight。

5. 应用整合

现在整合我们的应用。

5.1 求解过程

求解排程需 **创建 SolverFactory**，基于我们的 @PlanningSolution、@PlanningEntity 和 ConstraintProvider 类。SolverFactory 是长生命周期对象，通常每个应用只有一个实例。

还需配置求解器运行时长。对于大型数据集（数千班次和更多约束），在合理时间内找到最优解是不可能的（因为 NP-hard 问题的指数特性）。我们改为在可用时间内寻找最佳解。当前限制为 2 秒：

SolverFactory<ShiftSchedule> solverFactory = SolverFactory.create(new SolverConfig()
  .withSolutionClass(ShiftSchedule.class)
  .withEntityClasses(Shift.class)
  .withConstraintProviderClass(ShiftScheduleConstraintProvider.class)
  // 在此小数据集上仅运行2秒
  // 大型数据集建议至少运行5分钟 ("5m")
  .withTerminationSpentLimit(Duration.ofSeconds(2)));

用 SolverFactory 创建 Solver 实例（每个数据集一个），然后调用 Solver.solve() 求解：

Solver<ShiftSchedule> solver = solverFactory.buildSolver();
ShiftSchedule problem = loadProblem();
ShiftSchedule solution = solver.solve(problem);
printSolution(solution);

在 Spring Boot 中，SolverFactory 会自动构建并注入到 @Autowired 字段：

@Autowired
SolverFactory<ShiftSchedule> solverFactory;

求解时间在 application.properties 中配置：

timefold.solver.termination.spent-limit=5s

在 Quarkus 中类似，SolverFactory 也自动构建并注入到 @Inject 字段，求解时间同样在 application.properties 中配置。

若需异步求解（避免 Solver.solve() 阻塞当前线程），应注入并使用 SolverManager。

5.2 测试数据

生成包含五个班次和三名员工的测试数据集：

private ShiftSchedule loadProblem() {
    LocalDate monday = LocalDate.of(2030, 4, 1);
    LocalDate tuesday = LocalDate.of(2030, 4, 2);
    return new ShiftSchedule(List.of(
      new Employee("Ann", Set.of("Bartender")),
      new Employee("Beth", Set.of("Waiter", "Bartender")),
      new Employee("Carl", Set.of("Waiter"))
    ), List.of(
      new Shift(monday.atTime(6, 0), monday.atTime(14, 0), "Waiter"),
      new Shift(monday.atTime(9, 0), monday.atTime(17, 0), "Bartender"),
      new Shift(monday.atTime(14, 0), monday.atTime(22, 0), "Bartender"),
      new Shift(tuesday.atTime(6, 0), tuesday.atTime(14, 0), "Waiter"),
      new Shift(tuesday.atTime(14, 0), tuesday.atTime(22, 0), "Bartender")
    ));
}

5.3 求解结果

将测试数据输入求解器后，输出结果到 System.out：

private void printSolution(ShiftSchedule solution) {
    logger.info("班次分配结果");
    for (Shift shift : solution.getShifts()) {
        logger.info("  " + shift.getStart().toLocalDate()
          + " " + shift.getStart().toLocalTime()
          + " - " + shift.getEnd().toLocalTime()
          + ": " + shift.getEmployee().getName());
    }
}

输出结果示例：

班次分配结果
  2030-04-01 06:00 - 14:00: Carl
  2030-04-01 09:00 - 17:00: Ann
  2030-04-01 14:00 - 22:00: Beth
  2030-04-02 06:00 - 14:00: Beth
  2030-04-02 14:00 - 22:00: Ann

Ann 未被分配第一个班次，因为她不具备 服务员 技能。但为什么 Beth 也没被分配第一个班次？她有服务员技能啊。

如果 Beth 被分配到第一个班次，那么第二和第三个班次将无法分配——它们都需要调酒师，而 Carl 不行。只有当 Carl 被分配第一个班次时，才能得到可行解。在大型真实数据集中，这类复杂情况会更加棘手。把这些交给 Solver 处理吧。

6. 总结

Timefold Solver 框架为开发者提供了强大的工具，用于解决调度和资源分配等约束满足问题。它支持用代码（而非数学公式）编写自定义约束，使维护更友好。底层支持多种人工智能优化算法，可深度调优，但普通用户通常无需干预。

更多信息请参考 Timefold Solver 官方文档。

原始标题:A Guide to Timefold Solver for Employee Scheduling | Baeldung

« 上一篇： 处理 findFirst() 遇到首元素为 null 时的 NullPointerException
» 下一篇： Skip Bytes in InputStream in Java