[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Newbie scheduling problem question, contiguous time inte

From: Harley
Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints
Date: Wed, 29 May 2013 13:13:41 +1000
User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:17.0) Gecko/20130509 Thunderbird/17.0.6

There are a few examples that I could find. A good introductory presentation is:

That has a problem with some similarities that may be good to work through. Of note is their easier problem took 48 hours to solve!

And Natasha Boland (et al) from our local Melbourne University has a general paper on modelling techniques for school timetabling:

A good overall resource for all things GLPK is the GLPK wikibook (apart from the GLPK docs that I assume you have found):

You could try posting your entire model on the group for more direct assistance as others have done. It is hard to see exactly what you are doing form the excerpt.


On 29/05/13 12:44 PM, Roland Roberts wrote:
On 05/28/2013 09:45 PM, Harley wrote:
Hi Roland,

Timetabling is a wonderfully complex problem to learn to use any modelling 

You can formulate constraints across the time periods ie. p, p-1, p-2 to ensure that the scheduled classes form blocks rather than allow splitting. Having done a number of timetabling and scheduling problems, there probably is another hard constraint or maybe a soft constraint with a substantial penalty to ensure that not more than one block per class can be scheduled on any one day. If that is a hard constraint for your problem, then you can simplify the formulation of the constraint to ensure that there are always contiguous class blocks.

There are examples out there for many formulations but if you define a start period, and end period variable for each class then the constraint could be that no of scheduled class modules = end_period for class c - start_period for class c + 1 for and given day d.

I understand this constraint in a general fashion. I'm having trouble converting it to code. I've probably tackled a harder problem than I should really be starting with :-(

If I think of the scheduling problem as this 4-dimensional array to fill in, X[c,g,p,d], then I have constraints like these

# All students have to be scheduled *something* for every period.
sum {c in classes, p in 1..26} X[c,g,d,p] = 26

# Math requires a minimum of 15 modules per week
sum {c in MATH, p in 1..26, d in 1..5} >= 15

Similar constraints apply for other classes, and the above is a bit abstract (there are actually multiple math classes and only certain student groups take certain ones).

I had though of formulating the problem as one of choosing starting periods for a particular (class,group,day) as p0[c,g,d] with a duration of n[c,g,d] then I get constraints like

p0[c,g,d] >= 1
# 6 hours in school 24 daily periods
p0[c,g,d] + n[c,g,d] <= 24

But I'm confused on how to connect the two sets of constraints. In the first formulation, p0 through p0+n are just indices in X.

I'm sure this is a matter of "you should read the manual about feature Q." It's also possible I'm trying to make the problem specification more compact than is really possible, but the set of classes is small (about 20), the number of student groups is small (about 12) and the periods and days are also small sets.

I'm also good with being told that I really need to work through some set of tutorial problems first (suggestions on which ones might be useful?). I know that I'm trying to jump straight to the problem I really want to solve and that I'm being impatient :-)


               PGP Key ID: 66 BC 3B CD
Roland B. Roberts, PhD                             RL Enterprises
address@hidden                            6818 Madeline Court
address@hidden                           Brooklyn, NY 11220

     Dr. Harley Mackenzie         ABN:   36 348 783 012

     HARD Software                Web:
     PO BOX 8004                  Tel:   +61 3 5222 3435
     Newtown 3220, Australia      Email: address@hidden

reply via email to

[Prev in Thread] Current Thread [Next in Thread]