Drools Solver solves planning problems. In this session, we'll take a look at the use case of examination timetabling: We will automatically assign exams to periods and rooms, while respecting the physical resources and while make the enrolled students as happy as possible.
First, we 'll see how we can easily define a scalable score function by using the drools rule engine with little or no impact on our (JPA annotated?) domain classes. Constraints such as these become maintainable and readable:
The hard constraints have to be fulfilled:
- No student can attend 2 exams in the same period.
- No exam can take longer than the period's duration.
- No room must exceed it's available seating.
The soft constraints should be fulfilled as much as possible (according to their weight):
- Students don't like to attend 2 exams in the same day.
- It is distracting to have exams of different durations in the same room in the same period.
- Students don't like large exams near the end of the schedule.
Secondly, we'll investigate how we can find a good solution for real world data sets. Even a small university's schedule with 934 exams, 36 periods and 48 rooms has an astonishing 10^5000 possible solutions. We'll use different Drools Solver algorithms such as its tabu search and come up with feasible solutions in mere minutes.
This use case is defined by the International Timetabling Competition 2007. It uses large data sets from real-world institutions. Geoffrey, lead developer of Drools Solver, participated in the competition with an early, untweaked version of his Drools Solver and finished 4th. Much has been improved meanwhile. The complete example (as well as several others) is available for download from the Drools website.
For more information about Drools Solver, take a look a the Drools team blog or the Drools Solver reference manual.
Geoffrey De Smet is a member of the Drools team and the Drools Solver lead developer. He has years of experience with many Java technologies such as JPA, Spring, JEE, ...