此内容没有您所选择的语言版本。
Chapter 8. Red Hat build of OptaPlanner on Red Hat build of Quarkus: a school timetable quick start guide
This guide walks you through the process of creating a Red Hat build of Quarkus application with Red Hat build of OptaPlanner’s constraint solving artificial intelligence (AI). You will build a REST application that optimizes a school timetable for students and teachers
Your service will assign Lesson instances to Timeslot and Room instances automatically by using AI to adhere to the following hard and soft scheduling constraints:
- 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.
Mathematically speaking, school timetabling is an NP-hard problem. That means it is difficult to scale. Simply iterating through all possible combinations with brute force would take millions of years for a non-trivial dataset, even on a supercomputer. Fortunately, AI constraint solvers such as Red Hat build of OptaPlanner have advanced algorithms that deliver a near-optimal solution in a reasonable amount of time. What is considered to be a reasonable amount of time is subjective and depends on the goals of your problem.
Prerequisites
- OpenJDK 11 or later is installed. Red Hat build of Open JDK is available from the Software Downloads page in the Red Hat Customer Portal (login required).
- Apache Maven 3.6 or higher is installed. Maven is available from the Apache Maven Project website.
- An IDE, such as IntelliJ IDEA, VSCode, Eclipse, or NetBeans is available.
8.1. Creating the school timetable project 复制链接链接已复制到粘贴板!
The school timetable project lets you get up and running with a Red Hat build of OptaPlanner and Quarkus application using Apache Maven and the Quarkus Maven plug-in.
If you prefer, you can create a Quakus OptaPlanner project as described in Chapter 7, Getting Started with OptaPlanner and Quarkus.
Procedure
In a command terminal, enter the following command to verify that Maven is using JDK 11 and that the Maven version is 3.6 or higher:
mvn --version
mvn --versionCopy to Clipboard Copied! Toggle word wrap Toggle overflow - If the preceding command does not return JDK 11, add the path to JDK 11 to the PATH environment variable and enter the preceding command again.
To generate the project, enter one of the following commands:
NoteApple macOS and Microsoft Windows are not supported production environments.
If you are using Linux or Apple macOS, enter the following command:
Copy to Clipboard Copied! Toggle word wrap Toggle overflow This command create the following elements in the
./optaplanner-quickstartdirectory:- The Maven structure
-
Example
Dockerfilefile insrc/main/docker The application configuration file
Expand Table 8.1. Properties used in the mvn io.quarkus:quarkus-maven-plugin:1.11.6.Final-redhat-00001:create command Property Description projectGroupIdThe group ID of the project.
projectArtifactIdThe artifact ID of the project.
extensionsA comma-separated list of Quarkus extensions to use with this project. For a full list of Quarkus extensions, enter
mvn quarkus:list-extensionson the command line.platformGroupIdThe Group ID of the target platform.
platformVersionThe version of the platform that you want the project to use.
noExamplesCreates a project with the project structure but without tests or classes.
The values of the
projectGroupIDand theprojectArtifactIDproperties are used to generate the project version. The default project version is1.0.0-SNAPSHOT. The values of theplatformGroupIdandplatformVersionproperties are used byquarkus-universe-bomto manage project dependencies.
After the directory structure is created, open the
optaplanner-quickstart/pom.xmlfile in a text editor and examine the contents of the file to ensure it contains the following elements:Copy to Clipboard Copied! Toggle word wrap Toggle overflow The Quarkus BOM is imported into the
pom.xmlfile. Therefore, you do not need to list the versions of individual Quarkus dependencies in thepom.xmlfile.Review the
quarkus-resteasydependency in thepom.xmlfile. This dependency enables you to develop REST applications:<dependency> <groupId>io.quarkus</groupId> <artifactId>quarkus-resteasy</artifactId> </dependency><dependency> <groupId>io.quarkus</groupId> <artifactId>quarkus-resteasy</artifactId> </dependency>Copy to Clipboard Copied! Toggle word wrap Toggle overflow
8.2. Model the domain objects 复制链接链接已复制到粘贴板!
The goal of the Red Hat build of OptaPlanner timetable project is to assign each lesson to a time slot and a room. To do this, add three classes, Timeslot, Lesson, and Room, as shown in the following diagram:
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. In this example, 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. There is no need for continuous planning. A timeslot is called a problem fact because no Timeslot instances change during solving. Such classes do not require any OptaPlanner-specific annotations.
Room
The Room class represents a location where lessons are taught, for example, Room A or Room B. In this example, all rooms are without capacity limits and they can accommodate all lessons.
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 each 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:
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.
Procedure
Create the
src/main/java/com/example/domain/Timeslot.javaclass:Copy to Clipboard Copied! Toggle word wrap Toggle overflow Notice the
toString()method keeps the output short so it is easier to read OptaPlanner’sDEBUGorTRACElog, as shown later.Create the
src/main/java/com/example/domain/Room.javaclass:Copy to Clipboard Copied! Toggle word wrap Toggle overflow Create the
src/main/java/com/example/domain/Lesson.javaclass:Copy to Clipboard Copied! Toggle word wrap Toggle overflow The
Lessonclass has an@PlanningEntityannotation, so OptaPlanner knows that this class changes during solving because it contains one or more planning variables.The
timeslotfield has an@PlanningVariableannotation, so OptaPlanner knows that it can change its value. In order to find potentialTimeslotinstances to assign to this field, OptaPlanner uses thevalueRangeProviderRefsproperty to connect to a value range provider that provides aList<Timeslot>to pick from. See Section 8.4, “Gather the domain objects in a planning solution” for information about value range providers.The
roomfield also has an@PlanningVariableannotation for the same reasons.
8.3. Define the constraints and calculate the score 复制链接链接已复制到粘贴板!
When solving a problem, a score represents the quality of a specific solution. The higher the score the better. Red Hat build of OptaPlanner looks for the best solution, which is the solution with the highest score found in the available time. It might be the optimal solution.
Because the timetable example 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 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:
Unfortunately, this solution 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.
A better solution is to create a src/main/java/com/example/solver/TimeTableConstraintProvider.java class to perform incremental score calculation. This class uses OptaPlanner’s ConstraintStream API which is inspired by Java 8 Streams and SQL. The ConstraintProvider scales an order of magnitude better than the EasyScoreCalculator: O(n) instead of O(n²).
Procedure
Create the following src/main/java/com/example/solver/TimeTableConstraintProvider.java class:
8.4. Gather the domain objects in a planning solution 复制链接链接已复制到粘贴板!
A TimeTable instance 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.
The TimeTable class has an @PlanningSolution annotation, so Red Hat build of OptaPlanner knows that this class contains all of the input and output data.
Specifically, this class is the input of the problem:
A
timeslotListfield with all time slots- This is a list of problem facts, because they do not change during solving.
A
roomListfield with all rooms- This is a list of problem facts, because they do not change during solving.
A
lessonListfield with all lessons- This is a list of planning entities because they change during solving.
Of each
Lesson:-
The values of the
timeslotandroomfields are typically stillnull, so unassigned. They are planning variables. -
The other fields, such as
subject,teacherandstudentGroup, are filled in. These fields are problem properties.
-
The values of the
However, this class is also the output of the solution:
-
A
lessonListfield for which eachLessoninstance has non-nulltimeslotandroomfields after solving -
A
scorefield that represents the quality of the output solution, for example,0hard/-5soft
Procedure
Create the src/main/java/com/example/domain/TimeTable.java class:
The value range providers
The 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.
8.5. Create the solver service 复制链接链接已复制到粘贴板!
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 data sets in parallel.
Procedure
Create the src/main/java/org/acme/optaplanner/rest/TimeTableResource.java class:
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.
8.6. Set the solver termination time 复制链接链接已复制到粘贴板!
If your planning application does not have a termination setting or a termination event, it theoretically runs forever and in reality eventually causes an HTTP timeout error. To prevent this from occurring, use the optaplanner.solver.termination.spent-limit parameter to specify the length of time after which the application terminates. In most applications, set the time to at least five minutes (5m). However, in the Timetable example, limit the solving time to five second, which is short enough to avoid the HTTP timeout.
Procedure
Create the src/main/resources/application.properties file with the following content:
quarkus.optaplanner.solver.termination.spent-limit=5s
quarkus.optaplanner.solver.termination.spent-limit=5s
8.7. Running the school timetable application 复制链接链接已复制到粘贴板!
After you have created the school timetable project, run it in development mode. In development mode, you can update the application sources and configurations while your application is running. Your changes will appear in the running application.
Prerequisites
- You have created the school timetable project.
Procedure
To compile the application in development mode, enter the following command from the project directory:
./mvnw compile quarkus:dev
./mvnw compile quarkus:devCopy to Clipboard Copied! Toggle word wrap Toggle overflow Test the REST service. You can use any REST client. The following example uses the Linux command
curlto send a POST request: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"}]}'$ 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"}]}'Copy to Clipboard Copied! Toggle word wrap Toggle overflow After the time period specified in
termination spent timedefined in yourapplication.propertiesfile, the service returns output similar to the following example:HTTP/1.1 200 Content-Type: application/json ... {"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"}HTTP/1.1 200 Content-Type: application/json ... {"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"}Copy to Clipboard Copied! Toggle word wrap Toggle overflow 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.
To review what OptaPlanner did during the solving time, review the info log on the server side. The following is sample info log output:
... Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). ... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4). ... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398). ... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).
... Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). ... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4). ... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398). ... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).Copy to Clipboard Copied! Toggle word wrap Toggle overflow
8.7.1. Test the application 复制链接链接已复制到粘贴板!
A good application includes test coverage. This example tests the Red Hat build of OptaPlanner school timetable project on Red Hat build of Quarkus. It uses a JUnit test to generate a test dataset and send it to the TimeTableController to solve.
Procedure
Create the
src/test/java/com/example/rest/TimeTableResourceTest.javaclass with the following content:Copy to Clipboard Copied! Toggle word wrap Toggle overflow 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.propertiesfile:Copy to Clipboard Copied! Toggle word wrap Toggle overflow
Normally, the solver finds a feasible solution in less than 200 milliseconds. Notice how the application.properties file 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 systems. But it does not run a millisecond longer than it strictly must, even on fast systems.
8.7.2. Logging 复制链接链接已复制到粘贴板!
After you complete the Red Hat build of OptaPlanner school timetable project, you can use logging information to help you fine-tune the constraints in the ConstraintProvider. Review the score calculation speed in the info log file to assess the impact of changes to your constraints. Run the application in debug mode to show every step that your application takes or use trace logging to log every step and every move.
Procedure
- Run the school timetable application for a fixed amount of time, for example, five minutes.
Review the score calculation speed in the
logfile as shown in the following example:... Solving ended: ..., score calculation speed (29455/sec), ...
... Solving ended: ..., score calculation speed (29455/sec), ...Copy to Clipboard Copied! Toggle word wrap Toggle overflow -
Change a constraint, run the planning application again for the same amount of time, and review the score calculation speed recorded in the
logfile. Run the application in debug mode to log every step that the application makes:
-
To run debug mode from the command line, use the
-Dsystem property. To permanently enable debug mode, add the following line to the
application.propertiesfile:quarkus.log.category."org.optaplanner".level=debug
quarkus.log.category."org.optaplanner".level=debugCopy to Clipboard Copied! Toggle word wrap Toggle overflow The following example shows output in the
logfile in debug mode:... Solving started: time spent (67), best score (-20init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). ... 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}]). ... 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}]). ...... Solving started: time spent (67), best score (-20init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0). ... 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}]). ... 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}]). ...Copy to Clipboard Copied! Toggle word wrap Toggle overflow
-
To run debug mode from the command line, use the
-
Use
tracelogging to show every step and every move for each step.