[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

RE: [school-discuss] Master schedule building and scheduling



>I use a meta-heuristic combinatorial optimization algorithm that integrates concepts of tabo search.  The heart of the algorithm is a recursive function to traverse the solution space. – David Frankson. 

Whew! That’s a lot of big words for one sentence or even two. Especially right after reading about a master schedule builder that uses a genetics / evolutionary design.

As I read this forum there are a lot of non-programmers. A lot of people who work in schools and are interested in open software solutions but don’t necessarily write them. Since both of these solutions have to do with my promised next post, let me start with them.

First for the non-programmers in the group, let me attempt to explain “meta-heuristic combinatorial optimization algorithm that integrates concepts of tabo search”. Bored already go to “The Bottom line” Heuristic implies rules, meta-heuristic implies various levels of rules. Computer programs themselves are lists of instructions and rules for the computer to follow, so most of them are Heuristic. Beyond that Heuristic implies some common sense rules that increase your chances of solving the problem.

A simple example:

2x = 10.

One way we could attempt to solve this problem (one used by many students, alas) is to guess. Start picking numbers and test them. Since we know the answer is a real number of some sort and there are an infinite number of real numbers and only one is the right answer, this seems a poor strategy. A much better one would be to just divide both sides of the equation by 2 (the golden rule).

Like wise in a scheduling problem with millions of possible combinations only some of them are winners. David is trying to develop rules (heuristics) that allow him to find the answer sooner; he doesn't want to test every possible combination. In my case, instead a using a tree structure I make a pyramid with the most likely combinations at the top and then proceed to do a systematic test of these possibilities.  The end result, with the current version of my scheduler I have not seen runs over 5 minutes, and typical runs are under 1 minute (for 1200 students on 1 GHz P4). To the end user the algorithm used is not important only the bottom line.

These rules should also let us identify when no solution is possible as soon as possible. For example, a student has mandatory requests that require 40 periods to satisfy, while the school runs a 5 day by 7 period schedules. There are only 35 periods available and 40 are needed, why even try? Or a student needs AP English that meets Monday through Friday 1st period and is a singleton (1 section) and also needs the singleton AP History with the same meeting time. As soon as this irreconcilable conflict is hit, you might as well save further effort.

As for the “tabo” search, I think David meant “Tabu search” and past that I not familiar with how it works or even what it does.

With regard to “recursive functions”. Recursion (a function or method calling itself) quite frequently produces elegant solutions to problems. Check out recursive versions of quick sort on the Internet. They are however not with out cost. There typically is much more overhead in executing them.

The Bottom Line.

In any event the bottom line is this. Every strategy has a cost associated with it. There is a computer cost and a human cost. The computer cost is measured in resources required (Cost of equipment, CPU cycles) and the human cost is the cost of the person’s time, which goes up (in theory) with the value of their knowledge.

Since the cost of a modern PC is low compared with the cost of an employee's time, we can pretty much measure the cost in time (the person's time, not the computer's). Say my scheduler makes a run in 30 seconds, while another makes a run in 2 minutes. What is the difference? Nothing, because there is no significant cost in human time. However if the difference was 30 seconds to 2 hours, then there is a significant impact. Not only does it take a significant slice of time from the person but in starts to change the way they work. Instead of making one small change (like a science experiment) and rerunning, they need to make more complex changes, because of the lack of time. The outcome of more complex changes is harder to predict and understand and the level of skill needed to make them successfully increases. A hundred runs at 30 seconds (< 1 hour) is trivial, a hundred at 2 hours (200 hours) is not.

On the other hand if a computer could build and schedule an acceptable (politically and every other way) schedule with no human intervention after the start of the run, it would not matter if it took 2 weeks or a month. Its cost in human time is zero.

What schools should look for in scheduling (not Master Schedule building) is the following:

·         Does the scheduler find the “best” (whatever your definition of that is) schedule for a student.

·         How fast does it do it? Does this fit your work flow?

·         How much human intervention (setup, conflict resolution, playing god) is required?

If you want master schedule building you probably want something that helps you reduce your cost (time) rather than something that attempts to do it all. This is hopefully a temporary situation.

Next: My proposed framework for the Holy Grail.

 

 

James P. Smyth

Technology Coordinator

Northeast Metropolitan School District