Over a million developers have joined DZone.
Platinum Partner

The Examination Timetabling Problem

· Java Zone

The Java Zone is brought to you in partnership with JetBrains.  Learn more about Kotlin, a new programming language designed by JetBrains to solve problems that software developers face every day.

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:

Examination timetabling 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.


The Java Zone is brought to you in partnership with JetBrains.  Discover how powerful static code analysis and ergonomic design make development not only productive but also an enjoyable experience.


{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}