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

[Harley]

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: address@hidden
> ------------------------------------------------------------------