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

[Roland Roberts]

On 05/30/2013 09:09 PM, Jeffrey Kantor wrote:
> 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.

There are 36 classes, 24 student groups, 26 periods, 5 days. For any 
given student group, there are only 12 classes open. As an example, for 
grade 6 there are two distinct class offerings for each of the core 
subjects of math, English, science, and social studies (a standard and 
advanced class). Any particular student will be in only 4. At present, 
if you are in the standard math class, you are also in the standard 
English, science and social studies classes. It seems like that ought to 
help reduce the number of variables, but I don't see how right now, and 
our principal would like to relax that, at least in the 8th grade as the 
city has tasked us with opening the advanced classes to more students.

> 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?

Any feasible solution will work.

Using student groups instead of students already deals with some of the 
symmetry dropping the 360 students to 24 groups. There are other partial 
symmetries; the grade 6 students are broken into 8 distinct groups, but 
for most of their classes they will function as 4 distinct groups. We 
had started with using 13 periods (each 30 minutes long); most classes 
would span double periods a few would span triple. That runs afoul of 
some teacher's union contracts on minimum time for lunch break and prep 
periods. Using 26 15-minute periods allows us to accommodate class 
durations from 30-minutes (for student lunch periods and "advisory" 
periods) up to 90 minutes (for certain lab classes).

The school is a small grade 6-8 "middle" school. The sort of tight 
constraints on scheduling are, near as I can tell from reading, normal 
for this type of school. In principle, we have to insure that every 
student is fully scheduled. In practice, I don't think I have to specify 
that and can leave blank spots in the student schedules. We'll simply 
find some extracurricular activity, service project, or "elective" class 
to slot into any holes, so most of the timetabling for a particular 
student group will be to fill at least a minimum number of periods for 
the various classes (to meet state/city instructional time limits).

> 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.

What I was thinking of doing is trying to schedule only one grade level 
and ignore teacher constraints (which you'll notice I haven't even 
mentioned previously). The other simplified case I was thinking of doing 
is just finding solutions for the current case which is 8 45-minute 
periods and 12 student groups; it's still 12 classes/grade. The reduced 
number of student groups is because we would not split the groups for 
certain classes.  We still have some classes which are double periods, 
so I think that still has all the features of the full problem but a 
smaller set of variables.

I'm still reading the paper by Boland et al, but my day job keeps 
getting in the way of working on this except in dribs and drabs.

roland

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