[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Newbie scheduling problem question, contiguous time inte
From: |
Roland Roberts |
Subject: |
Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints |
Date: |
Tue, 28 May 2013 22:44:31 -0400 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130514 Thunderbird/17.0.6 |
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
- [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Roland Roberts, 2013/05/28
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Harley, 2013/05/28
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints,
Roland Roberts <=
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Michael Hennebry, 2013/05/29
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Roland Roberts, 2013/05/29
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Michael Hennebry, 2013/05/29
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Michael Hennebry, 2013/05/30
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Jeffrey Kantor, 2013/05/30
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Roland Roberts, 2013/05/31
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Jeffrey Kantor, 2013/05/31
- Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints, Michael Hennebry, 2013/05/31