第10章 Red Hat build of Quarkus プラットフォーム上の Red Hat build of OptaPlanner: 時間割のクイックスタートガイド
本書では、Red Hat build of OptaPlanner の制約解決人工知能 (AI) を使用して Red Hat build of Quarkus アプリケーションを作成するプロセスを説明します。学生および教師向けの時間割を最適化する REST アプリケーションを構築していきます。
サービスは、AI を使用して、以下のハードおよびソフトの スケジュール制約 に準拠し、Lesson インスタンスを Timeslot インスタンスと Room インスタンスに自動的に割り当てます。
- 1 部屋に同時に割り当てることができる授業は、最大 1 コマです。
- 教師が同時に一度に行うことができる授業は最大 1 回です。
- 生徒は同時に出席できる授業は最大 1 コマです。
- 教師は、1 つの部屋での授業を希望します。
- 教師は、連続した授業を好み、授業間に時間が空くのを嫌います。
数学的に考えると、学校の時間割は NP 困難 の問題であります。つまり、スケーリングが困難です。総当たり攻撃で考えられる組み合わせを単純にすべて反復すると、スーパーコンピューターを使用したとしても、非自明的なデータセットを取得するのに数百年かかります。幸い、Red Hat build of OptaPlanner などの AI 制約ソルバーには、妥当な時間内にほぼ最適なソリューションを提供する高度なアルゴリズムがあります。妥当な期間として考慮される内容は、問題の目的によって異なります。
前提条件
- OpenJDK 11 以降がインストールされている。Red Hat ビルドの Open JDK は Red Hat カスマーポータル (ログインが必要) の ソフトウェアダウンロード ページから入手できます。
- Apache Maven 3.8 以降がインストールされている。Maven は Apache Maven Project の Web サイトから入手できます。
- IntelliJ IDEA、VSCode、Eclipse などの IDE が利用できる。
- Red Hat build of OptaPlanner の Red Hat build of Quarkus プロジェクトが利用できる。Red Hat build of OptaPlanner の Red Hat build of Quarkus プロジェクトの作成方法は、Red Hat build of OptaPlanner のスタートガイド セクションの OptaPlanner および Quarkus の概要 を参照してください。
10.1. ドメインオブジェクトのモデル化 リンクのコピーリンクがクリップボードにコピーされました!
Red Hat build of OptaPlanner の時間割プロジェクトの目標は、レッスンごとに時間枠と部屋に割り当てることです。これには、次の図に示すように、Timeslot、Lesson、および Room の 3 つのクラスを追加します。
Timeslot
Timeslot クラスは、Monday 10:30 - 11:30、Tuesday 13:30 - 14:30 など、授業の長さを表します。この例では、時間枠はすべて同じ長さ (期間) で、昼休みまたは他の休憩時間にはこのスロットはありません。
高校のスケジュールは毎週 (同じ内容が) 繰り返されるだけなので、時間枠には日付がありません。また、継続的プランニング は必要ありません。解決時に Timeslot インスタンスが変更しないため、Timeslot は 問題ファクト と呼ばれます。このようなクラスには OptaPlanner 固有のアノテーションは必要ありません。
Room
Room クラスは、Room A、Room B など、授業の場所を表します。以下の例では、どの部屋も定員制限がなく、すべての授業に対応できます。
Room インスタンスは解決時に変化しないため、Room は 問題ファクト でもあります。
Lesson
授業中 (Lesson クラスで表現)、教師は複数の生徒に Math by A.Turing for 9th grade、Chemistry by M.Curie for 10th grade などの教科を指導します。ある教科について、毎週複数回、同じ教師が同じ生徒グループを指導する場合は、Lesson インスタンスが複数使用されますが、それらは id で識別可能です。たとえば、9 年生の場合は、1 週間に 6 回数学の授業があります。
解決中に、OptaPlanner は、Lesson クラスの timeslot フィールドと room フィールドを変更して、各授業を、時間枠 1 つ、部屋 1 つに割り当てます。OptaPlanner はこれらのフィールドを変更するため、Lesson は プランニングエンティティー となります。
前図では、オレンジのフィールド以外のほぼすべてのフィールドに、入力データが含まれています。授業の timeslot フィールドと room フィールドは、入力データに割り当てられておらず (null)、出力データに割り当てられて (null ではない) います。Red Hat build of OptaPlanner は、解決時にこれらのフィールドを変更します。このようなフィールドはプランニング変数と呼ばれます。このフィールドを OptaPlanner に認識させるには、timeslot フィールドと room のフィールドに @PlanningVariable アノテーションが必要です。このフィールドに含まれる Lesson クラスには、@PlanningEntity アノテーションが必要です。
手順
src/main/java/com/example/domain/Timeslot.javaクラスを作成します。Copy to Clipboard Copied! Toggle word wrap Toggle overflow 後述しているように、
toString()メソッドで出力を短くするため、OptaPlanner のDEBUGログまたはTRACEログの読み取りが簡単になっています。src/main/java/com/example/domain/Room.javaクラスを作成します。Copy to Clipboard Copied! Toggle word wrap Toggle overflow src/main/java/com/example/domain/Lesson.javaクラスを作成します。Copy to Clipboard Copied! Toggle word wrap Toggle overflow Lessonクラスには@PlanningEntityアノテーションが含まれており、その中にプランニング変数が 1 つ以上含まれているため、OptaPlanner はこのクラスが解決時に変化することを認識します。timeslotフィールドには@PlanningVariableアノテーションがあるため、OptaPlanner は、このフィールドの値が変化することを認識しています。このフィールドに割り当てることのできるTimeslotインスタンスを見つけ出すために、OptaPlanner はvalueRangeProviderRefsプロパティーを使用して値の範囲プロバイダーと連携し、List<Timeslot>を提供して選択できるようにします。値の範囲プロバイダーに関する詳細は、「プランニングソリューションでのドメインオブジェクトの収集」 を参照してください。roomフィールドにも、同じ理由で@PlanningVariableアノテーションが含まれます。