[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: Roland Roberts
Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints
Date: Fri, 31 May 2013 08:45:53 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130509 Thunderbird/17.0.6

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.


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

reply via email to

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