[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: Jeffrey Kantor
Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints
Date: Fri, 31 May 2013 12:29:10 -0400


The full complexity of this problem is daunting.  36*24*26*5 = 112,320 binary variables which is large by any standard.  Not all of these variables has to be generated, of course, since you can rule out the assignment of some student groups to some classes from the start.  On the other hand, rules on teacher assignments will increase the size of the problem.  There may be some 'secret sauce' for this class of problems, but a frontal assault seems destined for a lot of frustration and troubles.

I've only glanced at the Boland paper, but note it uses 'blocking' as a decomposition strategy. In the end you'll likely need to employ some sort of problem decomposition to make the problem manageable. 

Knowing absolutely nothing about blocking or classroom timetabling, a perhaps naive suggestion would be to use a column generation technique to break the problem into two levels.  The lower level generates a set of viable class schedules satisfying many of the problem constraints, such as no two periods of the same class on the same day, overall time requirements, etc. Think of them as patterns, and there may be a lot of viable patterns. For the lower level problem you would have up to 36*26*5 = 4680 binary assignments to create a class schedule many of which might be avoided when generating the decision variables.  At this point you might also add teacher constraints.

The upper level problem is then to assign students groups to the set of viable class schedules. If you had generated N viable class schedules you'd have 24*N binary assignments with the objective of maximizing the number of assigned students.  If no feasible solution is found, use standard techniques to generate additional class schedules and thereby iterate until a feasible solution is found.

There may be far better ways to break the problem down than this admittedly naive suggestion, but decomposition is a strategy that may be worth a look. The second of your two simplified cases sounds a bit like a decomposition strategy.


reply via email to

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