OptaPlanner - Using AI to optimize a schedule with OptaPlanner

This guide walks you through the process of creating a Quarkus application with OptaPlanner‘s constraint solving Artificial Intelligence (AI).

What you will build

You will build a REST application that optimizes a school timetable for students and teachers:

optaplanner time table app screenshot

Your service will assign Lesson instances to Timeslot and Room instances automatically by using AI to adhere to hard and soft scheduling constraints, such as:

  • A room can have at most one lesson at the same time.

  • A teacher can teach at most one lesson at the same time.

  • A student can attend at most one lesson at the same time.

  • A teacher prefers to teach in a single room.

  • A teacher prefers to teach sequential lessons and dislikes gaps between lessons.

  • A student dislikes sequential lessons on the same subject.

Mathematically speaking, school timetabling is an NP-hard problem. That means it is difficult to scale. Simply brute force iterating through all possible combinations takes millions of years for a non-trivial dataset, even on a supercomputer. Luckily, AI constraint solvers such as OptaPlanner have advanced algorithms that deliver a near-optimal solution in a reasonable amount of time.

Solution

We recommend that you follow the instructions in the next sections and create the application step by step. However, you can go right to the completed example.

Clone the Git repository: git clone [https://github.com/quarkusio/quarkus-quickstarts.git](https://github.com/quarkusio/quarkus-quickstarts.git), or download an archive.

The solution is located in the optaplanner-quickstart directory.

Prerequisites

To complete this guide, you need:

  • about 30 minutes

  • an IDE

  • JDK 1.8+ installed with JAVA_HOME configured appropriately

  • Apache Maven 3.6.2+ or Gradle 4+

The build file and the dependencies

Use code.quarkus.io to generate an application with the following extensions, for Maven or Gradle:

  • RESTEasy JAX-RS (quarkus-resteasy)

  • RESTEasy Jackson (quarkus-resteasy-jackson)

  • OptaPlanner (optaplanner-quarkus)

  • OptaPlanner Jackson (optaplanner-quarkus-jackson)

Alternatively, generate it from the command line with Maven:

  1. mvn io.quarkus:quarkus-maven-plugin:1.7.6.Final:create \
  2.     -DprojectGroupId=org.acme \
  3.     -DprojectArtifactId=optaplanner-quickstart \
  4.     -Dextensions="resteasy, resteasy-jackson, optaplanner-quarkus, optaplanner-quarkus-jackson"
  5. cd optaplanner-quickstart

In Maven, your pom.xml file contains these dependencies:

  1.   <dependencyManagement>
  2.     <dependencies>
  3.       <dependency>
  4.         <groupId>io.quarkus</groupId>
  5.         <artifactId>quarkus-universe-bom</artifactId>
  6.         <version>1.7.6.Final</version>
  7.         <type>pom</type>
  8.         <scope>import</scope>
  9.       </dependency>
  10.     </dependencies>
  11.   </dependencyManagement>
  12.   <dependencies>
  13.     <dependency>
  14.       <groupId>io.quarkus</groupId>
  15.       <artifactId>quarkus-resteasy</artifactId>
  16.     </dependency>
  17.     <dependency>
  18.       <groupId>io.quarkus</groupId>
  19.       <artifactId>quarkus-resteasy-jackson</artifactId>
  20.     </dependency>
  21.     <dependency>
  22.       <groupId>org.optaplanner</groupId>
  23.       <artifactId>optaplanner-quarkus</artifactId>
  24.     </dependency>
  25.     <dependency>
  26.       <groupId>org.optaplanner</groupId>
  27.       <artifactId>optaplanner-quarkus-jackson</artifactId>
  28.     </dependency>
  30.     <dependency>
  31.       <groupId>io.quarkus</groupId>
  32.       <artifactId>quarkus-junit5</artifactId>
  33.       <scope>test</scope>
  34.     </dependency>
  35.   </dependencies>

Model the domain objects

Your goal is to assign each lesson to a time slot and a room. You will create these classes:

optaplanner time table class diagram pure

Timeslot

The Timeslot class represents a time interval when lessons are taught, for example, Monday 10:30 - 11:30 or Tuesday 13:30 - 14:30. For simplicity’s sake, all time slots have the same duration and there are no time slots during lunch or other breaks.

A time slot has no date, because a high school schedule just repeats every week. So there is no need for continuous planning.

Create the src/main/java/org/acme/optaplanner/domain/Timeslot.java class:

  1. package org.acme.optaplanner.domain;
  3. import java.time.DayOfWeek;
  4. import java.time.LocalTime;
  6. public class Timeslot {
  8.     private DayOfWeek dayOfWeek;
  9.     private LocalTime startTime;
  10.     private LocalTime endTime;
  12.     public Timeslot() {
  13.     }
  15.     public Timeslot(DayOfWeek dayOfWeek, LocalTime startTime, LocalTime endTime) {
  16.         this.dayOfWeek = dayOfWeek;
  17.         this.startTime = startTime;
  18.         this.endTime = endTime;
  19.     }
  21.     public DayOfWeek getDayOfWeek() {
  22.         return dayOfWeek;
  23.     }
  25.     public LocalTime getStartTime() {
  26.         return startTime;
  27.     }
  29.     public LocalTime getEndTime() {
  30.         return endTime;
  31.     }
  33.     @Override
  34.     public String toString() {
  35.         return dayOfWeek + " " + startTime;
  36.     }
  38. }

Because no Timeslot instances change during solving, a Timeslot is called a problem fact. Such classes do not require any OptaPlanner specific annotations.

Notice the toString() method keeps the output short, so it is easier to read OptaPlanner’s DEBUG or TRACE log, as shown later.

Room

The Room class represents a location where lessons are taught, for example, Room A or Room B. For simplicity’s sake, all rooms are without capacity limits and they can accommodate all lessons.

Create the src/main/java/org/acme/optaplanner/domain/Room.java class:

  1. package org.acme.optaplanner.domain;
  3. public class Room {
  5.     private String name;
  7.     public Room() {
  8.     }
  10.     public Room(String name) {
  11.         this.name = name;
  12.     }
  14.     public String getName() {
  15.         return name;
  16.     }
  18.     @Override
  19.     public String toString() {
  20.         return name;
  21.     }
  23. }

Room instances do not change during solving, so Room is also a problem fact.

Lesson

During a lesson, represented by the Lesson class, a teacher teaches a subject to a group of students, for example, Math by A.Turing for 9th grade or Chemistry by M.Curie for 10th grade. If a subject is taught multiple times per week by the same teacher to the same student group, there are multiple Lesson instances that are only distinguishable by id. For example, the 9th grade has six math lessons a week.

During solving, OptaPlanner changes the timeslot and room fields of the Lesson class, to assign each lesson to a time slot and a room. Because OptaPlanner changes these fields, Lesson is a planning entity:

optaplanner time table class diagram annotated

Most of the fields in the previous diagram contain input data, except for the orange fields: A lesson’s timeslot and room fields are unassigned (null) in the input data and assigned (not null) in the output data. OptaPlanner changes these fields during solving. Such fields are called planning variables. In order for OptaPlanner to recognize them, both the timeslot and room fields require an @PlanningVariable annotation. Their containing class, Lesson, requires an @PlanningEntity annotation.

Create the src/main/java/org/acme/optaplanner/domain/Lesson.java class:

  1. package org.acme.optaplanner.domain;
  3. import org.optaplanner.core.api.domain.entity.PlanningEntity;
  4. import org.optaplanner.core.api.domain.lookup.PlanningId;
  5. import org.optaplanner.core.api.domain.variable.PlanningVariable;
  7. @PlanningEntity
  8. public class Lesson {
  10.     @PlanningId
  11.     private Long id;
  13.     private String subject;
  14.     private String teacher;
  15.     private String studentGroup;
  17.     @PlanningVariable(valueRangeProviderRefs = "timeslotRange")
  18.     private Timeslot timeslot;
  19.     @PlanningVariable(valueRangeProviderRefs = "roomRange")
  20.     private Room room;
  22.     public Lesson() {
  23.     }
  25.     public Lesson(Long id, String subject, String teacher, String studentGroup) {
  26.         this.id = id;
  27.         this.subject = subject;
  28.         this.teacher = teacher;
  29.         this.studentGroup = studentGroup;
  30.     }
  32.     public Long getId() {
  33.         return id;
  34.     }
  36.     public String getSubject() {
  37.         return subject;
  38.     }
  40.     public String getTeacher() {
  41.         return teacher;
  42.     }
  44.     public String getStudentGroup() {
  45.         return studentGroup;
  46.     }
  48.     public Timeslot getTimeslot() {
  49.         return timeslot;
  50.     }
  52.     public void setTimeslot(Timeslot timeslot) {
  53.         this.timeslot = timeslot;
  54.     }
  56.     public Room getRoom() {
  57.         return room;
  58.     }
  60.     public void setRoom(Room room) {
  61.         this.room = room;
  62.     }
  64.     @Override
  65.     public String toString() {
  66.         return subject + "(" + id + ")";
  67.     }
  69. }

The Lesson class has an @PlanningEntity annotation, so OptaPlanner knows that this class changes during solving because it contains one or more planning variables.

The timeslot field has an @PlanningVariable annotation, so OptaPlanner knows that it can change its value. In order to find potential Timeslot instances to assign to this field, OptaPlanner uses the valueRangeProviderRefs property to connect to a value range provider (explained later) that provides a List<Timeslot> to pick from.

The room field also has an @PlanningVariable annotation, for the same reasons.

Determining the @PlanningVariable fields for an arbitrary constraint solving use case is often challenging the first time. Read the domain modeling guidelines to avoid common pitfalls.

Define the constraints and calculate the score

A score represents the quality of a given solution. The higher the better. OptaPlanner looks for the best solution, which is the solution with the highest score found in the available time. It could be the optimal solution.

Because this use case has hard and soft constraints, use the HardSoftScore class to represent the score:

  • Hard constraints must not be broken. For example: A room can have at most one lesson at the same time.

  • Soft constraints should not be broken. For example: A teacher prefers to teach in a single room.

Hard constraints are weighted against other hard constraints. Soft constraints are weighted too, against other soft constraints. Hard constraints always outweigh soft constraints, regardless of their respective weights.

To calculate the score, you could implement an EasyScoreCalculator class:

  1. public class TimeTableEasyScoreCalculator implements EasyScoreCalculator<TimeTable> {
  3.     @Override
  4.     public HardSoftScore calculateScore(TimeTable timeTable) {
  5.         List<Lesson> lessonList = timeTable.getLessonList();
  6.         int hardScore = 0;
  7.         for (Lesson a : lessonList) {
  8.             for (Lesson b : lessonList) {
  9.                 if (a.getTimeslot() != null && a.getTimeslot().equals(b.getTimeslot())
  10.                         && a.getId() < b.getId()) {
  11.                     // A room can accommodate at most one lesson at the same time.
  12.                     if (a.getRoom() != null && a.getRoom().equals(b.getRoom())) {
  13.                         hardScore--;
  14.                     }
  15.                     // A teacher can teach at most one lesson at the same time.
  16.                     if (a.getTeacher().equals(b.getTeacher())) {
  17.                         hardScore--;
  18.                     }
  19.                     // A student can attend at most one lesson at the same time.
  20.                     if (a.getStudentGroup().equals(b.getStudentGroup())) {
  21.                         hardScore--;
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.         int softScore = 0;
  27.         // Soft constraints are only implemented in optaplanner-quickstart
  28.         return HardSoftScore.of(hardScore, softScore);
  29.     }
  31. }

Unfortunately that does not scale well, because it is non-incremental: every time a lesson is assigned to a different time slot or room, all lessons are re-evaluated to calculate the new score.

Instead, create a src/main/java/org/acme/optaplanner/solver/TimeTableConstraintProvider.java class to perform incremental score calculation. It uses OptaPlanner’s ConstraintStream API which is inspired by Java 8 Streams and SQL:

  1. package org.acme.optaplanner.solver;
  3. import org.acme.optaplanner.domain.Lesson;
  4. import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
  5. import org.optaplanner.core.api.score.stream.Constraint;
  6. import org.optaplanner.core.api.score.stream.ConstraintFactory;
  7. import org.optaplanner.core.api.score.stream.ConstraintProvider;
  8. import org.optaplanner.core.api.score.stream.Joiners;
  10. public class TimeTableConstraintProvider implements ConstraintProvider {
  12.     @Override
  13.     public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
  14.         return new Constraint[] {
  15.                 // Hard constraints
  16.                 roomConflict(constraintFactory),
  17.                 teacherConflict(constraintFactory),
  18.                 studentGroupConflict(constraintFactory),
  19.                 // Soft constraints are only implemented in optaplanner-quickstart
  20.         };
  21.     }
  23.     private Constraint roomConflict(ConstraintFactory constraintFactory) {
  24.         // A room can accommodate at most one lesson at the same time.
  26.         // Select a lesson ...
  27.         return constraintFactory.from(Lesson.class)
  28.                 // ... and pair it with another lesson ...
  29.                 .join(Lesson.class,
  30.                         // ... in the same timeslot ...
  31.                         Joiners.equal(Lesson::getTimeslot),
  32.                         // ... in the same room ...
  33.                         Joiners.equal(Lesson::getRoom),
  34.                         // ... and the pair is unique (different id, no reverse pairs)
  35.                         Joiners.lessThan(Lesson::getId))
  36.                 // then penalize each pair with a hard weight.
  37.                 .penalize("Room conflict", HardSoftScore.ONE_HARD);
  38.     }
  40.     private Constraint teacherConflict(ConstraintFactory constraintFactory) {
  41.         // A teacher can teach at most one lesson at the same time.
  42.         return constraintFactory
  43.                 .fromUniquePair(Lesson.class,
  44.                         Joiners.equal(Lesson::getTimeslot),
  45.                         Joiners.equal(Lesson::getTeacher))
  46.                 .penalize("Teacher conflict", HardSoftScore.ONE_HARD);
  47.     }
  49.     private Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
  50.         // A student can attend at most one lesson at the same time.
  51.         return constraintFactory
  52.                 .fromUniquePair(Lesson.class,
  53.                         Joiners.equal(Lesson::getTimeslot),
  54.                         Joiners.equal(Lesson::getStudentGroup))
  55.                 .penalize("Student group conflict", HardSoftScore.ONE_HARD);
  56.     }
  58. }

The ConstraintProvider scales an order of magnitude better than the EasyScoreCalculator: O(n) instead of O(n²).

Gather the domain objects in a planning solution

A TimeTable wraps all Timeslot, Room, and Lesson instances of a single dataset. Furthermore, because it contains all lessons, each with a specific planning variable state, it is a planning solution and it has a score:

  • If lessons are still unassigned, then it is an uninitialized solution, for example, a solution with the score -4init/0hard/0soft.

  • If it breaks hard constraints, then it is an infeasible solution, for example, a solution with the score -2hard/-3soft.

  • If it adheres to all hard constraints, then it is a feasible solution, for example, a solution with the score 0hard/-7soft.

Create the src/main/java/org/acme/optaplanner/domain/TimeTable.java class:

  1. package org.acme.optaplanner.domain;
  3. import java.util.List;
  5. import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
  6. import org.optaplanner.core.api.domain.solution.PlanningScore;
  7. import org.optaplanner.core.api.domain.solution.PlanningSolution;
  8. import org.optaplanner.core.api.domain.solution.drools.ProblemFactCollectionProperty;
  9. import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
  10. import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
  12. @PlanningSolution
  13. public class TimeTable {
  15.     @ProblemFactCollectionProperty
  16.     @ValueRangeProvider(id = "timeslotRange")
  17.     private List<Timeslot> timeslotList;
  18.     @ProblemFactCollectionProperty
  19.     @ValueRangeProvider(id = "roomRange")
  20.     private List<Room> roomList;
  21.     @PlanningEntityCollectionProperty
  22.     private List<Lesson> lessonList;
  24.     @PlanningScore
  25.     private HardSoftScore score;
  27.     public TimeTable() {
  28.     }
  30.     public TimeTable(List<Timeslot> timeslotList, List<Room> roomList, List<Lesson> lessonList) {
  31.         this.timeslotList = timeslotList;
  32.         this.roomList = roomList;
  33.         this.lessonList = lessonList;
  34.     }
  36.     public List<Timeslot> getTimeslotList() {
  37.         return timeslotList;
  38.     }
  40.     public List<Room> getRoomList() {
  41.         return roomList;
  42.     }
  44.     public List<Lesson> getLessonList() {
  45.         return lessonList;
  46.     }
  48.     public HardSoftScore getScore() {
  49.         return score;
  50.     }
  52. }

The TimeTable class has an @PlanningSolution annotation, so OptaPlanner knows that this class contains all of the input and output data.

Specifically, this class is the input of the problem:

  • A timeslotList field with all time slots

    • This is a list of problem facts, because they do not change during solving.

  • A roomList field with all rooms

    • This is a list of problem facts, because they do not change during solving.

  • A lessonList field with all lessons

    • This is a list of planning entities, because they change during solving.

    • Of each Lesson:

      • The values of the timeslot and room fields are typically still null, so unassigned. They are planning variables.

      • The other fields, such as subject, teacher and studentGroup, are filled in. These fields are problem properties.

However, this class is also the output of the solution:

  • A lessonList field for which each Lesson instance has non-null timeslot and room fields after solving

  • A score field that represents the quality of the output solution, for example, 0hard/-5soft

The value range providers

That timeslotList field is a value range provider. It holds the Timeslot instances which OptaPlanner can pick from to assign to the timeslot field of Lesson instances. The timeslotList field has an @ValueRangeProvider annotation to connect those two, by matching the id with the valueRangeProviderRefs of the @PlanningVariable in the Lesson.

Following the same logic, the roomList field also has an @ValueRangeProvider annotation.

The problem fact and planning entity properties

Furthermore, OptaPlanner needs to know which Lesson instances it can change as well as how to retrieve the Timeslot and Room instances used for score calculation by your TimeTableConstraintProvider.

The timeslotList and roomList fields have an @ProblemFactCollectionProperty annotation, so your TimeTableConstraintProvider can select from those instances.

The lessonList has an @PlanningEntityCollectionProperty annotation, so OptaPlanner can change them during solving and your TimeTableConstraintProvider can select from those too.

Create the solver service

Now you are ready to put everything together and create a REST service. But solving planning problems on REST threads causes HTTP timeout issues. Therefore, the Quarkus extension injects a SolverManager, which runs solvers in a separate thread pool and can solve multiple datasets in parallel.

Create the src/main/java/org/acme/optaplanner/rest/TimeTableResource.java class:

  1. package org.acme.optaplanner.rest;
  3. import java.util.UUID;
  4. import java.util.concurrent.ExecutionException;
  5. import javax.inject.Inject;
  6. import javax.ws.rs.Consumes;
  7. import javax.ws.rs.POST;
  8. import javax.ws.rs.Path;
  9. import javax.ws.rs.Produces;
  10. import javax.ws.rs.core.MediaType;
  12. import org.acme.optaplanner.domain.TimeTable;
  13. import org.optaplanner.core.api.solver.SolverJob;
  14. import org.optaplanner.core.api.solver.SolverManager;
  16. @Path("/timeTable")
  17. @Produces(MediaType.APPLICATION_JSON)
  18. @Consumes(MediaType.APPLICATION_JSON)
  19. public class TimeTableResource {
  21.     @Inject
  22.     SolverManager<TimeTable, UUID> solverManager;
  24.     @POST
  25.     @Path("/solve")
  26.     public TimeTable solve(TimeTable problem) {
  27.         UUID problemId = UUID.randomUUID();
  28.         // Submit the problem to start solving
  29.         SolverJob<TimeTable, UUID> solverJob = solverManager.solve(problemId, problem);
  30.         TimeTable solution;
  31.         try {
  32.             // Wait until the solving ends
  33.             solution = solverJob.getFinalBestSolution();
  34.         } catch (InterruptedException | ExecutionException e) {
  35.             throw new IllegalStateException("Solving failed.", e);
  36.         }
  37.         return solution;
  38.     }
  40. }

For simplicity’s sake, this initial implementation waits for the solver to finish, which can still cause an HTTP timeout. The complete implementation avoids HTTP timeouts much more elegantly.

Set the termination time

Without a termination setting or a termination event, the solver runs forever. To avoid that, limit the solving time to five seconds. That is short enough to avoid the HTTP timeout.

Create the src/main/resources/application.properties file:

  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. quarkus.optaplanner.solver.termination.spent-limit=5s

Make the application executable

First start the application:

  1. $ ./mvnw compile quarkus:dev

Try the application

Now that the application is running, you can test the REST service. You can use any REST client you wish. The following example uses the Linux command curl to send a POST request:

  1. $ curl -i -X POST http://localhost:8080/timeTable/solve -H "Content-Type:application/json" -d '{"timeslotList":[{"dayOfWeek":"MONDAY","startTime":"08:30:00","endTime":"09:30:00"},{"dayOfWeek":"MONDAY","startTime":"09:30:00","endTime":"10:30:00"}],"roomList":[{"name":"Room A"},{"name":"Room B"}],"lessonList":[{"id":1,"subject":"Math","teacher":"A. Turing","studentGroup":"9th grade"},{"id":2,"subject":"Chemistry","teacher":"M. Curie","studentGroup":"9th grade"},{"id":3,"subject":"French","teacher":"M. Curie","studentGroup":"10th grade"},{"id":4,"subject":"History","teacher":"I. Jones","studentGroup":"10th grade"}]}'

After about five seconds, according to the termination spent time defined in your application.properties, the service returns an output similar to the following example:

  1. HTTP/1.1 200
  2. Content-Type: application/json
  3. ...
  5. {"timeslotList":...,"roomList":...,"lessonList":[{"id":1,"subject":"Math","teacher":"A. Turing","studentGroup":"9th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"08:30:00","endTime":"09:30:00"},"room":{"name":"Room A"}},{"id":2,"subject":"Chemistry","teacher":"M. Curie","studentGroup":"9th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"09:30:00","endTime":"10:30:00"},"room":{"name":"Room A"}},{"id":3,"subject":"French","teacher":"M. Curie","studentGroup":"10th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"08:30:00","endTime":"09:30:00"},"room":{"name":"Room B"}},{"id":4,"subject":"History","teacher":"I. Jones","studentGroup":"10th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"09:30:00","endTime":"10:30:00"},"room":{"name":"Room B"}}],"score":"0hard/0soft"}

Notice that your application assigned all four lessons to one of the two time slots and one of the two rooms. Also notice that it conforms to all hard constraints. For example, M. Curie’s two lessons are in different time slots.

On the server side, the info log show what OptaPlanner did in those five seconds:

  1. ... Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
  2. ... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4).
  3. ... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398).
  4. ... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).

Test the application

A good application includes test coverage. In a JUnit test, generate a test dataset and send it to the TimeTableResource to solve.

Create the src/test/java/org/acme/optaplanner/rest/TimeTableResourceTest.java class:

  1. package org.acme.optaplanner.rest;
  3. import java.time.DayOfWeek;
  4. import java.time.LocalTime;
  5. import java.util.ArrayList;
  6. import java.util.List;
  8. import javax.inject.Inject;
  10. import io.quarkus.test.junit.QuarkusTest;
  11. import org.acme.optaplanner.domain.Room;
  12. import org.acme.optaplanner.domain.Timeslot;
  13. import org.acme.optaplanner.domain.Lesson;
  14. import org.acme.optaplanner.domain.TimeTable;
  15. import org.acme.optaplanner.rest.TimeTableResource;
  16. import org.junit.jupiter.api.Test;
  17. import org.junit.jupiter.api.Timeout;
  19. import static org.junit.jupiter.api.Assertions.assertFalse;
  20. import static org.junit.jupiter.api.Assertions.assertNotNull;
  21. import static org.junit.jupiter.api.Assertions.assertTrue;
  23. @QuarkusTest
  24. public class TimeTableResourceTest {
  26.     @Inject
  27.     TimeTableResource timeTableResource;
  29.     @Test
  30.     @Timeout(600_000)
  31.     public void solve() {
  32.         TimeTable problem = generateProblem();
  33.         TimeTable solution = timeTableResource.solve(problem);
  34.         assertFalse(solution.getLessonList().isEmpty());
  35.         for (Lesson lesson : solution.getLessonList()) {
  36.             assertNotNull(lesson.getTimeslot());
  37.             assertNotNull(lesson.getRoom());
  38.         }
  39.         assertTrue(solution.getScore().isFeasible());
  40.     }
  42.     private TimeTable generateProblem() {
  43.         List<Timeslot> timeslotList = new ArrayList<>();
  44.         timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(8, 30), LocalTime.of(9, 30)));
  45.         timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(9, 30), LocalTime.of(10, 30)));
  46.         timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(10, 30), LocalTime.of(11, 30)));
  47.         timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(13, 30), LocalTime.of(14, 30)));
  48.         timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(14, 30), LocalTime.of(15, 30)));
  50.         List<Room> roomList = new ArrayList<>();
  51.         roomList.add(new Room("Room A"));
  52.         roomList.add(new Room("Room B"));
  53.         roomList.add(new Room("Room C"));
  55.         List<Lesson> lessonList = new ArrayList<>();
  56.         lessonList.add(new Lesson(101L, "Math", "B. May", "9th grade"));
  57.         lessonList.add(new Lesson(102L, "Physics", "M. Curie", "9th grade"));
  58.         lessonList.add(new Lesson(103L, "Geography", "M. Polo", "9th grade"));
  59.         lessonList.add(new Lesson(104L, "English", "I. Jones", "9th grade"));
  60.         lessonList.add(new Lesson(105L, "Spanish", "P. Cruz", "9th grade"));
  62.         lessonList.add(new Lesson(201L, "Math", "B. May", "10th grade"));
  63.         lessonList.add(new Lesson(202L, "Chemistry", "M. Curie", "10th grade"));
  64.         lessonList.add(new Lesson(203L, "History", "I. Jones", "10th grade"));
  65.         lessonList.add(new Lesson(204L, "English", "P. Cruz", "10th grade"));
  66.         lessonList.add(new Lesson(205L, "French", "M. Curie", "10th grade"));
  67.         return new TimeTable(timeslotList, roomList, lessonList);
  68.     }
  70. }

This test verifies that after solving, all lessons are assigned to a time slot and a room. It also verifies that it found a feasible solution (no hard constraints broken).

Add test properties to the src/main/resources/application.properties file:

  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. quarkus.optaplanner.solver.termination.spent-limit=5s
  5. # Effectively disable this termination in favor of the best-score-limit
  6. %test.quarkus.optaplanner.solver.termination.spent-limit=1h
  7. %test.quarkus.optaplanner.solver.termination.best-score-limit=0hard/*soft

Normally, the solver finds a feasible solution in less than 200 milliseconds. Notice how the application.properties overwrites the solver termination during tests to terminate as soon as a feasible solution (0hard/*soft) is found. This avoids hard coding a solver time, because the unit test might run on arbitrary hardware. This approach ensures that the test runs long enough to find a feasible solution, even on slow machines. But it does not run a millisecond longer than it strictly must, even on fast machines.

Logging

When adding constraints in your ConstraintProvider, keep an eye on the score calculation speed in the info log, after solving for the same amount of time, to assess the performance impact:

  1. ... Solving ended: ..., score calculation speed (29455/sec), ...

To understand how OptaPlanner is solving your problem internally, change the logging in the application.properties file or with a -D system property:

  1. quarkus.log.category."org.optaplanner".level=debug

Use debug logging to show every step:

  1. ... Solving started: time spent (67), best score (-20init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
  2. ...     CH step (0), time spent (128), score (-18init/0hard/0soft), selected move count (15), picked move ([Math(101) {null -> Room A}, Math(101) {null -> MONDAY 08:30}]).
  3. ...     CH step (1), time spent (145), score (-16init/0hard/0soft), selected move count (15), picked move ([Physics(102) {null -> Room A}, Physics(102) {null -> MONDAY 09:30}]).
  4. ...

Use trace logging to show every step and every move per step.

Summary

Congratulations! You have just developed a Quarkus application with OptaPlanner!

Further improvements: Database and UI integration

Now try adding database and UI integration:

  1. Store Timeslot, Room, and Lesson in the database with Hibernate and Panache.

  2. Expose them through REST.

  3. Adjust the TimeTableResource to read and write a TimeTable in a single transaction and use those accordingly:

    1. package org.acme.optaplanner.rest;
    3. import javax.inject.Inject;
    4. import javax.transaction.Transactional;
    5. import javax.ws.rs.Consumes;
    6. import javax.ws.rs.GET;
    7. import javax.ws.rs.POST;
    8. import javax.ws.rs.Path;
    9. import javax.ws.rs.Produces;
    10. import javax.ws.rs.core.MediaType;
    12. import io.quarkus.panache.common.Sort;
    13. import org.acme.optaplanner.domain.Lesson;
    14. import org.acme.optaplanner.domain.Room;
    15. import org.acme.optaplanner.domain.TimeTable;
    16. import org.acme.optaplanner.domain.Timeslot;
    17. import org.optaplanner.core.api.score.ScoreManager;
    18. import org.optaplanner.core.api.solver.SolverManager;
    19. import org.optaplanner.core.api.solver.SolverStatus;
    21. @Path("/timeTable")
    22. @Produces(MediaType.APPLICATION_JSON)
    23. @Consumes(MediaType.APPLICATION_JSON)
    24. public class TimeTableResource {
    26.     public static final Long SINGLETON_TIME_TABLE_ID = 1L;
    28.     @Inject
    29.     SolverManager<TimeTable, Long> solverManager;
    30.     @Inject
    31.     ScoreManager<TimeTable> scoreManager;
    33.     // To try, open http://localhost:8080/timeTable
    34.     @GET
    35.     public TimeTable getTimeTable() {
    36.         // Get the solver status before loading the solution
    37.         // to avoid the race condition that the solver terminates between them
    38.         SolverStatus solverStatus = getSolverStatus();
    39.         TimeTable solution = findById(SINGLETON_TIME_TABLE_ID);
    40.         scoreManager.updateScore(solution); // Sets the score
    41.         solution.setSolverStatus(solverStatus);
    42.         return solution;
    43.     }
    45.     @POST
    46.     @Path("/solve")
    47.     public void solve() {
    48.         solverManager.solveAndListen(SINGLETON_TIME_TABLE_ID,
    49.                 this::findById,
    50.                 this::save);
    51.     }
    53.     public SolverStatus getSolverStatus() {
    54.         return solverManager.getSolverStatus(SINGLETON_TIME_TABLE_ID);
    55.     }
    57.     @POST
    58.     @Path("/stopSolving")
    59.     public void stopSolving() {
    60.         solverManager.terminateEarly(SINGLETON_TIME_TABLE_ID);
    61.     }
    63.     @Transactional
    64.     protected TimeTable findById(Long id) {
    65.         if (!SINGLETON_TIME_TABLE_ID.equals(id)) {
    66.             throw new IllegalStateException("There is no timeTable with id (" + id + ").");
    67.         }
    68.         // Occurs in a single transaction, so each initialized lesson references the same timeslot/room instance
    69.         // that is contained by the timeTable's timeslotList/roomList.
    70.         return new TimeTable(
    71.                 Timeslot.listAll(Sort.by("dayOfWeek").and("startTime").and("endTime").and("id")),
    72.                 Room.listAll(Sort.by("name").and("id")),
    73.                 Lesson.listAll(Sort.by("subject").and("teacher").and("studentGroup").and("id")));
    74.     }
    76.     @Transactional
    77.     protected void save(TimeTable timeTable) {
    78.         for (Lesson lesson : timeTable.getLessonList()) {
    79.             // TODO this is awfully naive: optimistic locking causes issues if called by the SolverManager
    80.             Lesson attachedLesson = Lesson.findById(lesson.getId());
    81.             attachedLesson.setTimeslot(lesson.getTimeslot());
    82.             attachedLesson.setRoom(lesson.getRoom());
    83.         }
    84.     }
    86. }

    For simplicity’s sake, this code handles only one TimeTable, but it is straightforward to enable multi-tenancy and handle multiple TimeTable instances of different high schools in parallel.

    The getTimeTable() method returns the latest time table from the database. It uses the ScoreManager (which is automatically injected) to calculate the score of that time table, so the UI can show the score.

    The solve() method starts a job to solve the current time table and store the time slot and room assignments in the database. It uses the SolverManager.solveAndListen() method to listen to intermediate best solutions and update the database accordingly. This enables the UI to show progress while the backend is still solving.

  4. Adjust the TimeTableResourceTest accordingly, now that the solve() method returns immediately. Poll for the latest solution until the solver finishes solving:

    1. package org.acme.optaplanner.rest;
    3. import javax.inject.Inject;
    5. import io.quarkus.test.junit.QuarkusTest;
    6. import org.acme.optaplanner.domain.Lesson;
    7. import org.acme.optaplanner.domain.TimeTable;
    8. import org.junit.jupiter.api.Test;
    9. import org.junit.jupiter.api.Timeout;
    10. import org.optaplanner.core.api.solver.SolverStatus;
    12. import static org.junit.jupiter.api.Assertions.assertFalse;
    13. import static org.junit.jupiter.api.Assertions.assertNotNull;
    14. import static org.junit.jupiter.api.Assertions.assertTrue;
    16. @QuarkusTest
    17. public class TimeTableResourceTest {
    19.     @Inject
    20.     TimeTableResource timeTableResource;
    22.     @Test
    23.     @Timeout(600_000)
    24.     public void solveDemoDataUntilFeasible() throws InterruptedException {
    25.         timeTableResource.solve();
    26.         TimeTable timeTable = timeTableResource.getTimeTable();
    27.         while (timeTable.getSolverStatus() != SolverStatus.NOT_SOLVING) {
    28.             // Quick polling (not a Test Thread Sleep anti-pattern)
    29.             // Test is still fast on fast machines and doesn't randomly fail on slow machines.
    30.             Thread.sleep(20L);
    31.             timeTable = timeTableResource.getTimeTable();
    32.         }
    33.         assertFalse(timeTable.getLessonList().isEmpty());
    34.         for (Lesson lesson : timeTable.getLessonList()) {
    35.             assertNotNull(lesson.getTimeslot());
    36.             assertNotNull(lesson.getRoom());
    37.         }
    38.         assertTrue(timeTable.getScore().isFeasible());
    39.     }
    41. }

  5. Build an attractive web UI on top of these REST methods to visualize the timetable.

Take a look at the solution to see how this all turns out.