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!
I've written SQL based scheduling systems a number of different ways. I think all my previous designs had major annoyances in them compared to this:
SQL Based Scheduling Systems
Note, I haven't used this system (yet) but I enjoy the elegance of the bit-field query.
Good luck,
-malakai
-Malakai
A Dragon Lives in my Garage
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.
Greedy add.
The coward's way out. Often works on real world problems.
Network Security: It always comes down to a big guy with a gun.
Uh, I know I just took algorithms in my CS course, but we went over this type of problem in our greedy algorithm section. Earliest finish time first scheduling.
"shedule the class E that has the earliest finish time then recurse on the classes that start after E ends"
seems like this, applied and limited by the available personel, and per position could work pretty easily, and be easy to maintain.
--onyx--
There are a number of papers on the application of GAs to the optimization of the timetabling problem, but all of the require an initial solution. This is a basic premise of GA - start with a working solution, modify it randomly, and test it, until you find something that works better.
The initial solution comes from solving a complex system of constraints. Typically a collage will require the modelling of Students, Teachers, Classes and Venues. A group of Students enrolled for a particular Class, plus the Teacher teaching the Class, must not have clashes with other Classes, and the Class must not have a Venue clash.
Venues are assigned to a class based on teacher locality and class size. Students are assigned to a class based on registration. Teachers are assigned to classes by a department.
A useful heuristic for getting the initial solution is to allocate class time in "streams": identify courses that cannot be taken simultaneously, and schedule them at the same time. e.g. CS 1, CS 2 and CS 3. If the same Teacher is required for different subjects in the stream, you have to take out all but one such subject.
You may also have to consider oversize classes - sometimes a class of (say) 900 students must be split into 2 venues; and sometimes one teacher must teach all 900, so instead of venues, there is a split into two classes. This is rather more complex than it sounds: some students will only be able to attend one of the classes, others could attend either. Those that can attend either need to be assigned to a particular class, to prevent the venue from being overfilled and "starving out" those who need to attend that class, because they have a clash with the other.
On the other hand, if it takes a single staff member "at least a day" to schedule all of this, then you are probably looking for a less complex solution. I was asked by a high school (1000 pupils, approx. 40 staff) to assist them by writing an timetabling program; they took up to a week between three planners to schedule their classes.
i-name =twylite [http://public.xdi.org/=twylite], see idcommons.net
Screw the data system. Have people register directly for the timeslots they want, and stop accepting entries when said timeslot is fully staffed. First come, first shift. Nothing sucks more than variable shift work.
-Billco, Fnarg.com
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...
Most people who have spoken up so far seem right:
GAs can be used to find sub-optimal or optimal (given enough time) solutions for NP-complete problems, Timetable (TT) being one of them.
However, I think the core benefits of using such a heuristic, in this case, might be:
1. At any point in time, you can tell the GA to stop, and you can get a feasible (but probably sub-optimal) soltuion from it,
2. GAs are, in some small ways, parallelizable.
Of couse, you're probably not looking for a whiz-bang super-duper fast utility, so (2) probably isn't useful.
Perhaps you can find some use of these:
- A presentation I did on why TT is NP-Complete,
- I spoke about a GA approach for solving the TT.
Note that the time spent by a GA in finding an optimal solution is not guaranteed to be any better than the speed of an approximation algorithm, nor even the speed of the naive approach, when solving TT (or any other NP-complete problem).
The GA approach mentioned above had been used successfully in practice, though.
-- Brian
... well, in algorithms, anyways.
This is a variant of the napsack problems. It's a little more complicated, but not much. You have a collection of objects (employee hours) and a collection of containers (hours of time that need to be filled by some employee). You also have various restrictions (certain employees can't work at certain times, or equivelently certain employees can only work at certain times). Just start grabbing employee-hours at random, and shoving them in. If you reach an impasse (no employee can work a given hour) you backtrack to an earlier decision and pick differently.
There are degenerate situations where, although a solution exists, this algorithm will take an excessive amount of time to find the solution. But I'd bet you find them in this situation.
Brian
NP includes P, and therefore says nothing about how hard an algorithm is. What you meant is NP-hard.
Do you know what NP-hard means?
It means there's no known polynomial-time algorithm, which means the best you can do is probably exponential time. It means 24 hours is barely any more helpful than 24 seconds. A factor of 3600 extra time with an NP-hard might allow you to schedule 40 staff instead of 30, but you'd probably need longer than the lifetime of the universe to reach 100, let alone 400.
People don't just avoid NP-hard problems just to be picky. They avoid them because they simply don't work for large problem sizes in any reasonable amount of time.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....