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