[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Harley
Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints
Date: Wed, 29 May 2013 11:45:12 +1000
User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:17.0) Gecko/20130509 Thunderbird/17.0.6

Hi Roland,

Timetabling is a wonderfully complex problem to learn to use any modelling 

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.


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?


      Dr. Harley Mackenzie         ABN:   36 348 783 012

      HARD Software                Web:
      PO BOX 8004                  Tel:   +61 3 5222 3435
      Newtown 3220, Australia      Email: address@hidden

reply via email to

[Prev in Thread] Current Thread [Next in Thread]