
From:  Harley 
Subject:  Re: [Helpglpk] Newbie scheduling problem question, contiguous time interval constraints 
Date:  Wed, 29 May 2013 11:45:12 +1000 
Useragent:  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 environment!You can formulate constraints across the time periods ie. p, p1, p2 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 CoinCBC with MathProg (from GLPK) as CoinCBC solves a larger range of MILP problems and uses multicore processes or get to know someone really well who has an AMPL/CPLEXXPRESSGUROBI 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 15minute "modules" which have to be schedule. A class has to span 38 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 4dimensional 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 
[Prev in Thread]  Current Thread  [Next in Thread] 