Friday, February 22, 2008

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.