[school-discuss] Master schedule building and scheduling

Hi, I have noticed a couple of posts on master schedule or time table building and I thought that I would toss my two cents worth in. First I little background. I have been involved with scheduling since 1979, when I wrote my first scheduling program. It ran on a PDP 11/70 and scheduled a school of 1200 students in just under 10 minutes. When I first started I wanted a program that would build and schedule a complete master schedule, but when I investigated this it turned out to be too large a problem. I once worked out the math and figured it would take a PDP 11 (about as good as there was in schools at the time) about 2,000 years to do the job, too late for the summer of 1979!

I talked to many people in the scheduling business (mostly service centers at that time) and found out it took between 6 hours (on a main frame) to 2 days on a mini-computer for a run. I knew this was unacceptable so I started looking at what things machines could do fast and built the scheduler around them. I also look at various ways to restrict the problem to a smaller domain. Over time I was quite successful at developing a fast algorithm. The current object oriented version does the same job using a standard SQL database on 1.0 GHz P4 in well less than 30 second. I have had runs as low as 3-5 seconds.

With these advances in computers and programming technology it occurred to me that it would now be possible to tackle the 2,000 year problem. So if one wished to do this what would be the problems encountered and what would be a general strategy?

There are three major concerns with a master schedule.

The Math. There are lots of combinations here. It is a non-trival problem, at least to me. On the bright side at least it is a problem with a solution.
The Money. The master schedule determines how expensive your school is to run. Most of the money is, after all, spent to support this document. Every course, every section requires a teacher (and their salary) to teach it and a space to meet in. These are the two most expensive things in a school the staff salaries and the building. Then there are materials needed and the more teachers the more administrators (not really sure about this, administrators some times seem to come from nowhere).
The Politics. It would be much easier and more straight forward if this could be considered just a math problem, but it is not. There is always the department head that will not teach the last period, or just before lunch or the first period etc. There is the teacher who has taught in the same room for 417 years. There are the teachers that don’t get along (I know, not at your school) and should be separated. There is the comfort level with the current master schedule (at least among those that have a good deal) etc. In fact the current master schedule probably reflects the political concerns better than it does the educational goals and financial constraints. No matter what rules are set down, they will always be violated in some cases. We don’t want teachers to go from room to room, but inevitably some have to. Who makes this decision, the computer or the principal? How about the teacher that has to cover a subject he/she is not qualified to teach? Who makes that decision?

So what is our goal here? Obviously computerized master schedule building sounds good. After all the potential just to save money (see major concern 1) is attractive. And some constraints are not bad they reduce the size of the problem (if they are not near impossible to code). For example most master schedules run horizontally, if English meets 5 times a week we would probably want them on different days (Monday – Friday) not all Monday. On the other hand I’ve been in situations where English did meet twice on one day. If we could codify all the rules including political constraints would we have not done so much work that the master schedule would be pre-determined or possibly just the current master schedule? How much political capital would the administration invest in a new master schedule? Is the door to your office fire-proof just incase the teachers/administrators/everyone doesn’t like the new master schedule?

In my next post on this subject I will assume that the answers to the above are positive and discuss the general frame work for such a program.