Java技術Web開發高級語言其他技術腳本語言數據庫大數據教程XML技術專業教育框架軟件工具教程通信技術微軟技術軟件測試手機開發前端技術人工智能實例代碼

員工排班時間折疊求解器指南

瀏覽人數：641最近更新：

    1. 概述

    1.1.什麼是時間折疊求解器？

    Timefold Solver是一個純 Java 規劃求解器 AI。 Timefold 優化規劃問題，例如車輛路線問題 (VRP)、維護調度、作業車間調度和學校時間表。它產生的物流計劃可以大幅降低成本、提高服務品質並減少環境足跡（通常減少 25%），以實現複雜的現實世界調度操作。

    Timefold 是OptaPlanner 的延續。它是一種數學最佳化形式（在更廣泛的運籌學和人工智慧領域），支援以程式碼形式編寫的限制。

    1.2.我們將建造什麼

    在本教程中，我們將使用 Timefold Solver 來優化簡化的員工輪班調度問題。

    我們將自動為員工分配班次，以便：

    • 沒有員工在同一天輪班兩班
    • 每個班次都分配給具有適當技能的員工

    具體來說，我們將分配這五個班次：

     2030-04-01 06:00 - 14:00 (waiter)
 2030-04-01 09:00 - 17:00 (bartender)
 2030-04-01 14:00 - 22:00 (bartender)
 2030-04-02 06:00 - 14:00 (waiter)
 2030-04-02 14:00 - 22:00 (bartender)

    致這三位員工：

     Ann (bartender)
 Beth (waiter, bartender)
 Carl (waiter)

    這比看起來更難。在紙上試試看。

    2. 依賴關係

    Maven Central 上的 Timefold Solver 工件是根據 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 中，我們使用timefold-solver-spring-boot-starter依賴項。正如我們稍後將看到的，它會自動處理大部分求解器配置，並允許在application.properties中配置求解器時間和其他屬性。

    1. 前往start.spring.io
    2. 按一下Add dependencies以新增Timefold Solver依賴項
    3. 產生一個專案並在您喜歡的 IDE 中開啟它

    2.3.誇庫斯

    同樣，在 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字段，以便 Timefold 知道它應該填寫每個班次的員工：

    @PlanningEntity
 public class Shift {

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

 @PlanningVariable
 private Employee employee;

 // A no-arg constructor is required for @PlanningEntity annotated classes
 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類，以便 Timefold 知道它代表輸入和輸出。
    • 我們用@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;

 // A no-arg constructor is required for @PlanningSolution annotated classes
 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

    首先，我們為約束實作建立一個ConstraintProvider ：

    public class ShiftScheduleConstraintProvider implements ConstraintProvider {

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

 // Constraint implementations

 }

    4.2.對ConstraintProvider進行單元測試

    如果沒有經過測試，它就不起作用——尤其是對於約束。讓我們建立一個測試類別來測試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);

 // Tests for each constraint

 }

    我們還準備了兩個日期以在下面的測試中重複使用。接下來讓我們加入實際的約束。

    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))
 // Penalizes by 2 because both {shiftA, shiftB} and {shiftB, shiftA} match.
 // To avoid that, use forEachUniquePair() in the constraint instead of forEach().join() in the implementation.
 .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.解決這個問題

    為了解決時間表，我們從@PlanningSolution 、 @PlanningEntity和ConstraintProvider類別中建立一個SolverFactory 。 SolverFactory是一個長期存在的物件。通常，每個應用程式只有一個實例。

    我們還需要配置求解器運作的時間。對於具有數千個移位和更多約束的大型資料集，不可能在合理的時間範圍內找到最佳解決方案（由於NP 困難問題的指數性質）。相反，我們希望在可用的時間內找到最佳的解決方案。現在我們將其限制為兩秒：

    SolverFactory<ShiftSchedule> solverFactory = SolverFactory.create(new SolverConfig()
 .withSolutionClass(ShiftSchedule.class)
 .withEntityClasses(Shift.class)
 .withConstraintProviderClass(ShiftScheduleConstraintProvider.class)
 // The solver runs only for 2 seconds on this tiny dataset.
 // It's recommended to run for at least 5 minutes ("5m") on large datasets.
 .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("Shift assignments");
 for (Shift shift : solution.getShifts()) {
 logger.info(" " + shift.getStart().toLocalDate()
 + " " + shift.getStart().toLocalTime()
 + " - " + shift.getEnd().toLocalTime()
 + ": " + shift.getEmployee().getName());
 }
 }

    這是我們的數據集的結果：

    Shift assignments
 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

    安沒有被分配到第一班，因為她沒有waiter技能。但為什麼貝絲沒有被分配到第一班呢？她有waiter技能。

    如果貝絲被分配到第一班，那麼就不可能同時分配第二班和第三班。這兩件事都需要bartender ，所以卡爾做不到。只有當卡爾被分配到第一班時，才有可行的解決方案。在大型的現實資料集中，這些錯綜複雜的事情變得更加複雜。讓Solver擔心它們。

    六，結論

    Timefold Solver框架為開發人員提供了解決調度和資源分配等約束滿足問題的強大工具。它支援在程式碼中編寫自訂約束（而不是數學方程式），這使得它易於維護。在底層，它支援各種可以進行功率調整的人工智慧最佳化演算法，但典型用戶不需要這樣做。

    有關更多信息，請參閱時間折疊求解器文件。與往常一樣，本教學的源代碼位於 GitHub 上。

    本作品係原創或者翻譯，採用《署名-非商業性使用-禁止演繹4.0國際》許可協議

    最新文章

    Java 中的空數組到空列表如何在 Spock 測試中檢查記錄的訊息將 LangChain4j 與 Micronaut 結合使用Java 周刊，第 577 期設定 Jersey 的連線逾時和讀取逾時Java 周刊，第 576 期修正 Hibernate QueryParameterException：序數參數無參數使用 Spring Boot 在 Elasticsearch 中匯入 CSV使用反應式 Kafka Stream 和 Spring WebFlux使用 Choco 進行約束編程