Timetabling Algorithms?

Phil John queries: "I'm developing a system for a University Student Union which employs 400+ student staff. Allocating shifts up till now has been a manual task keeping 1 member of staff busy for at least a day. I've been asked to implement a Web/SQL based system to get student availability (which changes each week), get shifts required and automatically allocate shifts. Now, here's the problem: how do I handle the timetabling bit? Most solutions require genetic algorithms and while I can understand and implement them (having a degree in AI and CS) I'm not going to be around after the summer and this creates problems for people maintaining my code. Cheers for any help you guys (and gals) can give me!"

Comments

Don't Start From Scratch...

[pythorlh]

Unless your student availability varies wildly day to day.

Have you database detect collisions between the current schedule and the new student availabilities. Then try to juggle only the students with a collision. You won't always be able to do it, so a backup layer would juggle some of the other students, preferably randomly chosen (ie the most-available students don't always get shafted), until it works. This reduces the processing load of an otherwise NP-complete problem, and actually encourages the more stable students with a more stable schedule.

One drawback, initialy schedule needs to be entered by hand, but only once.

You're a hammer, and everything is a nail

[Laplace]

Genetic algorithms? Branch out, man.

Stuff like this has been around forever. Try looking up keywords like "optimization," "linear programming," "constrained optimization," and "operations research."

There are tons of packages out there to help you out. Good luck.

Sure

[You'reAFuckingMoron]

Dear Slashdot,

I have a degree in "AI". Really. I have no reason to just make that up.

Anyhow, it turns out that I am unable to implement standard AI algorithms. I have no idea where the standard AI algorithm repositories are on the net, and I am unaware of any of the standard textbooks on the subjet. In fact, I am unable to do even the most basic library research on my own.

Should I sue the school that gave me this fucked up, worthless degree? Or are my shortcomings entirely my own fault?

Sincerely,
Phil (The Turnip Head) John

Re:Sure

[Rick the Red]

You missed the subtile difference the moderators found all-important. His first, "redundant," post was signed:
"Sincerely, Bobby."

His second, "funny," post was signed:
"Sincerely,
Phil (The Turnip Head) John"

See the difference? The second is much funnier, making the first post clearly redundant.

Genetic??

[Tom7]

Genetic algorithms? Really? It sounds to me like a straight up bipartite matching problem, and though there are doubtlessly genetic algorithms for tackling matching, there are also plenty of simple algorithms too (like using max flow ... polynomial time!). It sounds like you don't have weights and you probably don't even require the optimum solution, so what's the big deal? Just implement it as a nice abstract package, and hopefully nobody will need to "maintain" your working matching library.

Aha!

[Nyarly]

I've figured out what Mr. John's problem really is. From the other replies, it seems that other /.ers had the same question I did, which is "Why does he think that timetable resolution is a GA problem?" and then it struck me: he has a degree in AI, and so has probably read a lot about genetic algorithms.

IIRC, most GA papers use either elevator control or personnel scheduling as example problems, much like many OO texts use bookstores. Therefore, Mr. John has come to believe that personnel scheduling is best solved by GA.

At least, so I hypothesize. It seems like a fairly straightforward A* search problem to me, although the suggestion of working from previous schedules and just fixing what needs fixing as opposed to starting from scratch is a good suggestion.

Additionally, so what if it is NP? Frankly, if it took an employee a day to do, the machine should have at least 24 hours to work on the data to come to a solution, which is intuitively more than reasonable. Sure, initially fan out is large, but the more restrictions students give the more fan out diminishes as you decend the solution tree. Honestly, you've got a pretty interesting heuristic to write, IMO.

By hand?

[ccoakley]

Ehhh... NP-complete hardly means something is better done by hand. However, you are right. Most scheduling problems are NP-complete (pp. 238-242 in Garey and Johnson).

Try a greedy add or even loading heuristic. You will find that both are extremely easy to implement and maintain, and often do a "good enough" job for most manual scheduling problems.

Here is a heuristic I wrote for scheduling Navy Instructor Pilots: Get a list of all of the holes in the schedule. Find all candidates for all holes. Find which hole has the fewest candidates (greedy). Find out who has gone the longest without serving this duty (simple even loading). It works better than 97% of the time.

Genetic algorithms are a pain in the --- to write and maintain (and I will be teaching a class on them in the Fall at UCSB, so there's a proper endorsement). Talk to the person who currently writes the schedule and see how they do it. The logic in such an expert system is likely to do a decent job. It's not like you are scheduling for a manufacturing plant where a 2% improvement in scheduling can mean 2% improvement in revenues.