[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: Michael Hennebry
Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints
Date: Fri, 31 May 2013 13:18:49 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Fri, 31 May 2013, Roland Roberts wrote:

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

You will have a symmetry whenever you can generate a new
solution by renumbering the variables on an old solution.

I expect your problem is symmetric about midweek:
Swapping Monday-Friday and Tuesday-Thursday would not invalidate a solution.
I expect your problem is symmetric about midday:
Reversing the order of periods would not invalidate a solution.
I expect that there are sets of equivalent (class, group) pairs.

To deal with midweek symmetry require
SUM  q[d]*X[d]  >=0,

where q=[-2, -1, 0, 1, 2]

Midday symmetry could be handled similarly.

Suppose (c1, g1), (c2, g2) and (c3, g3) are equivalent.

SUM q[p,d]*X[c3,g3,p,d] >= SUM q[d,p]*X[c2,g2,p,d] >= SUM q[d,p]*X[c1,g1,p,d]
d,p                        d,p                        d,p

where q is nonzero

Any feasible solution will work.

Use depth-first.
Pick a real good objective.

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

reply via email to

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