### 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.