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

server/2024/9/25 17:17:08/

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

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd"><modelVersion>4.0.0</modelVersion><!-- Use spring boot parent to use its native profile --><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>3.2.1</version></parent><groupId>org.acme</groupId><artifactId>spring-boot-school-timetabling</artifactId><version>1.0-SNAPSHOT</version><properties><maven.compiler.release>17</maven.compiler.release><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><version.ai.timefold.solver>1.10.0</version.ai.timefold.solver><version.org.springframework.boot>${project.parent.version}</version.org.springframework.boot><version.compiler.plugin>3.13.0</version.compiler.plugin><version.surefire.plugin>3.2.5</version.surefire.plugin></properties><dependencyManagement><dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-dependencies</artifactId><version>${version.org.springframework.boot}</version><type>pom</type><scope>import</scope></dependency><dependency><groupId>ai.timefold.solver</groupId><artifactId>timefold-solver-bom</artifactId><version>${version.ai.timefold.solver}</version><type>pom</type><scope>import</scope></dependency></dependencies></dependencyManagement><dependencies><!-- Spring boot --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><dependency><groupId>ai.timefold.solver</groupId><artifactId>timefold-solver-spring-boot-starter</artifactId></dependency><!-- Swagger --><dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-starter-webmvc-ui</artifactId><version>2.5.0</version></dependency><!-- Testing --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scope>test</scope></dependency><dependency><groupId>ai.timefold.solver</groupId><artifactId>timefold-solver-test</artifactId><scope>test</scope></dependency><dependency><groupId>org.springframework</groupId><artifactId>spring-webflux</artifactId><scope>test</scope></dependency><dependency><groupId>org.awaitility</groupId><artifactId>awaitility</artifactId><scope>test</scope></dependency><!-- UI --><!-- No webjar locator; incompatible in native mode;see https://github.com/spring-projects/spring-framework/issues/27619and https://github.com/webjars/webjars-locator-core/issues/96--><dependency><groupId>ai.timefold.solver</groupId><artifactId>timefold-solver-webui</artifactId><scope>runtime</scope></dependency><dependency><groupId>org.webjars</groupId><artifactId>bootstrap</artifactId><version>5.2.3</version><scope>runtime</scope></dependency><dependency><groupId>org.webjars</groupId><artifactId>jquery</artifactId><version>3.6.4</version><scope>runtime</scope></dependency><dependency><groupId>org.webjars</groupId><artifactId>font-awesome</artifactId><version>5.15.1</version><scope>runtime</scope></dependency><dependency><groupId>org.webjars.npm</groupId><artifactId>js-joda</artifactId><version>1.11.0</version><scope>runtime</scope></dependency></dependencies><build><plugins><plugin><artifactId>maven-compiler-plugin</artifactId><version>${version.compiler.plugin}</version></plugin><plugin><artifactId>maven-surefire-plugin</artifactId><version>${version.surefire.plugin}</version></plugin><plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-plugin</artifactId><version>${version.org.springframework.boot}</version><executions><!-- Repackage the archive produced by maven-jar-plugin into an executable JAR file. --><execution><goals><goal>repackage</goal></goals></execution></executions><configuration><!-- optimizedLaunch disables the C2 compiler, which has a massive performance impact --><optimizedLaunch>false</optimizedLaunch></configuration></plugin><plugin><groupId>org.graalvm.buildtools</groupId><artifactId>native-maven-plugin</artifactId></plugin></plugins></build></project>

时间段

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

package org.acme.schooltimetabling.domain;import ai.timefold.solver.core.api.domain.lookup.PlanningId;
import com.fasterxml.jackson.annotation.JsonIdentityInfo;
import com.fasterxml.jackson.annotation.ObjectIdGenerators;import java.time.DayOfWeek;
import java.time.LocalTime;@JsonIdentityInfo(scope = Timeslot.class, generator = ObjectIdGenerators.PropertyGenerator.class, property = "id")
public class Timeslot {@PlanningIdprivate String id;private DayOfWeek dayOfWeek;private LocalTime startTime;private LocalTime endTime;public Timeslot() {}public Timeslot(String id, DayOfWeek dayOfWeek, LocalTime startTime, LocalTime endTime) {this.id = id;this.dayOfWeek = dayOfWeek;this.startTime = startTime;this.endTime = endTime;}public Timeslot(String id, DayOfWeek dayOfWeek, LocalTime startTime) {this(id, dayOfWeek, startTime, startTime.plusMinutes(50));}@Overridepublic String toString() {return dayOfWeek + " " + startTime;}// ************************************************************************// Getters and setters// ************************************************************************public String getId() {return id;}public DayOfWeek getDayOfWeek() {return dayOfWeek;}public LocalTime getStartTime() {return startTime;}public LocalTime getEndTime() {return endTime;}
}

房间

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

package org.acme.schooltimetabling.domain;import ai.timefold.solver.core.api.domain.lookup.PlanningId;
import com.fasterxml.jackson.annotation.JsonIdentityInfo;
import com.fasterxml.jackson.annotation.ObjectIdGenerators;@JsonIdentityInfo(scope = Room.class, generator = ObjectIdGenerators.PropertyGenerator.class, property = "id")
public class Room {@PlanningIdprivate String id;private String name;public Room() {}public Room(String id, String name) {this.id = id;this.name = name;}@Overridepublic String toString() {return name;}// ************************************************************************// Getters and setters// ************************************************************************public String getId() {return id;}public String getName() {return name;}
}

课程

在课堂上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

package org.acme.schooltimetabling.domain;import ai.timefold.solver.core.api.domain.entity.PlanningEntity;
import ai.timefold.solver.core.api.domain.lookup.PlanningId;
import ai.timefold.solver.core.api.domain.variable.PlanningVariable;
import com.fasterxml.jackson.annotation.JsonIdentityReference;@PlanningEntity
public class Lesson {@PlanningIdprivate String id;private String subject;private String teacher;private String studentGroup;@JsonIdentityReference@PlanningVariableprivate Timeslot timeslot;@JsonIdentityReference@PlanningVariableprivate Room room;public Lesson() {}public Lesson(String id, String subject, String teacher, String studentGroup) {this.id = id;this.subject = subject;this.teacher = teacher;this.studentGroup = studentGroup;}public Lesson(String id, String subject, String teacher, String studentGroup, Timeslot timeslot, Room room) {this(id, subject, teacher, studentGroup);this.timeslot = timeslot;this.room = room;}@Overridepublic String toString() {return subject + "(" + id + ")";}// ************************************************************************// Getters and setters// ************************************************************************public String getId() {return id;}public String getSubject() {return subject;}public String getTeacher() {return teacher;}public String getStudentGroup() {return studentGroup;}public Timeslot getTimeslot() {return timeslot;}public void setTimeslot(Timeslot timeslot) {this.timeslot = timeslot;}public Room getRoom() {return room;}public void setRoom(Room room) {this.room = room;}
}

定义约束并计算分数

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

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

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

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

package org.acme.schooltimetabling.solver;import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
import ai.timefold.solver.core.api.score.stream.Constraint;
import ai.timefold.solver.core.api.score.stream.ConstraintFactory;
import ai.timefold.solver.core.api.score.stream.ConstraintProvider;
import ai.timefold.solver.core.api.score.stream.Joiners;
import org.acme.schooltimetabling.domain.Lesson;
import org.acme.schooltimetabling.solver.justifications.*;import java.time.Duration;public class TimetableConstraintProvider implements ConstraintProvider {@Overridepublic Constraint[] defineConstraints(ConstraintFactory constraintFactory) {return new Constraint[] {// Hard constraintsroomConflict(constraintFactory),teacherConflict(constraintFactory),studentGroupConflict(constraintFactory),// Soft constraintsteacherRoomStability(constraintFactory),teacherTimeEfficiency(constraintFactory),studentGroupSubjectVariety(constraintFactory)};}Constraint roomConflict(ConstraintFactory constraintFactory) {// A room can accommodate at most one lesson at the same time.return constraintFactory// Select each pair of 2 different lessons ....forEachUniquePair(Lesson.class,// ... in the same timeslot ...Joiners.equal(Lesson::getTimeslot),// ... in the same room ...Joiners.equal(Lesson::getRoom))// ... and penalize each pair with a hard weight..penalize(HardSoftScore.ONE_HARD).justifyWith((lesson1, lesson2, score) -> new RoomConflictJustification(lesson1.getRoom(), lesson1, lesson2)).asConstraint("Room conflict");}Constraint teacherConflict(ConstraintFactory constraintFactory) {// A teacher can teach at most one lesson at the same time.return constraintFactory.forEachUniquePair(Lesson.class,Joiners.equal(Lesson::getTimeslot),Joiners.equal(Lesson::getTeacher)).penalize(HardSoftScore.ONE_HARD).justifyWith((lesson1, lesson2, score) -> new TeacherConflictJustification(lesson1.getTeacher(), lesson1, lesson2)).asConstraint("Teacher conflict");}Constraint studentGroupConflict(ConstraintFactory constraintFactory) {// A student can attend at most one lesson at the same time.return constraintFactory.forEachUniquePair(Lesson.class,Joiners.equal(Lesson::getTimeslot),Joiners.equal(Lesson::getStudentGroup)).penalize(HardSoftScore.ONE_HARD).justifyWith((lesson1, lesson2, score) -> new StudentGroupConflictJustification(lesson1.getStudentGroup(), lesson1, lesson2)).asConstraint("Student group conflict");}Constraint teacherRoomStability(ConstraintFactory constraintFactory) {// A teacher prefers to teach in a single room.return constraintFactory.forEachUniquePair(Lesson.class,Joiners.equal(Lesson::getTeacher)).filter((lesson1, lesson2) -> lesson1.getRoom() != lesson2.getRoom()).penalize(HardSoftScore.ONE_SOFT).justifyWith((lesson1, lesson2, score) -> new TeacherRoomStabilityJustification(lesson1.getTeacher(), lesson1, lesson2)).asConstraint("Teacher room stability");}Constraint teacherTimeEfficiency(ConstraintFactory constraintFactory) {// A teacher prefers to teach sequential lessons and dislikes gaps between lessons.return constraintFactory.forEach(Lesson.class).join(Lesson.class, Joiners.equal(Lesson::getTeacher),Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek())).filter((lesson1, lesson2) -> {Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),lesson2.getTimeslot().getStartTime());return !between.isNegative() && between.compareTo(Duration.ofMinutes(30)) <= 0;}).reward(HardSoftScore.ONE_SOFT).justifyWith((lesson1, lesson2, score) -> new TeacherTimeEfficiencyJustification(lesson1.getTeacher(), lesson1, lesson2)).asConstraint("Teacher time efficiency");}Constraint studentGroupSubjectVariety(ConstraintFactory constraintFactory) {// A student group dislikes sequential lessons on the same subject.return constraintFactory.forEach(Lesson.class).join(Lesson.class,Joiners.equal(Lesson::getSubject),Joiners.equal(Lesson::getStudentGroup),Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek())).filter((lesson1, lesson2) -> {Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),lesson2.getTimeslot().getStartTime());return !between.isNegative() && between.compareTo(Duration.ofMinutes(30)) <= 0;}).penalize(HardSoftScore.ONE_SOFT).justifyWith((lesson1, lesson2, score) -> new StudentGroupSubjectVarietyJustification(lesson1.getStudentGroup(), lesson1, lesson2)).asConstraint("Student group subject variety");}}

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

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

  • 如果课程仍未分配，那么它就是一个未初始化的解决方案，例如分数为 的解决方案-4init/0hard/0soft。
  • 如果它打破了硬约束，那么它就是一个不可行的解决方案，例如得分为 的解决方案-2hard/-3soft。
  • 如果它遵守所有硬性约束，那么它就是一个可行的解决方案，例如分数为 的解决方案0hard/-7soft。
package org.acme.schooltimetabling.domain;import ai.timefold.solver.core.api.domain.solution.PlanningEntityCollectionProperty;
import ai.timefold.solver.core.api.domain.solution.PlanningScore;
import ai.timefold.solver.core.api.domain.solution.PlanningSolution;
import ai.timefold.solver.core.api.domain.solution.ProblemFactCollectionProperty;
import ai.timefold.solver.core.api.domain.valuerange.ValueRangeProvider;
import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
import ai.timefold.solver.core.api.solver.SolverStatus;import java.util.List;@PlanningSolution
public class Timetable {private String name;@ProblemFactCollectionProperty@ValueRangeProviderprivate List<Timeslot> timeslots;@ProblemFactCollectionProperty@ValueRangeProviderprivate List<Room> rooms;@PlanningEntityCollectionPropertyprivate List<Lesson> lessons;@PlanningScoreprivate HardSoftScore score;// Ignored by Timefold, used by the UI to display solve or stop solving buttonprivate SolverStatus solverStatus;// No-arg constructor required for Timefoldpublic Timetable() {}public Timetable(String name, HardSoftScore score, SolverStatus solverStatus) {this.name = name;this.score = score;this.solverStatus = solverStatus;}public Timetable(String name, List<Timeslot> timeslots, List<Room> rooms, List<Lesson> lessons) {this.name = name;this.timeslots = timeslots;this.rooms = rooms;this.lessons = lessons;}// ************************************************************************// Getters and setters// ************************************************************************public String getName() {return name;}public List<Timeslot> getTimeslots() {return timeslots;}public List<Room> getRooms() {return rooms;}public List<Lesson> getLessons() {return lessons;}public HardSoftScore getScore() {return score;}public SolverStatus getSolverStatus() {return solverStatus;}public void setSolverStatus(SolverStatus solverStatus) {this.solverStatus = solverStatus;}}

controller

package org.acme.schooltimetabling.rest;import java.util.Collection;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;import ai.timefold.solver.core.api.score.analysis.ScoreAnalysis;
import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
import ai.timefold.solver.core.api.solver.ScoreAnalysisFetchPolicy;
import ai.timefold.solver.core.api.solver.SolutionManager;
import ai.timefold.solver.core.api.solver.SolverManager;
import ai.timefold.solver.core.api.solver.SolverStatus;import org.acme.schooltimetabling.domain.Timetable;
import org.acme.schooltimetabling.rest.exception.ErrorInfo;
import org.acme.schooltimetabling.rest.exception.TimetableSolverException;
import org.acme.schooltimetabling.solver.justifications.RoomConflictJustification;
import org.acme.schooltimetabling.solver.justifications.StudentGroupConflictJustification;
import org.acme.schooltimetabling.solver.justifications.StudentGroupSubjectVarietyJustification;
import org.acme.schooltimetabling.solver.justifications.TeacherConflictJustification;
import org.acme.schooltimetabling.solver.justifications.TeacherRoomStabilityJustification;
import org.acme.schooltimetabling.solver.justifications.TeacherTimeEfficiencyJustification;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.aot.hint.annotation.RegisterReflectionForBinding;
import org.springframework.http.HttpStatus;
import org.springframework.http.MediaType;
import org.springframework.web.bind.annotation.DeleteMapping;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.PutMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;import io.swagger.v3.oas.annotations.Operation;
import io.swagger.v3.oas.annotations.Parameter;
import io.swagger.v3.oas.annotations.media.Content;
import io.swagger.v3.oas.annotations.media.Schema;
import io.swagger.v3.oas.annotations.responses.ApiResponse;
import io.swagger.v3.oas.annotations.responses.ApiResponses;
import io.swagger.v3.oas.annotations.tags.Tag;@Tag(name = "School Timetables", description = "School timetable service assigning lessons to rooms and timeslots.")
@RestController
@RequestMapping("/timetables")
public class TimetableController {private static final Logger LOGGER = LoggerFactory.getLogger(TimetableController.class);private final SolverManager<Timetable, String> solverManager;private final SolutionManager<Timetable, HardSoftScore> solutionManager;// TODO: Without any "time to live", the map may eventually grow out of memory.private final ConcurrentMap<String, Job> jobIdToJob = new ConcurrentHashMap<>();public TimetableController(SolverManager<Timetable, String> solverManager,SolutionManager<Timetable, HardSoftScore> solutionManager) {this.solverManager = solverManager;this.solutionManager = solutionManager;}@Operation(summary = "List the job IDs of all submitted timetables.")@ApiResponses(value = {@ApiResponse(responseCode = "200", description = "List of all job IDs.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(type = "array", implementation = String.class))) })@GetMappingpublic Collection<String> list() {return jobIdToJob.keySet();}@Operation(summary = "Submit a timetable to start solving as soon as CPU resources are available.")@ApiResponses(value = {@ApiResponse(responseCode = "202",description = "The job ID. Use that ID to get the solution with the other methods.",content = @Content(mediaType = MediaType.TEXT_PLAIN_VALUE,schema = @Schema(implementation = String.class))) })@PostMapping(consumes = MediaType.APPLICATION_JSON_VALUE, produces = MediaType.TEXT_PLAIN_VALUE)public String solve(@RequestBody Timetable problem) {String jobId = UUID.randomUUID().toString();jobIdToJob.put(jobId, Job.ofTimetable(problem));solverManager.solveBuilder().withProblemId(jobId).withProblemFinder(jobId_ -> jobIdToJob.get(jobId).timetable).withBestSolutionConsumer(solution -> jobIdToJob.put(jobId, Job.ofTimetable(solution))).withExceptionHandler((jobId_, exception) -> {jobIdToJob.put(jobId, Job.ofException(exception));LOGGER.error("Failed solving jobId ({}).", jobId, exception);}).run();return jobId;}@Operation(summary = "Submit a timetable to analyze its score.")@ApiResponses(value = {@ApiResponse(responseCode = "202",description = "Resulting score analysis, optionally without constraint matches.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ScoreAnalysis.class))) })@PutMapping(value = "/analyze", consumes = MediaType.APPLICATION_JSON_VALUE, produces = MediaType.APPLICATION_JSON_VALUE)@RegisterReflectionForBinding({RoomConflictJustification.class,StudentGroupConflictJustification.class,StudentGroupSubjectVarietyJustification.class,TeacherConflictJustification.class,TeacherRoomStabilityJustification.class,TeacherTimeEfficiencyJustification.class})public ScoreAnalysis<HardSoftScore> analyze(@RequestBody Timetable problem,@RequestParam(name = "fetchPolicy", required = false) ScoreAnalysisFetchPolicy fetchPolicy) {return fetchPolicy == null ? solutionManager.analyze(problem) : solutionManager.analyze(problem, fetchPolicy);}@Operation(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.")@ApiResponses(value = {@ApiResponse(responseCode = "200", description = "The best solution of the timetable so far.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = Timetable.class))),@ApiResponse(responseCode = "404", description = "No timetable found.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ErrorInfo.class))),@ApiResponse(responseCode = "500", description = "Exception during solving a timetable.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ErrorInfo.class)))})@GetMapping(value = "/{jobId}", produces = MediaType.APPLICATION_JSON_VALUE)public Timetable getTimeTable(@Parameter(description = "The job ID returned by the POST method.") @PathVariable("jobId") String jobId) {Timetable timetable = getTimetableAndCheckForExceptions(jobId);SolverStatus solverStatus = solverManager.getSolverStatus(jobId);timetable.setSolverStatus(solverStatus);return timetable;}@Operation(summary = "Get the timetable status and score for a given job ID.")@ApiResponses(value = {@ApiResponse(responseCode = "200", description = "The timetable status and the best score so far.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = Timetable.class))),@ApiResponse(responseCode = "404", description = "No timetable found.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ErrorInfo.class))),@ApiResponse(responseCode = "500", description = "Exception during solving a timetable.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ErrorInfo.class)))})@GetMapping(value = "/{jobId}/status", produces = MediaType.APPLICATION_JSON_VALUE)public Timetable getStatus(@Parameter(description = "The job ID returned by the POST method.") @PathVariable("jobId") String jobId) {Timetable timetable = getTimetableAndCheckForExceptions(jobId);SolverStatus solverStatus = solverManager.getSolverStatus(jobId);return new Timetable(timetable.getName(), timetable.getScore(), solverStatus);}private Timetable getTimetableAndCheckForExceptions(String jobId) {Job job = jobIdToJob.get(jobId);if (job == null) {throw new TimetableSolverException(jobId, HttpStatus.NOT_FOUND, "No timetable found.");}if (job.exception != null) {throw new TimetableSolverException(jobId, job.exception);}return job.timetable;}@Operation(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.")@ApiResponses(value = {@ApiResponse(responseCode = "200", description = "The best solution of the timetable so far.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = Timetable.class))),@ApiResponse(responseCode = "404", description = "No timetable found.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ErrorInfo.class))),@ApiResponse(responseCode = "500", description = "Exception during solving a timetable.",content = @Content(mediaType = MediaType.APPLICATION_JSON_VALUE,schema = @Schema(implementation = ErrorInfo.class)))})@DeleteMapping(value = "/{jobId}", produces = MediaType.APPLICATION_JSON_VALUE)public Timetable terminateSolving(@Parameter(description = "The job ID returned by the POST method.") @PathVariable("jobId") String jobId) {// TODO: Replace with .terminateEarlyAndWait(... [, timeout]); see https://github.com/TimefoldAI/timefold-solver/issues/77solverManager.terminateEarly(jobId);return getTimeTable(jobId);}private record Job(Timetable timetable, Throwable exception) {static Job ofTimetable(Timetable timetable) {return new Job(timetable, null);}static Job ofException(Throwable error) {return new Job(null, error);}}
}

设置终止时间

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

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

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

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

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

代码仓库

  • https://github.com/Harries/springboot-demo

3.测试

启动Spring Boot应用程序

时间表生成

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

111

4.引用

  • Optimization algorithms :: Timefold Documentation
  • Spring Boot集成Timefold Solver实现课程表编排 | Harries Blog™

http://www.ppmy.cn/server/49341.html

相关文章

力扣911.在线选举

力扣911.在线选举

力扣911.在线选举 类似1818. 将每个时刻的候选人存储 在时间段上做二分 class TopVotedCandidate {vector<int> time,person;public:TopVotedCandidate(vector<int>& persons, vector<int>& times) {int n persons.size();unordered_map<int,…
阅读更多...
基于Java和SSM框架的多人命题系统

基于Java和SSM框架的多人命题系统

你好呀&#xff0c;我是计算机学长猫哥&#xff01;如果你对多人命题系统感兴趣或者有相关开发需求&#xff0c;文末可以找到我的联系方式。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;Java SSM框架 工具&#xff1a;Eclipse、MySQL Workbench、…
阅读更多...
Springboot 整合 Flowable（二）：使用 Flowable BPMN visualizer 绘制流程图

Springboot 整合 Flowable（二）：使用 Flowable BPMN visualizer 绘制流程图

&#x1f4c1; Springboot 整合 Flowable&#xff08;一&#xff09;&#xff1a;使用 flowable-UI 绘制流程图-CSDN博客 一、安装 IDEA 插件&#xff1a;Flowable BPMN visualizer 二、绘制流程图 1、创建流程文件 2、选中文件后&#xff0c;右键打开流程图设计界面 以一个简…
阅读更多...
DAY24 回溯算法part01 77. 组合 216.组合总和III 17.电话号码的字母组合

DAY24 回溯算法part01 77. 组合 216.组合总和III 17.电话号码的字母组合

理论基础 #什么是回溯法 回溯法也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 在二叉树系列中&#xff0c;我们已经不止一次&#xff0c;提到了回溯&#xff0c;例如二叉树&#xff1a;以为使用了递归&#xff0c;其实还隐藏着回溯 (opens new window)。 回溯是递…
阅读更多...
AI大模型在运动项目的深度融合和在穿戴设备的实践及未来运动健康技术发展

AI大模型在运动项目的深度融合和在穿戴设备的实践及未来运动健康技术发展

文章目录 1. 技术架构2. 模型选择2.1 LSTM&#xff08;长短期记忆网络&#xff09;2.2 CNN&#xff08;卷积神经网络&#xff09;2.3 Transformer 3. 数据处理数据预处理 4. 实时性要求4.1 边缘计算4.2 模型优化 5. 数据隐私与安全6. 深入分析AI大模型在穿戴设备的应用和未来发…
阅读更多...
【LeetCode最详尽解答】238.除自身以外数组的乘积 Product-of-Array-Except-Self

【LeetCode最详尽解答】238.除自身以外数组的乘积 Product-of-Array-Except-Self

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家&#xff01; 链接: 238_除自身以外数组的乘积 直觉 这个问题有点棘手&#xff0c;我看了 Neetcode 的解释。Neetco…
阅读更多...
实验：贪心算法

实验：贪心算法

实验二&#xff1a;贪心算法 【实验目的】 应用贪心算法求解活动安排问题。 【实验性质】 验证性实验。 【实验要求】 活动安排问题是可以用贪心算法有效求解的很好的例子。 问题&#xff1a;有n个活动的集合A{1,2,…,n}&#xff0c;其中每个活动都要求使用同一资源&…
阅读更多...
IDEA2023中使用run Dashboard面板?实现批量运行微服务

IDEA2023中使用run Dashboard面板?实现批量运行微服务

1、直接点击Add service--->Run Configuration Type---->Spring Boot 2、这样就出现了run Dashboard面板&#xff0c;可同时运行多个工程模块&#xff0c;shift选中所有启动类组命名&#xff08;Group Configurations&#xff09; 3、启动所有的项目
阅读更多...
最新文章

Copyright @ 2022~2023