The way I envision any scheduling system to work is by (1) a brute force program generating a feasible but poor schedule subject to hard constraints and (2) some probabilistic algorithm(s) optimizing said poor schedule given a number of things to weigh in.
I’ve already written a quick brute force program 1. The result is the attached file. Please look at the attached file, and consider why the schedule is so poor. In order for the schedule to get better, we need to figure out what makes a schedule good and what data we will need in order to measure that. Some of this is tricky since it’s so intuitive.
I’ve written below a list of what I think are some pieces missing. Any text in square brackets ([….]) are data that I’ve identified we will likely need/use in order to implement the constraint.
FEASIBILITY PROBLEMS (aka hard constraints)
- For Splash, some timeslots only work with certain grade ranges. Timeslots don’t know this. I’m not sure how we should encode this type of constraint, but we would need to somewhere.
- prereqs?
- Class blocking. Similar to prereqs. For Splash 2008 I taught the Theory of Optimization I and II. Even though they were two classes, they were designed such that some students could take both and it would essentially be one long class. This only works if it takes the same room and have consecutive times. Fortunately for me humans can deal with this, but we might need to somehow encode this information. I’m sure this isn’t the only scenario that uses blocking of classes.
OPTIMIZATION PROBLEMS (aka soft constraints)
- Even course distribution. There should be an approximately equal number of student slots each time period. There might be a discussion of # student slots / vs. # of classes. Also, we may want to be able to tweak this and perhaps have the early Saturday morning have fewer classes than later on. [an idea of desired distribution vs time]
- Right classroom size. A class for 8 people should not go in a lecture hall. We should strive to make the number of students match for both class and room. [max_students…]
- Some of the classroom assignments are very poor. From looking at it it seems that a strict resources-aware constraint would help this considerably. Lobby 13 won’t get classes that require blackboards, if it doesn’t have them. (Or desks, for that matter?) [Resources]
- Course distribution part II. Course distribution is not just about # of classes and students, but also how likely students are to meet conflicts. Thus, we should strive to have an even number of classes different categories etc. [Class similarities]
- Geographical clustering. Directors do this all the time. They put math classes in one building while they put language classes in another. This is extremely useful for students, as it decreases their odds of having to walk across campus. Provided enough information, we could do a much better job of this. [distance between rooms/buildings, similarity between classes (category, etc)]
- Negative resource match. A class on finger painting should never, ever go into a classroom with a piano. [Resources Redux]
I’m sure there’s more that I’m missing, and there’s plenty that I have not ironed out. Also, while this information is useful to an algorithm, it would also be useful to a UI for the directors when they are scheduling by hand.
Additionally, two of the above constraints (Geographical clustering and Course distribution part II) could use information about course similarity above and beyond just category, size of class, and grade range. But I’ll revisit that in a long time.
Cheers,
Mike
1: The program is available at http://axiak.scripts.mit.edu/trac/browser/public/projects/genalg/initial, the data is in the ‘y’ file in the above directory. It came from JSON in the views from a locally modified ajaxschedulingmodule.py. The changes have been emailed to this mailing list.