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
| 7741 views |
  • submit to reddit

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.

 

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

Comments

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.

You can see some use cases here.

Shams Imran replied on Sun, 2011/02/20 - 3:40pm

It is really hard to think in depth about this subject. I appreciate your efforts about this article. I have heard much about this country and the particular class in the country but never got a chance to get a deep idea about its economical and social structure. I read the whole article and found it impressive and appreciable. I was not much even aware with the concept of mine workers in Bolivia. I am thankful for such wonderful information on the subject.Steiner Predator Binoculars

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.