The Mathematics of Scheduling Classes

After a chat with my colleague from the math department who does the scheduling for the entire MS and HS of our school, I have become very intrigued by the mathematics of scheduling. His background is in Discrete Mathematics, and the professor under whom he had studied way back when has recently been awarded the equivalent of the Nobel Prize in mathematics. So, this colleague is a semi-expert in tackling problems such as this. He took over the task of programming for our school's MS and HS schedules a few years back because of his personal interest in the complexities involved. He told me it's like a big Sudoku puzzle that you don't know whether there is a solution for. Even though he uses software to help, much of it is too complex for the software and he has to manually do a lot of it. Often, when the software gets "stuck" from all the rules that have been inputted, he has to go back to the drawing board, try asking departments to change their teaching assignments on particular teachers, in order to enter in new rules, in new orders, in hopes of getting the software "un-stuck" and to progress further. Tough task! And, as it turns out, it is most mathematical.

Here are some basic things that make scheduling for our MS/HS school tricky and difficult:

• We share facilities (such as art pavillion, cafeteria, and gym) with the elementary school. So, all of those classes are blocked out during certain days and certain times. 
• We are an IB school, which means that kids get to choose in Grade 11 and Grade 12 (and to a lesser extent, in Grades 9 and 10 as well) any combination of high-level and standard-level classes from our offerings based on their interest. Because we truly believe in kid's choice, we don't limit the types of combinations they can have, but it also means that we need to weave together the classes to allow for a variety of combinations.
• Imagine kid 1: English-High, Math-Standard, Chemistry-Standard, History-High, Economics-High, Music-Standard.
• Imagine kid 2: English-High, Math-High, Biology-High, History-Standard, Economics-Standard, Spanish-Standard.
• Imagine kid 3: English-Standard, Math-Standard, Physics-High, Economics-High, Music-High, Art-Standard.
• All of these combinations of schedules (and all other possible combinations) need to be supported, which comes into conflict with our next constraint....
• Because we are a relatively small school (only about 60 kids per grade), that limits the number of classes that can be offered. So, for example, there is only 1 section of High-level mathematics in Grade 11. All 10 or so kids who are interested in taking that class will need to be able to fit that one class into their schedules. We cannot afford to open up an additional section of High-level math in Grade 11, when there are only about 10 kids total who are capable of taking math at that level. Same with kids in High-level classes of most other subjects, probably.
• FYI: High-level IB math is really intense. It goes into differential equations and stuff, well beyond Calculus AB of the A.P. system.
• In the IB, each kid is required to choose 3 High-level classes to take. Again, this means we need to have a master schedule that supports the variety of possible combinations of High-level classes that kids might wish for. A TOTAL MATH PROBLEM!!!!
• Because we want to allow the flexibility of students changing their choices of high- and standard- level classes during the year (typically in Grade 11), we need to piece together department schedules in a way that allows a student to change options without too many problems during the year. Hopefully as well, this means that they will incur minimal changes in teachers of their other classes.

As a result, one of the consequences of these cross-constraints is that all Grade 11 math classes, regardless of levels, must be taught at the same time. Same with all Grade 12 math classes. (It's not obvious perhaps why that is, but it's a natural fallout of reasons #2 through #4 above.) Another indirect consequence is that all teachers must teach a lot of different "preps", so it is common for a teacher like me to teach 5 different grades during the week, because at the same time that I am teaching, my colleagues are teaching other sections of the same age group.

So very interesting, eh? Have you worked with scheduling before? Can you chime in to say something about the mathematical nature of this problem? Notice that we're not even talking about physical space constraints above. This is mathematical problem-solving at its richest!