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

[Roland Roberts]

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 
scheduling. Even now, a few classes hold a weekly "double-period" but 
everything is hand scheduled which basically works by severely limiting 
what is offered to students. The attempt this past year to hand schedule 
under the new paradigm was a failure as hand scheduling never resolved 
the conflicts that we kept running into.

> If so, the start time determines the end time.
> Your array works if p, d refer to the start times.

In my thinking, p referred to a time slot, not necessarily the start 
time. I'm reading the paper by Boland et al., and think I'll be in a 
better position to describe my setup coherently once I get through that. 
At the very least, I'll have a consistent set of terminology to describe 
what I'm trying to do.

> If c1, g1 requires 4 periods and c2, g2 requires 7 periods:
> If c1, g1 starts in period p1, then c2, g2 may not start in p1-6..p1+3
>
>  p1+3
>  SUM X[c2, g2, k, d] <= 1-X[c1, g1, p1, d]  for c2, g2, d, c1, g1, p1...
> k=p1-6

Let me think about that a little. c1, g1 won't constrain c2, g2 that way 
since it's a both a different class and a different group of students, 
think c1=6th grade math, c2=6th grade English. But you've got me 
thinking since c1, g1 will constrain c2, g1.

roland

--
                       PGP Key ID: 66 BC 3B CD
Roland B. Roberts, PhD                             RL Enterprises
address@hidden                            6818 Madeline Court
address@hidden                           Brooklyn, NY 11220