Re: [school-discuss] A plan for automatic schedule building and scheduling

Thanks for your input. I would not describe my method as genetic, I steal what I can from evolution but, not the key parts (randomness and a lot of time). I would describe this more as goal seeking. I don't think the math is as hard as it looks, but that is not my strong suite so who knows. I know that given a master schedule in memory and its requests I can typically schedule it in less than 5 seconds for students. I plan to schedule for staff and rooms first to eliminate bad masters.

Jim

----- Original Message -----

From: David Frankson

To: schoolforge-discuss@schoolforge.net

Sent: Saturday, April 19, 2003 12:09 PM

Subject: Re: [school-discuss] A plan for automatic schedule building and scheduling

> Evolution starts with DNA and makes random changes in the DNA. The resulting organism needs only to pass a simple test to be successful.

I would also recommend against genetic algorithms. I looked into this method a couple years ago. Genetic algorighms tend to get stuck in a local optima. The problem is that there are many solutions to a school schedule, and you have to set your mutation factor too high to explore enough of them. With a high mutation factor and many solutions, genetic algorithms break down into a pattern of random guesses.

> What are the hallmarks of a good master schedule?
...

I would also add:

User defined balancing. Overall student and gender balance is nice, but some schools need race and special ed balancing. We once had a freak occurance where half the students in a general ed class had an IEP. Allow users to enter a weighting factor on each of the balance factors.
Support for advanced term/period/calendar structures. Many schools run trimesters and quarters in the same schedule, or alternate courses every other day except for friday where they double the number of periods and every class meets for a shorter duration. Some districts run year round and have 1/4 of the students on vacation at any given time. There are also period rotations, hippie mod schedules, and 100s of other variations.
Lunch scheduling - this is often a big post scheduling headache. Schedule lunch as a full class, or else flag lunches to sections and balance the # of students.

> Here then is my general plan:

> Generate every non-constraint violating master schedule. The algorithm must allow them to be generated by number so I can tell computer #1 to generate and check the 1st 1000 scheduled and computer #2 the next etc.

Have you ever done the math on that? I would reccommend against brute-forcing the building.

Dave