Building up timetabling problem with lots of variables

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 开发者_Go百科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

Take a look at the curriculum course example code of Drools Planner. It's basically the same thing, but the terminology is slightly different: each course (= class) has a number of lectures which need to be scheduled into a room (=room) and period (= each term on each weekday is a period).

The trick is to keep a clean domain model and keep that separate from your constraint rules. Because your classes have different weights in terms of hours, I suggest that a Lecture is only assigned a startingPeriod so it's not a lot of code to move a Lecture to another set of Period (just reassign the first Period).

I've ended up with a solution that bundles "chosing the variables wisely" and "reducing the domains at selection". Below are the snippets from the django based timetabling application i'm doing:

class Course(models.Model):
    name = models.CharField(max_length=255, null=False, blank=False)
    duration = models.PositiveSmallIntegerField(blank=False)
    type = models.ForeignKey(CourseType, blank=False, null=False)
    mandatory = models.BooleanField(default=False)
    '''
        following are the basic constraints  
    '''
    days = models.ManyToManyField(Day, blank=True, null=True)
    terms = models.ManyToManyField(Term)
    rooms = models.ManyToManyField('ClassRoom', blank=True, null=True)


    def __unicode__(self):
        return u'%s' % self.name   

I've embedded the basic constraints into the classes, such as "this course may be on monday or tuesday, in terms 1 or 2 or 3 in rooms 1 or 2 or 3 or 4or 5",which allows me to directly apply these basic constraints at the beginning when selecting the courses from database.

General constraints such as "no two courses can be at the same room inbetween the same hours on the same day" are applied to reduced variable domains coming from the selection done in database.

Seems to be working for now.