Slashdot Mirror
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!"
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.
Do not confuse duty with what other people expect of you; they are utterly different.Duty is a debt you owe to yourself.
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.
The middle mind speaks!
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
What a fabulous troll your post was.... or how fabulously stupid you are. It's impossible to tell.
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.
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
Well, since this is slashdot, why not open source it, then the "community" can maintain it?
just kiddding.
Do you even lift?
These aren't the 'roids you're looking for.
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.
IP is just rude.
Is there any torture so subl
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.
Network Security: It always comes down to a big guy with a gun.
Schedle For Week of 6/22:
- Abe Aableson
- Bobby Boring
- Zippy Zzyzzix
The truth is, doing the pattern matching isn't going to be the difficult part of implementing this. The difficult part is going to be implementing the correct rules. It's going to be a real bitch figuring out what the rules should be, and then creating documentation and an interface for the rule parameters so that future users will understand what the parameters are, what the (likely) effect of changing the parameters will be.- Mon: 8:00 a.m. - 12:00 a.m.
- Tue: 8:00 a.m. - 12:00 a.m.
- Wed: 8:00 a.m. - 12:00 a.m.
- Thr: 8:00 a.m. - 12:00 a.m.
- Fri: 8:00 a.m. - 3:30 p.m., 4:15 p.m. - 12:00 a.m.
Total Hours: 79.25- Mon: none
- Tue: none
- Wed: none
- Thr: none
- Fri: 3:30 p.m. - 4:15 p.m.
Total Hours: 0.75- Mon: none
- Tue: none
- Wed: none
- Thr: none
- Fri: none
Total Hours: 0It's a good thing he'll be gone after the summer is over, because he won't be around when the users discover that he's missed some important rule. Then, the future users will either have to patch in some extra rules themselves, or abandon the system. As Nelson says, "Ha Ha!"
Anyhow, the correct thing may be to not implement any rules. Keep the human around to actually fill in the blanks, and just use "Mr. Computer" to simplify coordination between the 400 students and the scheduler.
Figure out how the human scheduler does his work now, and automate the truly tedious parts of it (like, copying the schedule over from last week, going through hundreds of slips of paper with time-off requests, totalling up the coverage for all the time slots for all the days, and marking off requested scheduled times). Then, let the human do the heavy lifting, and deal with things like "Suzy doesn't like to work the Bill", and "George wants a few extra hours this week, if he can get them", or "Brenda will only work on Friday evening if no-one else will do it."
But automating the whole thing a few days before you leave town forever is just begging to create a nightmare application that doesn't quite do exactly what they need in a way that anyone there is trained to understand. The fact that you seem concerned about "algorithm maintenance" instead of "rule maintenance" makes me doubly sure that you probably shouldn't build this system.
Well, unless you just want to build the thing, for fun, and you really don't give a damn if they use it. Then, go ahead. Knock yourself out. But don't prentend like you give a poop about maintenance, 'cuz it ain't gonna be maintained.
What a fabulous troll your post was.... or how fabulously stupid you are. It's impossible to tell.
The reference on how to do Army duty rosters properly (i.e. without screwing people or pissing them off) is to follow the directions in AR 220-45 and to fill out DA Form 6.
As another former S1 (and later G1), this was the only way to do it. I saw command investigations where people were repremanded for not following the regs properly (or at all). In this case, the regulation does set out a fair way to rotate duty in a group.
I'm actually using this for scheduling Level 3 support in my development group and there've benn no complaints...