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

[Roland Roberts]

On 05/28/2013 09:45 PM, Harley wrote:
> Hi Roland,
>
> Timetabling is a wonderfully complex problem to learn to use any 
> modelling environment!
>
> 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 :-)

roland

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