第13章 OptaPlanner と Java の Red Hat ビルド: 学校の時間割のクイックスタートガイド

本書では、OptaPlanner の制約解決人工知能 (AI) を使用してシンプル Java アプリケーションを作成するプロセスを説明します。生徒と教師のために学校の時間割を最適化するコマンドラインアプリケーションを作成します。

...
INFO  Solving ended: time spent (5000), best score (0hard/9soft), ...
INFO
INFO  |            | Room A     | Room B     | Room C     |
INFO  |------------|------------|------------|------------|
INFO  | MON 08:30  | English    | Math       |            |
INFO  |            | I. Jones   | A. Turing  |            |
INFO  |            | 9th grade  | 10th grade |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 09:30  | History    | Physics    |            |
INFO  |            | I. Jones   | M. Curie   |            |
INFO  |            | 9th grade  | 10th grade |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 10:30  | History    | Physics    |            |
INFO  |            | I. Jones   | M. Curie   |            |
INFO  |            | 10th grade | 9th grade  |            |
INFO  |------------|------------|------------|------------|
...
INFO  |------------|------------|------------|------------|

アプリケーションは、AI を使用してハードスケジュールとソフトスケジュールの 制約 を順守することにより、Lesson インスタンスを タイムスロット インスタンスと Room インスタンスに自動的に割り当てます。次に例を示します。

  • 1 部屋に同時に割り当てることができる授業は、最大 1 コマです。
  • 教師が同時に一度に行うことができる授業は最大 1 回です。
  • 生徒は同時に出席できる授業は最大 1 コマです。
  • 教師は、すべてのレッスンを同じ部屋で教えることを好みます。
  • 教師は、連続した授業を好み、授業間に時間が空くのを嫌います。
  • 生徒は、同じ科目の連続したレッスンを嫌います。

数学的に考えると、学校の時間割は NP 困難 の問題であります。これは、スケーリングが困難であることを意味します。すべての可能な組み合わせを単純に総当たりで反復すると、スーパーコンピューター上でさえ、自明ではないデータセットに対して数百万年かかります。幸い、OptaPlanner などの AI 制約ソルバーには、妥当な時間内にほぼ最適なソリューションを提供する高度なアルゴリズムがあります。

前提条件

  • OpenJDK (JDK) 11 がインストールされている。Red Hat ビルドの Open JDK は Red Hat カスマーポータル (ログインが必要) の ソフトウェアダウンロード ページから入手できます。
  • Apache Maven 3.6 以降がインストールされている。Maven は Apache Maven Project の Web サイトから入手できます。
  • IntelliJ IDEA、VSCode、Eclipse などの IDE

13.1. Maven または Gradle ビルドファイルを作成し、依存関係を追加する

OptaPlanner 学校の時間割アプリケーションには、Maven または Gradle を使用できます。ビルドファイルを作成したら、次の依存関係を追加します。

  • 学校の時間割問題を解決するための optaplanner-core (コンパイルスコープ)
  • optaplanner-test (テストスコープ) から JUnit への学校の時間割の制約のテスト
  • OptaPlanner が実行するステップを表示するための logback-classic (ランタイムスコープ) などの実装

手順

  1. Maven または Gradle ビルドファイルを作成します。
  2. optaplanner-coreoptaplanner-test、および logback-classic の依存関係をビルドファイルに追加します。

    • Maven の場合、次の依存関係を pom.xml ファイルに追加します。

        <dependency>
          <groupId>org.optaplanner</groupId>
          <artifactId>optaplanner-core</artifactId>
        </dependency>
      
        <dependency>
          <groupId>org.optaplanner</groupId>
          <artifactId>optaplanner-test</artifactId>
          <scope>test</scope>
        </dependency>
      
        <dependency>
          <groupId>ch.qos.logback</groupId>
          <artifactId>logback-classic</artifactId>
          <version>1.2.3</version>
        </dependency>

      次の例は、完全な 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>
      
        <groupId>org.acme</groupId>
        <artifactId>optaplanner-hello-world-school-timetabling-quickstart</artifactId>
        <version>1.0-SNAPSHOT</version>
      
        <properties>
          <maven.compiler.release>11</maven.compiler.release>
          <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
      
          <version.org.optaplanner>8.11.1.Final-redhat-00006</version.org.optaplanner>
          <version.org.logback>1.2.3</version.org.logback>
      
          <version.compiler.plugin>3.8.1</version.compiler.plugin>
          <version.surefire.plugin>3.0.0-M5</version.surefire.plugin>
          <version.exec.plugin>3.0.0</version.exec.plugin>
        </properties>
      
        <dependencyManagement>
          <dependencies>
            <dependency>
              <groupId>org.optaplanner</groupId>
              <artifactId>optaplanner-bom</artifactId>
              <version>${version.org.optaplanner}</version>
              <type>pom</type>
              <scope>import</scope>
            </dependency>
            <dependency>
              <groupId>ch.qos.logback</groupId>
              <artifactId>logback-classic</artifactId>
              <version>${version.org.logback}</version>
            </dependency>
          </dependencies>
        </dependencyManagement>
      
        <dependencies>
          <dependency>
            <groupId>org.optaplanner</groupId>
            <artifactId>optaplanner-core</artifactId>
          </dependency>
          <dependency>
            <groupId>ch.qos.logback</groupId>
            <artifactId>logback-classic</artifactId>
            <scope>runtime</scope>
          </dependency>
      
          <!-- Testing -->
          <dependency>
            <groupId>org.optaplanner</groupId>
            <artifactId>optaplanner-test</artifactId>
            <scope>test</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.codehaus.mojo</groupId>
              <artifactId>exec-maven-plugin</artifactId>
              <version>${version.exec.plugin}</version>
              <configuration>
                <mainClass>org.acme.schooltimetabling.TimeTableApp</mainClass>
              </configuration>
            </plugin>
          </plugins>
        </build>
      
        <repositories>
          <repository>
            <id>jboss-public-repository-group</id>
            <url>https://repository.jboss.org/nexus/content/groups/public/</url>
            <releases>
              <!-- Get releases only from Maven Central which is faster. -->
              <enabled>false</enabled>
            </releases>
            <snapshots>
              <enabled>true</enabled>
            </snapshots>
          </repository>
        </repositories>
      </project>
    • Gradle の場合、次の依存関係を gradle.build ファイルに追加します。

      dependencies {
          implementation "org.optaplanner:optaplanner-core:${optaplannerVersion}"
          runtimeOnly "ch.qos.logback:logback-classic:${logbackVersion}"
      
          testImplementation "org.optaplanner:optaplanner-test:${optaplannerVersion}"
      }

      次の例は、完成した gradle.build ファイルを示しています。

      plugins {
          id "java"
          id "application"
      }
      
      def optaplannerVersion = "{project-version}"
      def logbackVersion = "1.2.3"
      
      group = "org.acme"
      version = "0.1.0-SNAPSHOT"
      
      repositories {
          mavenCentral()
      }
      
      dependencies {
          implementation "org.optaplanner:optaplanner-core:${optaplannerVersion}"
          runtimeOnly "ch.qos.logback:logback-classic:${logbackVersion}"
      
          testImplementation "org.optaplanner:optaplanner-test:${optaplannerVersion}"
      }
      
      java {
          sourceCompatibility = JavaVersion.VERSION_11
          targetCompatibility = JavaVersion.VERSION_11
      }
      
      compileJava {
          options.encoding = "UTF-8"
          options.compilerArgs << "-parameters"
      }
      
      compileTestJava {
          options.encoding = "UTF-8"
      }
      
      application {
          mainClass = "org.acme.schooltimetabling.TimeTableApp"
      }
      
      test {
          // Log the test execution results.
          testLogging {
              events "passed", "skipped", "failed"
          }
      }