4.11. 試験の時間割 (ITC 2007 track 1 - 試験)

すべての試験に、時間と部屋を割り当てます。同じ時間帯に同じ部屋で、複数の試験を行うことができるものとします。

examinationTimetablingUseCase

ハード制約:

  • 試験の制約: 同じ学生が受ける 2 つの試験は、同じ時間帯に実施できないものとする。
  • 教室の収容人数: 教室の座席数は、常に受験者数よりも多くなければならない。
  • 期間: 期間は、すべての試験に対応できる長さでなければならない。

  • 期間関連のハード制約 (データセットごとに指定):

    • 一致: 特定の 2 つの試験を同じ時間帯に設定する必要がある (別の教室を使用することも可能)。
    • 除外: 特定の 2 つの試験を同じ時間帯に設定できない。
    • 以降: 特定の試験を、別の特定の試験の後に行う必要がある。

  • 教室関連の制約 (データセットごとに指定):

    • 排他的: 特定の試験を、他の試験と同じ教室で行うことはできない。

ソフト制約 (パラメーター化されたペナルティーがそれぞれ設定されている):

  • 同じ学生が、続けて試験を 2 つ受けてはいけない。
  • 同じ学生が、同じ日に試験を 2 つ受けてはいけない。
  • 時間帯の分散: 同じ学生が受ける 2 つの試験は、時間をある程度あける。
  • 異なる試験の長さ: 教室を共有する 2 つの試験の長さは、同じにする。
  • 前倒し: 規模の大きい試験は、スケジュールを早めに決定する。
  • 期間のペナルティー (データセットごとに指定): 期間によっては、使用されるとペナルティーが発生する。
  • 部屋のペナルティー (データセットごとに指定): 部屋によっては、使用されるとペナルティーが発生する。

実際に大学から取得した大規模な試験データセットを使用します。

この問題は、International Timetabling Competition 2007 track 1 で定義されています。Geoffrey De Smet 氏は、ごく初期段階の Planner を使用して、このコンペティションで 4 位を獲得しました。このコンペティション以降、多くの改良点が加えられています。

問題の規模

exam_comp_set1 has  7883 students,  607 exams, 54 periods,  7 rooms,  12 period constraints and  0 room constraints with a search space of 10^1564.
exam_comp_set2 has 12484 students,  870 exams, 40 periods, 49 rooms,  12 period constraints and  2 room constraints with a search space of 10^2864.
exam_comp_set3 has 16365 students,  934 exams, 36 periods, 48 rooms, 168 period constraints and 15 room constraints with a search space of 10^3023.
exam_comp_set4 has  4421 students,  273 exams, 21 periods,  1 rooms,  40 period constraints and  0 room constraints with a search space of  10^360.
exam_comp_set5 has  8719 students, 1018 exams, 42 periods,  3 rooms,  27 period constraints and  0 room constraints with a search space of 10^2138.
exam_comp_set6 has  7909 students,  242 exams, 16 periods,  8 rooms,  22 period constraints and  0 room constraints with a search space of  10^509.
exam_comp_set7 has 13795 students, 1096 exams, 80 periods, 15 rooms,  28 period constraints and  0 room constraints with a search space of 10^3374.
exam_comp_set8 has  7718 students,  598 exams, 80 periods,  8 rooms,  20 period constraints and  1 room constraints with a search space of 10^1678.

4.11.1. 試験の時間割のドメインモデル

以下の図では、主な試験のドメインクラスを紹介しています。

図4.11 試験のドメインクラスの図

examinationDomainDiagram

試験のコンセプトを、Exam クラスと Topic クラスに分けた点に注意してください。期間または教室のプロパティーを変更し、解 (プランニングエンティティークラス) を求めると、Exam インスタンスが変化します。このとき、Topic インスタンス、Period インスタンス、および Room インスタンスは変化しません (他のクラスと同様、これらも問題ファクトです)。