|
>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 |