Solving the Examination problem part 1: Domain diagram

The examination problem is one of the examples in drools-solver. It has a number of exams, students, periods and rooms. A student is enrolled into multiple exams. Each exam needs to be scheduled into a period and into a room. Multiple exams can share the same room during the same period.

There are a number of hard constraints that cannot be broken:

  • Exam conflict: 2 exams that share students should not occur in the same period.
  • Room capacity: A room’s seating capacity should suffice at all times.
  • Period duration: A period’s duration should suffice for all of its exams.
  • Period related hard constraints should be fulfilled:

    • Coincidence: 2 exams should use the same period (but possibly another room).
    • Exclusion: 2 exams should not use the same period.
    • After: 1 exam should occur in a period after another exam’s period.
  • Room related hard constraints should be fulfilled:

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

There are also a number of soft constraints that should be minimized (each of which has parameterized penalty’s):

  • 2 exams in a row.
  • 2 exams in a day.
  • Period spread: 2 exams that share students should have a number of periods between them.
  • Mixed durations: 2 exams that share a room should not have different durations.
  • Front load: Large exams should be scheduled earlier in the schedule.
  • Period penalty: Some periods have a penalty when used.
  • Room penalty: Some rooms have a penalty when used.

It uses large test data sets of real-life universities. You can find more information here.

So let’s take a look at the domain diagram:

The first dataset has 7883 students, 607 exams, 54 periods and 7 rooms. That makes over 10 to the power 1052 possible solutions. Another dataset even has 10^5761 possible solutions. This means that a brute force algorithm is not an option, unless you can wait over 10^5700 years.

In upcoming blogs, I ‘ll take a deeper look into the implementation and how to deal which such a massive search space. Continue with the next part of this blog series.

Comments are closed.