サポートコンソール開発者トライアルの開始お問い合わせ

12.14. Exam timetabling (ITC 2007 track 1 - Examination)

Schedule each exam into a period and into a room. Multiple exams can share the same room during the same period.

examinationTimetablingUseCase

Hard constraints:

  • Exam conflict: Two exams that share students must not occur in the same period.
  • Room capacity: A room’s seating capacity must suffice at all times.
  • Period duration: A period’s duration must suffice for all of its exams.

  • Period related hard constraints (specified per dataset):

    • Coincidence: Two specified exams must use the same period (but possibly another room).
    • Exclusion: Two specified exams must not use the same period.
    • After: A specified exam must occur in a period after another specified exam’s period.

  • Room related hard constraints (specified per dataset):

    • Exclusive: One specified exam should not have to share its room with any other exam.

Soft constraints (each of which has a parametrized penalty):

  • The same student should not have two exams in a row.
  • The same student should not have two exams on the same day.
  • Period spread: Two exams that share students should be a number of periods apart.
  • Mixed durations: Two exams that share a room should not have different durations.
  • Front load: Large exams should be scheduled earlier in the schedule.
  • Period penalty (specified per dataset): Some periods have a penalty when used.
  • Room penalty (specified per dataset): Some rooms have a penalty when used.

It uses large test data sets of real-life universities.

The problem is defined by the International Timetabling Competition 2007 track 1. Geoffrey De Smet finished 4th in that competition with a very early version of Planner. Many improvements have been made since then.

Problem Size

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.

12.14.1. Domain model for Exam timetabling
リンクのコピー

The following diagram shows the main examination domain classes:

図12.11 Examination domain class diagram

examinationDomainDiagram

Notice that we’ve split up the exam concept into an Exam class and a Topic class. The Exam instances change during solving (this is the planning entity class), when their period or room property changes. The Topic, Period and Room instances never change during solving (these are problem facts, just like some other classes).

Red Hat logoGithubredditYoutubeTwitter

詳細情報

試用、購入および販売

コミュニティー

会社概要

Red Hat は、企業がコアとなるデータセンターからネットワークエッジに至るまで、各種プラットフォームや環境全体で作業を簡素化できるように、強化されたソリューションを提供しています。

多様性を受け入れるオープンソースの強化

Red Hat では、コード、ドキュメント、Web プロパティーにおける配慮に欠ける用語の置き換えに取り組んでいます。このような変更は、段階的に実施される予定です。詳細情報: Red Hat ブログ.

Red Hat ドキュメントについて

Red Hat をお使いのお客様が、信頼できるコンテンツが含まれている製品やサービスを活用することで、イノベーションを行い、目標を達成できるようにします。 最新の更新を見る.

Legal Notice

Theme

© 2026 Red Hatトップに戻る