Question

I have a classic timetabling problem consisting of the variables classes(~100), rooms(20),terms(8) and weekdays(5).

To just simplfy the problem, following are the reduced constraints.

A day is 9 hours.

Some classes are mandatory for students, and mandatory classes of the terms 1,3,5,7 (and for 2,4,6,8) must not overlap eachother.

Classes have different weights in terms of hours, some are 2 hours, some are 3.

Some classes should be at specific rooms.

There can not be two lectures at the same class at the same time.

I'm going with logilabs python constraint module. And i'm aware that chosing the variables and domains wisely will result in lesser time for solving the problem. Problem is I've never done constraint programming before and having a hard time building up the problem to find out where and what to begin with. For example:

I can set a constraint such as "no two class with same room, same day can overlap eachother's time slot". Or start with " no room can have more than 9 hours reserved on the same day" then continue with reduced solution domain. I estimate(did not try) that the first constraint will take much longer to solve than the other one. But it also requires (i guess) changing of variables and solution domains or a rebuilding of a smaller problem. I'm already a bit lost in variables, domains, intervals, implementations etc.

Long story short, i need some pointers for building up the problem, solution domains, chosing variables wisely etc.

Thanks

UPDATE

Using logilab-constraint package i've made a basic application and uploaded it to github

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top