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.
