Geoffrey De Smet is the OptaPlanner lead. Geoffrey has posted 16 posts at DZone. You can read more from them at their website. View Full User Profile

# The Examination Timetabling Problem

11.11.2009
| 7840 views |

Next week I 'll give a presentation about the timetabling problem at Devoxx. But what is it exactly? In the examination timetabling problem we need to assign exams to periods (AKA timeslots) and to rooms. Each student takes several exams. This would be easy, except for the 14 distinct constraints that need to be respected as much as possible. For example, a student cannot take 2 exams at the same time. Or, a student does not like to have 2 exams on the same day. This diagram shows a tiny examination problem:

On the top you can see which students takes which exams. For example, Ann (student A) takes History and Math. But Bobby and Carla also take the History exam. There are only 3 periods (monday morning, friday morning and friday afternoon) and 2 rooms (X with 4 seats and Y with 3 seats) available.

So we need to write an algorithm that assigns each exam to a period and also to a room. In practice for real-world university examinations, brute force (or even branch-and-bound) takes more then a billion years. So we need a faster, maybe less perfect algorithm.

The Example 1 algorithm schedules the biggest exams into the biggest rooms first, but it broke a couple of constraints. Greg (student G) has to take the Geo and Eng exams at the same time. And both Edna and Fred aren't too happy because they each have 2 exams on Friday.

The Drools Solver algorithm does a better job, but still gives Edna 2 exams on Friday, which is actually unavoidable because she has 3 exams and there are only 3 periods.

Wondering how Drools Solver does this? Come to my BOF presentation on Examination timetabling with Drools Solver at Devoxx on monday 16 november at 8PM! Or you can just download the example from the Drools webpage.

Published at DZone with permission of its author, Geoffrey De Smet.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

### Slikrek Slikrek1 replied on Sun, 2009/11/22 - 11:11pm

HI Geoffrey, Which package can be used for Patient Admission Scheduling .. please could you put the link and the package name ? Best Regards Slikrek

### Tommy Green replied on Thu, 2010/11/04 - 11:34pm

Geoffrey that is a perfect piece but I have a question for now, can it be applicable to all other schedules for instance studying timetable and working out schedule with of course a little tilt here and there I am waiting for the reply. - Jordan

### Geoffrey De Smet replied on Fri, 2010/12/03 - 7:56am in response to: Tommy Green

Tommy: yes. the examples include curriculum course (= lesson scheduling), examination (= exam scheduling), pas (= patient admission scheduling = hospital bed planning) and more. It's been used for conference talk scheduling too.