• Spring Boot集成Timefold Solver实现课程表编排

    1. 什么是Timefold Solver？

    每个组织都面临规划问题：使用一组有限的资源（员工、资产、时间和金钱）提供产品或服务。Timefold Solver 优化了此类规划，以更少的资源开展更多业务。这被称为约束满足编程（属于运筹学学科的一部分）。

    Timefold Solver是一个轻量级、可嵌入的约束满足引擎，可优化规划问题。它解决了以下用例：

    • 员工轮班排班：安排护士、修理工等的时间
    • 议程安排：安排会议、约会、维护工作、广告等
    • 教育时间表：安排课程、课程、考试、会议演示等
    • 车辆路线：使用已知的地图工具规划车辆路线（卡车、火车、轮船、飞机等），以便将货物和/或乘客运送到多个目的地……
    • 装箱：用物品填充集装箱、卡车、轮船和仓库，同时也跨计算机资源打包信息，例如云计算……
    • 车间调度：汽车装配线规划、机器队列规划、劳动力任务规划……
    • 切割库存：切割纸张、钢材、地毯等时尽量减少浪费……
    • 体育赛事安排：规划足球联赛、棒球联赛等的比赛和训练日程……
    • 财务优化：投资组合优化、风险分散……

    useCaseOverview

    1.1什么是规划问题？

    whatIsAPlanningProblem

    规划问题具有基于有限资源和特定约束的最优目标。最优目标可以是任意数量的事物，例如：

    • 利润最大化——最佳目标带来最高的利润。
    • 最小化生态足迹——最佳目标是对环境的影响最小。
    • 最大限度地提高员工或客户的满意度——最佳目标优先考虑员工或客户的需求。

    实现这些目标的能力取决于可用资源的数量，例如：

    • 人的数量。
    • 多少时间。
    • 预算。
    • 实物资产，例如机械、车辆、计算机、建筑物等。

    还必须考虑与这些资源相关的具体限制，例如一个人的工作时间、他们使用某些机器的能力或设备之间的兼容性。

    Timefold Solver 可帮助 Java TM、Kotlin 和 Python 程序员高效地解决约束满足问题。在底层，它将优化启发式和元启发式与非常高效的分数计算相结合。

    1.2规划问题是 NP 完全问题还是 NP 难题

    所有上述用例可能是 NP-complete/NP-hard，用外行人的话来说就是：

    • 在合理的时间内验证问题的给定解决方案很容易。
    • 没有什么灵丹妙药可以在合理的时间内找到问题的最佳解决方案（*）。

    (*) 至少，世界上最聪明的计算机科学家还没有找到这样的灵丹妙药。但如果他们能找到一个解决 NP 完全问题的灵丹妙药，那么它就能解决所有 NP 完全问题。

    事实上，如果有人能证明这种灵丹妙药是否真的存在，就可以获得 1,000,000 美元的奖励。

    这意味着非常可怕的事情：解决你的问题可能比你想象的要难，因为两种常用的技术是不够的：

    • 暴力算法（即使是更智能的变体）也会花费太长时间。
    • 一种快速算法，例如在装箱中，首先放入最大的物品，将返回远非最优的解决方案。

    通过使用先进的优化算法，Timefold Solver 确实能够在合理的时间内为此类规划问题找到接近最优的解决方案。

    1.3. 规划问题有（硬和软）约束

    通常，规划问题至少有两个层次的约束：

    • （负面）硬约束不能被打破。例如：1 位老师不能同时教授 2 门不同的课程。
    • 如果可以避免，则不应打破（负面）软约束。例如： A 老师不喜欢在星期五下午上课。

    有些问题也有积极的约束：

    • 如果可能的话，应该满足积极的软约束（或奖励）。例如：B老师喜欢在周一早上上课。

    有些基本问题只有硬约束，有些问题有三级或更多级的约束——硬约束、中等约束和软约束。

    这些约束定义了规划问题的得分计算（又称适应度函数）。规划问题的每个解决方案都可以用分数来评分。 使用 Timefold Solver，问题可以在 Java TM、Kotlin 或 Python等语言中以面向对象范式建模。这样的代码简单、灵活且可扩展。

    1.4. 规划问题具有巨大的搜索空间

    规划问题有多种解决方案。解决方案有以下几类：

    • 任何解决方案都是可能的解决方案，无论它是否打破了多少限制。规划问题往往有大量的可能解决方案。其中许多解决方案毫无价值。
    • 可行解是指不打破任何（负面）硬约束的解。可行解的数量往往与可能解的数量有关。有时没有可行解。每个可行解都是一个可能解。
    • 最优解是得分最高的解。规划问题往往有 1 个或几个最优解。即使在没有可行解且最优解不可行的情况下，也总是至少有 1 个最优解。
    • 找到的最佳解决方案是实现在给定时间内找到的得分最高的解决方案。找到的最佳解决方案很可能是可行的，并且如果有足够的时间，它就是最优解决方案。

    与直觉相反的是，即使数据集很小，可能的解决方案数量也是巨大的（如果计算正确的话）。正如您在示例中看到的，大多数情况下的可能解决方案比已知宇宙中原子的最小数量（10^80）要多得多。由于没有灵丹妙药可以找到最佳解决方案，因此任何实现都必须评估所有这些可能解决方案的至少一个子集。

    Timefold Solver 支持多种优化算法，可高效地处理数量惊人的可能解决方案。根据用例，某些优化算法的性能优于其他算法，但无法提前知道。 使用 Timefold Solver，只需在几行代码中更改求解器配置，即可轻松切换优化算法。

    2.代码工程

    实验目的：

    实现课程表编排，Lesson实例分配给Timeslot和Room实例以遵守硬调度和软调度约束，例如以下示例：

    • 一个房间最多可以同时上一节课。
    • 一位老师最多可以同时讲授一节课。
    • 一名学生最多可同时参加一节课。
    • 一位老师喜欢在同一个教室里讲授所有课程。
    • 一位老师喜欢教授连续的课程并且不喜欢课程之间有间隙。
    • 学生不喜欢连续学习同一科目。

    从数学上讲，学校时间表是一个NP难题。这意味着它很难扩展。对于一个非平凡的数据集，简单地用蛮力迭代所有可能的组合需要数百万年的时间，即使在超级计算机上也是如此。幸运的是，Timefold Solver 等 AI 约束求解器拥有先进的算法，可以在合理的时间内提供接近最优的解决方案。

    pom.xml

    1. <?xml version="1.0" encoding="UTF-8"?>
    2. <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    3.          xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
    4.   <modelVersion>4.0.0</modelVersion>
    5.   <!-- Use spring boot parent to use its native profile -->
    6.   <parent>
    7.     <groupId>org.springframework.boot</groupId>
    8.     <artifactId>spring-boot-starter-parent</artifactId>
    9.     <version>3.2.1</version>
    10.   </parent>
    11.  
    12.   <groupId>org.acme</groupId>
    13.   <artifactId>spring-boot-school-timetabling</artifactId>
    14.   <version>1.0-SNAPSHOT</version>
    15.  
    16.   <properties>
    17.     <maven.compiler.release>17</maven.compiler.release>
    18.     <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    19.  
    20.     <version.ai.timefold.solver>1.10.0</version.ai.timefold.solver>
    21.     <version.org.springframework.boot>${project.parent.version}</version.org.springframework.boot>
    22.  
    23.     <version.compiler.plugin>3.13.0</version.compiler.plugin>
    24.     <version.surefire.plugin>3.2.5</version.surefire.plugin>
    25.   </properties>
    26.  
    27.   <dependencyManagement>
    28.     <dependencies>
    29.       <dependency>
    30.         <groupId>org.springframework.boot</groupId>
    31.         <artifactId>spring-boot-dependencies</artifactId>
    32.         <version>${version.org.springframework.boot}</version>
    33.         <type>pom</type>
    34.         <scope>import</scope>
    35.       </dependency>
    36.       <dependency>
    37.         <groupId>ai.timefold.solver</groupId>
    38.         <artifactId>timefold-solver-bom</artifactId>
    39.         <version>${version.ai.timefold.solver}</version>
    40.         <type>pom</type>
    41.         <scope>import</scope>
    42.       </dependency>
    43.     </dependencies>
    44.   </dependencyManagement>
    45.  
    46.   <dependencies>
    47.     <!-- Spring boot -->
    48.     <dependency>
    49.       <groupId>org.springframework.boot</groupId>
    50.       <artifactId>spring-boot-starter-web</artifactId>
    51.     </dependency>
    52.     <dependency>
    53.       <groupId>ai.timefold.solver</groupId>
    54.       <artifactId>timefold-solver-spring-boot-starter</artifactId>
    55.     </dependency>
    56.  
    57.     <!-- Swagger -->
    58.     <dependency>
    59.       <groupId>org.springdoc</groupId>
    60.       <artifactId>springdoc-openapi-starter-webmvc-ui</artifactId>
    61.       <version>2.5.0</version>
    62.     </dependency>
    63.  
    64.     <!-- Testing -->
    65.     <dependency>
    66.       <groupId>org.springframework.boot</groupId>
    67.       <artifactId>spring-boot-starter-test</artifactId>
    68.       <scope>test</scope>
    69.     </dependency>
    70.     <dependency>
    71.       <groupId>ai.timefold.solver</groupId>
    72.       <artifactId>timefold-solver-test</artifactId>
    73.       <scope>test</scope>
    74.     </dependency>
    75.     <dependency>
    76.       <groupId>org.springframework</groupId>
    77.       <artifactId>spring-webflux</artifactId>
    78.       <scope>test</scope>
    79.     </dependency>
    80.     <dependency>
    81.       <groupId>org.awaitility</groupId>
    82.       <artifactId>awaitility</artifactId>
    83.       <scope>test</scope>
    84.     </dependency>
    85.  
    86.     <!-- UI -->
    87.     <!-- No webjar locator; incompatible in native mode;
    88.          see https://github.com/spring-projects/spring-framework/issues/27619
    89.          and https://github.com/webjars/webjars-locator-core/issues/96
    90.      -->
    91.     <dependency>
    92.       <groupId>ai.timefold.solver</groupId>
    93.       <artifactId>timefold-solver-webui</artifactId>
    94.       <scope>runtime</scope>
    95.     </dependency>
    96.     <dependency>
    97.       <groupId>org.webjars</groupId>
    98.       <artifactId>bootstrap</artifactId>
    99.       <version>5.2.3</version>
    100.       <scope>runtime</scope>
    101.     </dependency>
    102.     <dependency>
    103.       <groupId>org.webjars</groupId>
    104.       <artifactId>jquery</artifactId>
    105.       <version>3.6.4</version>
    106.       <scope>runtime</scope>
    107.     </dependency>
    108.     <dependency>
    109.       <groupId>org.webjars</groupId>
    110.       <artifactId>font-awesome</artifactId>
    111.       <version>5.15.1</version>
    112.       <scope>runtime</scope>
    113.     </dependency>
    114.     <dependency>
    115.       <groupId>org.webjars.npm</groupId>
    116.       <artifactId>js-joda</artifactId>
    117.       <version>1.11.0</version>
    118.       <scope>runtime</scope>
    119.     </dependency>
    120.   </dependencies>
    121.  
    122.   <build>
    123.     <plugins>
    124.       <plugin>
    125.         <artifactId>maven-compiler-plugin</artifactId>
    126.         <version>${version.compiler.plugin}</version>
    127.       </plugin>
    128.       <plugin>
    129.         <artifactId>maven-surefire-plugin</artifactId>
    130.         <version>${version.surefire.plugin}</version>
    131.       </plugin>
    132.       <plugin>
    133.         <groupId>org.springframework.boot</groupId>
    134.         <artifactId>spring-boot-maven-plugin</artifactId>
    135.         <version>${version.org.springframework.boot}</version>
    136.         <executions>
    137.           <!-- Repackage the archive produced by maven-jar-plugin into an executable JAR file. -->
    138.           <execution>
    139.             <goals>
    140.               <goal>repackage</goal>
    141.             </goals>
    142.           </execution>
    143.         </executions>
    144.         <configuration>
    145.           <!-- optimizedLaunch disables the C2 compiler, which has a massive performance impact -->
    146.           <optimizedLaunch>false</optimizedLaunch>
    147.         </configuration>
    148.       </plugin>
    149.       <plugin>
    150.         <groupId>org.graalvm.buildtools</groupId>
    151.         <artifactId>native-maven-plugin</artifactId>
    152.       </plugin>
    153.     </plugins>
    154.   </build>
    155.  
    156. </project>

    时间段

    课程Timeslot代表授课的时间间隔，例如Monday 10:30 - 11:30或Tuesday 13:30 - 14:30。为简单起见，所有时间段的持续时间相同，午餐或其他休息期间没有时间段。

    1. package org.acme.schooltimetabling.domain;
    2.  
    3. import ai.timefold.solver.core.api.domain.lookup.PlanningId;
    4. import com.fasterxml.jackson.annotation.JsonIdentityInfo;
    5. import com.fasterxml.jackson.annotation.ObjectIdGenerators;
    6.  
    7. import java.time.DayOfWeek;
    8. import java.time.LocalTime;
    9.  
    10. @JsonIdentityInfo(scope = Timeslot.class, generator = ObjectIdGenerators.PropertyGenerator.class, property = "id")
    11. public class Timeslot {
    12.  
    13.     @PlanningId
    14.     private String id;
    15.  
    16.     private DayOfWeek dayOfWeek;
    17.     private LocalTime startTime;
    18.     private LocalTime endTime;
    19.  
    20.     public Timeslot() {
    21.     }
    22.  
    23.     public Timeslot(String id, DayOfWeek dayOfWeek, LocalTime startTime, LocalTime endTime) {
    24.         this.id = id;
    25.         this.dayOfWeek = dayOfWeek;
    26.         this.startTime = startTime;
    27.         this.endTime = endTime;
    28.     }
    29.  
    30.     public Timeslot(String id, DayOfWeek dayOfWeek, LocalTime startTime) {
    31.         this(id, dayOfWeek, startTime, startTime.plusMinutes(50));
    32.     }
    33.  
    34.     @Override
    35.     public String toString() {
    36.         return dayOfWeek + " " + startTime;
    37.     }
    38.  
    39.     // ************************************************************************
    40.     // Getters and setters
    41.     // ************************************************************************
    42.  
    43.     public String getId() {
    44.         return id;
    45.     }
    46.  
    47.     public DayOfWeek getDayOfWeek() {
    48.         return dayOfWeek;
    49.     }
    50.  
    51.     public LocalTime getStartTime() {
    52.         return startTime;
    53.     }
    54.  
    55.     public LocalTime getEndTime() {
    56.         return endTime;
    57.     }
    58. }

    房间

    教室Room代表授课地点，例如Room A或Room B。为简单起见，所有房间均无容量限制，可容纳所有课程。

    1. package org.acme.schooltimetabling.domain;
    2.  
    3. import ai.timefold.solver.core.api.domain.lookup.PlanningId;
    4. import com.fasterxml.jackson.annotation.JsonIdentityInfo;
    5. import com.fasterxml.jackson.annotation.ObjectIdGenerators;
    6.  
    7. @JsonIdentityInfo(scope = Room.class, generator = ObjectIdGenerators.PropertyGenerator.class, property = "id")
    8. public class Room {
    9.  
    10.     @PlanningId
    11.     private String id;
    12.  
    13.     private String name;
    14.  
    15.     public Room() {
    16.     }
    17.  
    18.     public Room(String id, String name) {
    19.         this.id = id;
    20.         this.name = name;
    21.     }
    22.  
    23.     @Override
    24.     public String toString() {
    25.         return name;
    26.     }
    27.  
    28.     // ************************************************************************
    29.     // Getters and setters
    30.     // ************************************************************************
    31.  
    32.     public String getId() {
    33.         return id;
    34.     }
    35.  
    36.     public String getName() {
    37.         return name;
    38.     }
    39. }

    课程

    在课堂上Lesson，一位老师向一组学生讲授一门课程，例如Math by A.Turing for 9th grade或Chemistry by M.Curie for 10th grade。如果同一老师每周向同一组学生讲授同一门课程多次，则存在多个Lesson实例，只能通过 来区分id。例如，9 年级每周有 6 节数学课。

    在解决过程中，Timefold Solver 会更改课程的timeslot和room字段Lesson，以将每节课分配到时间段和房间。由于 Timefold Solver 会更改这些字段，因此Lesson是一个规划实体：

    schoolTimetablingClassDiagramAnnotated

    1. package org.acme.schooltimetabling.domain;
    2.  
    3. import ai.timefold.solver.core.api.domain.entity.PlanningEntity;
    4. import ai.timefold.solver.core.api.domain.lookup.PlanningId;
    5. import ai.timefold.solver.core.api.domain.variable.PlanningVariable;
    6. import com.fasterxml.jackson.annotation.JsonIdentityReference;
    7.  
    8. @PlanningEntity
    9. public class Lesson {
    10.  
    11.     @PlanningId
    12.     private String id;
    13.  
    14.     private String subject;
    15.     private String teacher;
    16.     private String studentGroup;
    17.  
    18.     @JsonIdentityReference
    19.     @PlanningVariable
    20.     private Timeslot timeslot;
    21.  
    22.     @JsonIdentityReference
    23.     @PlanningVariable
    24.     private Room room;
    25.  
    26.     public Lesson() {
    27.     }
    28.  
    29.     public Lesson(String id, String subject, String teacher, String studentGroup) {
    30.         this.id = id;
    31.         this.subject = subject;
    32.         this.teacher = teacher;
    33.         this.studentGroup = studentGroup;
    34.     }
    35.  
    36.     public Lesson(String id, String subject, String teacher, String studentGroup, Timeslot timeslot, Room room) {
    37.         this(id, subject, teacher, studentGroup);
    38.         this.timeslot = timeslot;
    39.         this.room = room;
    40.     }
    41.  
    42.     @Override
    43.     public String toString() {
    44.         return subject + "(" + id + ")";
    45.     }
    46.  
    47.     // ************************************************************************
    48.     // Getters and setters
    49.     // ************************************************************************
    50.  
    51.     public String getId() {
    52.         return id;
    53.     }
    54.  
    55.     public String getSubject() {
    56.         return subject;
    57.     }
    58.  
    59.     public String getTeacher() {
    60.         return teacher;
    61.     }
    62.  
    63.     public String getStudentGroup() {
    64.         return studentGroup;
    65.     }
    66.  
    67.     public Timeslot getTimeslot() {
    68.         return timeslot;
    69.     }
    70.  
    71.     public void setTimeslot(Timeslot timeslot) {
    72.         this.timeslot = timeslot;
    73.     }
    74.  
    75.     public Room getRoom() {
    76.         return room;
    77.     }
    78.  
    79.     public void setRoom(Room room) {
    80.         this.room = room;
    81.     }
    82. }

    定义约束并计算分数

    分数代表特定解决方案的质量。分数越高越好。Timefold Solver 寻找最佳解决方案，即在可用时间内找到的得分最高的解决方案。它可能是最佳解决方案。

    由于此用例有硬约束和软约束，因此使用HardSoftScore类来表示分数：

    • 不能打破硬性约束。例如：一个房间最多只能同时上一节课。
    • 软约束不能被打破。例如：老师喜欢在单人教室上课。

    硬约束相对于其他硬约束具有权重。软约束相对于其他软约束也具有权重。 无论各自的权重如何，硬约束总是比软约束更重要。

    1. package org.acme.schooltimetabling.solver;
    2.  
    3. import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
    4. import ai.timefold.solver.core.api.score.stream.Constraint;
    5. import ai.timefold.solver.core.api.score.stream.ConstraintFactory;
    6. import ai.timefold.solver.core.api.score.stream.ConstraintProvider;
    7. import ai.timefold.solver.core.api.score.stream.Joiners;
    8. import org.acme.schooltimetabling.domain.Lesson;
    9. import org.acme.schooltimetabling.solver.justifications.*;
    10.  
    11. import java.time.Duration;
    12.  
    13. public class TimetableConstraintProvider implements ConstraintProvider {
    14.  
    15.     @Override
    16.     public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
    17.         return new Constraint[] {
    18.                 // Hard constraints
    19.                 roomConflict(constraintFactory),
    20.                 teacherConflict(constraintFactory),
    21.                 studentGroupConflict(constraintFactory),
    22.                 // Soft constraints
    23.                 teacherRoomStability(constraintFactory),
    24.                 teacherTimeEfficiency(constraintFactory),
    25.                 studentGroupSubjectVariety(constraintFactory)
    26.         };
    27.     }
    28.  
    29.     Constraint roomConflict(ConstraintFactory constraintFactory) {
    30.         // A room can accommodate at most one lesson at the same time.
    31.         return constraintFactory
    32.                 // Select each pair of 2 different lessons ...
    33.                 .forEachUniquePair(Lesson.class,
    34.                         // ... in the same timeslot ...
    35.                         Joiners.equal(Lesson::getTimeslot),
    36.                         // ... in the same room ...
    37.                         Joiners.equal(Lesson::getRoom))
    38.                 // ... and penalize each pair with a hard weight.
    39.                 .penalize(HardSoftScore.ONE_HARD)
    40.                 .justifyWith((lesson1, lesson2, score) -> new RoomConflictJustification(lesson1.getRoom(), lesson1, lesson2))
    41.                 .asConstraint("Room conflict");
    42.     }
    43.  
    44.     Constraint teacherConflict(ConstraintFactory constraintFactory) {
    45.         // A teacher can teach at most one lesson at the same time.
    46.         return constraintFactory
    47.                 .forEachUniquePair(Lesson.class,
    48.                         Joiners.equal(Lesson::getTimeslot),
    49.                         Joiners.equal(Lesson::getTeacher))
    50.                 .penalize(HardSoftScore.ONE_HARD)
    51.                 .justifyWith(
    52.                         (lesson1, lesson2, score) -> new TeacherConflictJustification(lesson1.getTeacher(), lesson1, lesson2))
    53.                 .asConstraint("Teacher conflict");
    54.     }
    55.  
    56.     Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
    57.         // A student can attend at most one lesson at the same time.
    58.         return constraintFactory
    59.                 .forEachUniquePair(Lesson.class,
    60.                         Joiners.equal(Lesson::getTimeslot),
    61.                         Joiners.equal(Lesson::getStudentGroup))
    62.                 .penalize(HardSoftScore.ONE_HARD)
    63.                 .justifyWith((lesson1, lesson2, score) -> new StudentGroupConflictJustification(lesson1.getStudentGroup(), lesson1, lesson2))
    64.                 .asConstraint("Student group conflict");
    65.     }
    66.  
    67.     Constraint teacherRoomStability(ConstraintFactory constraintFactory) {
    68.         // A teacher prefers to teach in a single room.
    69.         return constraintFactory
    70.                 .forEachUniquePair(Lesson.class,
    71.                         Joiners.equal(Lesson::getTeacher))
    72.                 .filter((lesson1, lesson2) -> lesson1.getRoom() != lesson2.getRoom())
    73.                 .penalize(HardSoftScore.ONE_SOFT)
    74.                 .justifyWith((lesson1, lesson2, score) -> new TeacherRoomStabilityJustification(lesson1.getTeacher(), lesson1, lesson2))
    75.                 .asConstraint("Teacher room stability");
    76.     }
    77.  
    78.     Constraint teacherTimeEfficiency(ConstraintFactory constraintFactory) {
    79.         // A teacher prefers to teach sequential lessons and dislikes gaps between lessons.
    80.         return constraintFactory
    81.                 .forEach(Lesson.class)
    82.                 .join(Lesson.class, Joiners.equal(Lesson::getTeacher),
    83.                         Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek()))
    84.                 .filter((lesson1, lesson2) -> {
    85.                     Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),
    86.                             lesson2.getTimeslot().getStartTime());
    87.                     return !between.isNegative() && between.compareTo(Duration.ofMinutes(30)) <= 0;
    88.                 })
    89.                 .reward(HardSoftScore.ONE_SOFT)
    90.                 .justifyWith((lesson1, lesson2, score) -> new TeacherTimeEfficiencyJustification(lesson1.getTeacher(), lesson1, lesson2))
    91.                 .asConstraint("Teacher time efficiency");
    92.     }
    93.  
    94.     Constraint studentGroupSubjectVariety(ConstraintFactory constraintFactory) {
    95.         // A student group dislikes sequential lessons on the same subject.
    96.         return constraintFactory
    97.                 .forEach(Lesson.class)
    98.                 .join(Lesson.class,
    99.                         Joiners.equal(Lesson::getSubject),
    100.                         Joiners.equal(Lesson::getStudentGroup),
    101.                         Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek()))
    102.                 .filter((lesson1, lesson2) -> {
    103.                     Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),
    104.                             lesson2.getTimeslot().getStartTime());
    105.                     return !between.isNegative() && between.compareTo(Duration.ofMinutes(30)) <= 0;
    106.                 })
    107.                 .penalize(HardSoftScore.ONE_SOFT)
    108.                 .justifyWith((lesson1, lesson2, score) -> new StudentGroupSubjectVarietyJustification(lesson1.getStudentGroup(), lesson1, lesson2))
    109.                 .asConstraint("Student group subject variety");
    110.     }
    111.  
    112. }

    在规划解决方案中收集领域对象

    ATimetable包装单个数据集的所有Timeslot、Room和实例。此外，由于它包含所有课程，每个课程都有特定的规划变量状态，因此它是一个规划解决方案，并且具有分数：Lesson

    • 如果课程仍未分配，那么它就是一个未初始化的解决方案，例如分数为 的解决方案-4init/0hard/0soft。
    • 如果它打破了硬约束，那么它就是一个不可行的解决方案，例如得分为 的解决方案-2hard/-3soft。
    • 如果它遵守所有硬性约束，那么它就是一个可行的解决方案，例如分数为 的解决方案0hard/-7soft。
    1. package org.acme.schooltimetabling.domain;
    2.  
    3. import ai.timefold.solver.core.api.domain.solution.PlanningEntityCollectionProperty;
    4. import ai.timefold.solver.core.api.domain.solution.PlanningScore;
    5. import ai.timefold.solver.core.api.domain.solution.PlanningSolution;
    6. import ai.timefold.solver.core.api.domain.solution.ProblemFactCollectionProperty;
    7. import ai.timefold.solver.core.api.domain.valuerange.ValueRangeProvider;
    8. import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
    9. import ai.timefold.solver.core.api.solver.SolverStatus;
    10.  
    11. import java.util.List;
    12.  
    13. @PlanningSolution
    14. public class Timetable {
    15.  
    16.     private String name;
    17.  
    18.     @ProblemFactCollectionProperty
    19.     @ValueRangeProvider
    20.     private List<Timeslot> timeslots;
    21.     @ProblemFactCollectionProperty
    22.     @ValueRangeProvider
    23.     private List<Room> rooms;
    24.     @PlanningEntityCollectionProperty
    25.     private List<Lesson> lessons;
    26.  
    27.     @PlanningScore
    28.     private HardSoftScore score;
    29.  
    30.     // Ignored by Timefold, used by the UI to display solve or stop solving button
    31.     private SolverStatus solverStatus;
    32.  
    33.     // No-arg constructor required for Timefold
    34.     public Timetable() {
    35.     }
    36.  
    37.     public Timetable(String name, HardSoftScore score, SolverStatus solverStatus) {
    38.         this.name = name;
    39.         this.score = score;
    40.         this.solverStatus = solverStatus;
    41.     }
    42.  
    43.     public Timetable(String name, List<Timeslot> timeslots, List<Room> rooms, List<Lesson> lessons) {
    44.         this.name = name;
    45.         this.timeslots = timeslots;
    46.         this.rooms = rooms;
    47.         this.lessons = lessons;
    48.     }
    49.  
    50.     // ************************************************************************
    51.     // Getters and setters
    52.     // ************************************************************************
    53.  
    54.     public String getName() {
    55.         return name;
    56.     }
    57.  
    58.     public List<Timeslot> getTimeslots() {
    59.         return timeslots;
    60.     }
    61.  
    62.     public List<Room> getRooms() {
    63.         return rooms;
    64.     }
    65.  
    66.     public List<Lesson> getLessons() {
    67.         return lessons;
    68.     }
    69.  
    70.     public HardSoftScore getScore() {
    71.         return score;
    72.     }
    73.  
    74.     public SolverStatus getSolverStatus() {
    75.         return solverStatus;
    76.     }
    77.  
    78.     public void setSolverStatus(SolverStatus solverStatus) {
    79.         this.solverStatus = solverStatus;
    80.     }
    81.  
    82. }

    controller

    1. package org.acme.schooltimetabling.rest;
    2.  
    3. import java.util.Collection;
    4. import java.util.UUID;
    5. import java.util.concurrent.ConcurrentHashMap;
    6. import java.util.concurrent.ConcurrentMap;
    7.  
    8. import ai.timefold.solver.core.api.score.analysis.ScoreAnalysis;
    9. import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
    10. import ai.timefold.solver.core.api.solver.ScoreAnalysisFetchPolicy;
    11. import ai.timefold.solver.core.api.solver.SolutionManager;
    12. import ai.timefold.solver.core.api.solver.SolverManager;
    13. import ai.timefold.solver.core.api.solver.SolverStatus;
    14.  
    15. import org.acme.schooltimetabling.domain.Timetable;
    16. import org.acme.schooltimetabling.rest.exception.ErrorInfo;
    17. import org.acme.schooltimetabling.rest.exception.TimetableSolverException;
    18. import org.acme.schooltimetabling.solver.justifications.RoomConflictJustification;
    19. import org.acme.schooltimetabling.solver.justifications.StudentGroupConflictJustification;
    20. import org.acme.schooltimetabling.solver.justifications.StudentGroupSubjectVarietyJustification;
    21. import org.acme.schooltimetabling.solver.justifications.TeacherConflictJustification;
    22. import org.acme.schooltimetabling.solver.justifications.TeacherRoomStabilityJustification;
    23. import org.acme.schooltimetabling.solver.justifications.TeacherTimeEfficiencyJustification;
    24. import org.slf4j.Logger;
    25. import org.slf4j.LoggerFactory;
    26. import org.springframework.aot.hint.annotation.RegisterReflectionForBinding;
    27. import org.springframework.http.HttpStatus;
    28. import org.springframework.http.MediaType;
    29. import org.springframework.web.bind.annotation.DeleteMapping;
    30. import org.springframework.web.bind.annotation.GetMapping;
    31. import org.springframework.web.bind.annotation.PathVariable;
    32. import org.springframework.web.bind.annotation.PostMapping;
    33. import org.springframework.web.bind.annotation.PutMapping;
    34. import org.springframework.web.bind.annotation.RequestBody;
    35. import org.springframework.web.bind.annotation.RequestMapping;
    36. import org.springframework.web.bind.annotation.RequestParam;
    37. import org.springframework.web.bind.annotation.RestController;
    38.  
    39. import io.swagger.v3.oas.annotations.Operation;
    40. import io.swagger.v3.oas.annotations.Parameter;
    41. import io.swagger.v3.oas.annotations.media.Content;
    42. import io.swagger.v3.oas.annotations.media.Schema;
    43. import io.swagger.v3.oas.annotations.responses.ApiResponse;
    44. import io.swagger.v3.oas.annotations.responses.ApiResponses;
    45. import io.swagger.v3.oas.annotations.tags.Tag;
    46.  
    47. @Tag(name = "School Timetables", description = "School timetable service assigning lessons to rooms and timeslots.")
    48. @RestController
    49. @RequestMapping("/timetables")
    50. public class TimetableController {
    51.  
    52.     private static final Logger LOGGER = LoggerFactory.getLogger(TimetableController.class);
    53.  
    54.     private final SolverManager<Timetable, String> solverManager;
    55.     private final SolutionManager<Timetable, HardSoftScore> solutionManager;
    56.  
    57.     // TODO: Without any "time to live", the map may eventually grow out of memory.
    58.     private final ConcurrentMap<String, Job> jobIdToJob = new ConcurrentHashMap<>();
    59.  
    60.     public TimetableController(SolverManager<Timetable, String> solverManager,
    61.             SolutionManager<Timetable, HardSoftScore> solutionManager) {
    62.         this.solverManager = solverManager;
    63.         this.solutionManager = solutionManager;
    64.     }
    65.  
    66.     @Operation(summary = "List the job IDs of all submitted timetables.")
    67.     @ApiResponses(value = {
    68.             @ApiResponse(responseCode = "200", description = "List of all job IDs.",
    69.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    70.                             schema = @Schema(type = "array", implementation = String.class))) })
    71.     @GetMapping
    72.     public Collection<String> list() {
    73.         return jobIdToJob.keySet();
    74.     }
    75.  
    76.     @Operation(summary = "Submit a timetable to start solving as soon as CPU resources are available.")
    77.     @ApiResponses(value = {
    78.             @ApiResponse(responseCode = "202",
    79.                     description = "The job ID. Use that ID to get the solution with the other methods.",
    80.                     content = @Content(mediaType = MediaType.TEXT_PLAIN_VALUE,
    81.                             schema = @Schema(implementation = String.class))) })
    82.     @PostMapping(consumes = MediaType.APPLICATION_JSON_VALUE, produces = MediaType.TEXT_PLAIN_VALUE)
    83.     public String solve(@RequestBody Timetable problem) {
    84.         String jobId = UUID.randomUUID().toString();
    85.         jobIdToJob.put(jobId, Job.ofTimetable(problem));
    86.         solverManager.solveBuilder()
    87.                 .withProblemId(jobId)
    88.                 .withProblemFinder(jobId_ -> jobIdToJob.get(jobId).timetable)
    89.                 .withBestSolutionConsumer(solution -> jobIdToJob.put(jobId, Job.ofTimetable(solution)))
    90.                 .withExceptionHandler((jobId_, exception) -> {
    91.                     jobIdToJob.put(jobId, Job.ofException(exception));
    92.                     LOGGER.error("Failed solving jobId ({}).", jobId, exception);
    93.                 })
    94.                 .run();
    95.         return jobId;
    96.     }
    97.  
    98.     @Operation(summary = "Submit a timetable to analyze its score.")
    99.     @ApiResponses(value = {
    100.             @ApiResponse(responseCode = "202",
    101.                     description = "Resulting score analysis, optionally without constraint matches.",
    102.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    103.                             schema = @Schema(implementation = ScoreAnalysis.class))) })
    104.     @PutMapping(value = "/analyze", consumes = MediaType.APPLICATION_JSON_VALUE, produces = MediaType.APPLICATION_JSON_VALUE)
    105.     @RegisterReflectionForBinding({
    106.             RoomConflictJustification.class,
    107.             StudentGroupConflictJustification.class,
    108.             StudentGroupSubjectVarietyJustification.class,
    109.             TeacherConflictJustification.class,
    110.             TeacherRoomStabilityJustification.class,
    111.             TeacherTimeEfficiencyJustification.class
    112.     })
    113.     public ScoreAnalysis<HardSoftScore> analyze(@RequestBody Timetable problem,
    114.             @RequestParam(name = "fetchPolicy", required = false) ScoreAnalysisFetchPolicy fetchPolicy) {
    115.         return fetchPolicy == null ? solutionManager.analyze(problem) : solutionManager.analyze(problem, fetchPolicy);
    116.     }
    117.  
    118.     @Operation(
    119.             summary = "Get the solution and score for a given job ID. This is the best solution so far, as it might still be running or not even started.")
    120.     @ApiResponses(value = {
    121.             @ApiResponse(responseCode = "200", description = "The best solution of the timetable so far.",
    122.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    123.                             schema = @Schema(implementation = Timetable.class))),
    124.             @ApiResponse(responseCode = "404", description = "No timetable found.",
    125.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    126.                             schema = @Schema(implementation = ErrorInfo.class))),
    127.             @ApiResponse(responseCode = "500", description = "Exception during solving a timetable.",
    128.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    129.                             schema = @Schema(implementation = ErrorInfo.class)))
    130.     })
    131.  
    132.     @GetMapping(value = "/{jobId}", produces = MediaType.APPLICATION_JSON_VALUE)
    133.     public Timetable getTimeTable(
    134.             @Parameter(description = "The job ID returned by the POST method.") @PathVariable("jobId") String jobId) {
    135.         Timetable timetable = getTimetableAndCheckForExceptions(jobId);
    136.         SolverStatus solverStatus = solverManager.getSolverStatus(jobId);
    137.         timetable.setSolverStatus(solverStatus);
    138.         return timetable;
    139.     }
    140.  
    141.     @Operation(
    142.             summary = "Get the timetable status and score for a given job ID.")
    143.     @ApiResponses(value = {
    144.             @ApiResponse(responseCode = "200", description = "The timetable status and the best score so far.",
    145.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    146.                             schema = @Schema(implementation = Timetable.class))),
    147.             @ApiResponse(responseCode = "404", description = "No timetable found.",
    148.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    149.                             schema = @Schema(implementation = ErrorInfo.class))),
    150.             @ApiResponse(responseCode = "500", description = "Exception during solving a timetable.",
    151.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    152.                             schema = @Schema(implementation = ErrorInfo.class)))
    153.     })
    154.     @GetMapping(value = "/{jobId}/status", produces = MediaType.APPLICATION_JSON_VALUE)
    155.     public Timetable getStatus(
    156.             @Parameter(description = "The job ID returned by the POST method.") @PathVariable("jobId") String jobId) {
    157.         Timetable timetable = getTimetableAndCheckForExceptions(jobId);
    158.         SolverStatus solverStatus = solverManager.getSolverStatus(jobId);
    159.         return new Timetable(timetable.getName(), timetable.getScore(), solverStatus);
    160.     }
    161.  
    162.     private Timetable getTimetableAndCheckForExceptions(String jobId) {
    163.         Job job = jobIdToJob.get(jobId);
    164.         if (job == null) {
    165.             throw new TimetableSolverException(jobId, HttpStatus.NOT_FOUND, "No timetable found.");
    166.         }
    167.         if (job.exception != null) {
    168.             throw new TimetableSolverException(jobId, job.exception);
    169.         }
    170.         return job.timetable;
    171.     }
    172.  
    173.     @Operation(
    174.             summary = "Terminate solving for a given job ID. Returns the best solution of the timetable so far, as it might still be running or not even started.")
    175.     @ApiResponses(value = {
    176.             @ApiResponse(responseCode = "200", description = "The best solution of the timetable so far.",
    177.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    178.                             schema = @Schema(implementation = Timetable.class))),
    179.             @ApiResponse(responseCode = "404", description = "No timetable found.",
    180.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    181.                             schema = @Schema(implementation = ErrorInfo.class))),
    182.             @ApiResponse(responseCode = "500", description = "Exception during solving a timetable.",
    183.                     content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,
    184.                             schema = @Schema(implementation = ErrorInfo.class)))
    185.     })
    186.     @DeleteMapping(value = "/{jobId}", produces = MediaType.APPLICATION_JSON_VALUE)
    187.     public Timetable terminateSolving(
    188.             @Parameter(description = "The job ID returned by the POST method.") @PathVariable("jobId") String jobId) {
    189.         // TODO: Replace with .terminateEarlyAndWait(... [, timeout]); see https://github.com/TimefoldAI/timefold-solver/issues/77
    190.         solverManager.terminateEarly(jobId);
    191.         return getTimeTable(jobId);
    192.     }
    193.  
    194.     private record Job(Timetable timetable, Throwable exception) {
    195.  
    196.         static Job ofTimetable(Timetable timetable) {
    197.             return new Job(timetable, null);
    198.         }
    199.  
    200.         static Job ofException(Throwable error) {
    201.             return new Job(null, error);
    202.         }
    203.     }
    204. }

    设置终止时间

    如果没有终止设置或terminationEarly()事件，求解器将永远运行。为避免这种情况，请将求解时间限制为五秒。这足够短，可以避免 HTTP 超时。

    创建src/main/resources/application.properties文件：

    1. # The solver runs only for 5 seconds to avoid a HTTP timeout in this simple implementation.
    2. # It's recommended to run for at least 5 minutes ("5m") otherwise.
    3. timefold.solver.termination.spent-limit=5s

    Timefold Solver 返回在可用终止时间内找到的最佳解决方案。由于NP-hard 问题的性质，最佳解决方案可能不是最优的，尤其是对于较大的数据集。增加终止时间可能会找到更好的解决方案。

    以上只是一些关键代码，所有代码请参见下面代码仓库

    代码仓库

    3.测试

    启动Spring Boot应用程序

    时间表生成

    访问http://127.0.0.1:8080/，点击solve

    111

    4.引用

  • 相关阅读:
    【华为OD题库-027】代码编辑器-java
    大热电视剧《好事成双》里的IT故事：用户数据泄露事件引出的美女黑客
    ZYNQ7000交叉编译MPlayer到开发板播放视频
    （SpringBoot）第八章：SpringMVC程序开发
    c#学习系列相关之多线程（三）----invoke和begininvoke
    图论08-图的建模-状态的表达与理解 - 倒水问题为例
    CSS画一条虚线,并且灵活设置虚线的宽度和虚线之间的间隔和虚线的颜色
    acwing算法提高之数据结构--树状数组
    Flutter 调用百度地图APP实现位置搜索、路线规划
    如何在C程序中使用libcurl库下载网页内容
  • 原文地址：https://blog.csdn.net/dot_life/article/details/139668653