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.
If you can provide code or more details, then I may be able to assist further. There are examples of
formulations of timetabling models available, although they may be written for other languages such
as AMPL (very close to Mathprog) or GAMS but they should provide insight into your problem.
Some complex timetabling may take a long time to solve with GLPK although once the model is
formulated you could try many of the cutting plane options and other techniques to see if they help
your specific problem. Also if the entire model isnt solving or not in a reasonable time frame,
other options include using a version of Coin-CBC with MathProg (from GLPK) as Coin-CBC solves a
larger range of MILP problems and uses multi-core processes or get to know someone really well who
has an AMPL/CPLEX|XPRESS|GUROBI licence.
Harley
On 29/05/13 10:32 AM, Roland Roberts wrote:
I'm a newbie to MILP and am stuck on specifying what I think should be a pretty common problem.
I'm trying to solve a student class scheduling problem for a middle school. I can formulate parts
of the problem, but am drawing a blank on connecting everything. I'm willing to pick up both
manuals and texts if someone can point me to ones that should be helpful.
The basic problem is that I classes c, student groups g, time periods p, and days d. We're
breaking each day into 15-minute "modules" which have to be schedule. A class has to span 3-8
modules on any give day. Some classes have a minimum number of modules per week that have to be
completed. With just the above, I can specify the constraints by thinking of this as a
4-dimensional array X[c,g,p,d] and the constraints are various sums. The problem I run into is
specifying the the continuity constraint on scheduling. It's not sufficient to have 3 modules for
class C1, they have to be 3 contiguous modules.
How do I specify this sort of thing?
roland
--
------------------------------------------------------------------
Dr. Harley Mackenzie ABN: 36 348 783 012
HARD Software Web: www.hardsoftware.com
PO BOX 8004 Tel: +61 3 5222 3435
Newtown 3220, Australia Email: h...@hardsoftware.com
------------------------------------------------------------------
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
