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

[Jeffrey Kantor]

Hi Roland,

Before going into some thoughts regarding the modeling aspects, could you tell us about the scale of your problem?  For example, if there are, say, 20 classes, 10 student groups, 26 periods, and 5 days, then you have 20*10*26*5 = 26,000 binary variables in your assignment formulation. That's a pretty large number. 

Moreover, there may be quite a  bit of symmetry in your solution space which would need to be addressed for a problem of this scale. Can you clarify what you mean by solving the problem? For example, is any feasible solution good enough?  Or is there some specific criterion you trying to optimize?

As a suggestion, developing solutions to problems like this can be pretty challenging.  So it might make sense to look at some simplified cases and special cases, and perhaps test some problem specific heuristics.

Jeff

On Thu, May 30, 2013 at 11:14 AM, Michael Hennebry <address@hidden> wrote:

On Wed, 29 May 2013, Roland Roberts wrote:

On 05/29/2013 01:27 PM, Michael Hennebry wrote:

On Tue, 28 May 2013, Roland Roberts wrote:

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?

Is each class a fixed length?

No, that's the first thing the school wants to relax with the modular

My previous constraints were necessary, but not sufficient.
They would allow breaking the day into 3 or
more parts with middle parts being too short.

The following are sufficient
to ensure all blocks have at least 4 periods:

X[c,g,p1,d]-X[c,g,p2,d]+X[c,g,p3,d]>=0   for p1< p2< p3<=p1+4, c,g,d...

where periods outside of a day are implictly 0.

Note that the constraints are numerous (quadratic
in the size of a minimum block) and rather loose.

--
Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk