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!"
The information you need should be easily obtainable from Google.
Good luck, it sounds like you'll need it!
... you would know that the problem is NP-complete. meaning it's better to do it by hand.
What university is this again? You must have gotten your Degree in AI and CS somewhere else?
Why not have some faith in people and do it right the first time? Besides, given you already "know" the answer what's the point of asking slashdot? You just trolling for some stupid cs jokes?
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'm not just making this 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 and of the standard books 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, Bobby.
What a fabulous troll your post was.... or how fabulously stupid you are. It's impossible to tell.
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.
I thought bipartite matching with integral weights (probably no weights in this case, actually) was polynomial time. Am I missing something that makes this NP-complete, or did you just make that up?
You have a degree in AI. Gimme a fucking break.
You surely recognize this as a constraint satisfaction problem then. Set up the variables, their domains and the set of constraints and use a standard package to solve it (or give a reasonably good approximation). This is your initial solution, and then you incrementally resolve as the constaints change. How much do you expect people's availability to change? Are the constaints going to be drastically different?
Do you need to dump a nice explanation of why your code produces the resulting solution? Jesus christ. What kinda kids do people hire to do these jobs. And this isn't even that difficult.
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
AI nothing!! Do your business trends change dynamically? Do your employees come and go every 15 minutes? Are you going to tie this application to your student registration system (FERPA ALERT -- FERPA ALERT)? Yeeeesh, your degree in CS and AI is making this problem a lot more difficult than what it needs to be. Obviously the human scheduler knew when and where he needed people because of repeating and predictable business trends.
Your S.U. manager should know how many employees he needs where and when he needs them. Simply break the days up into fixed shifts for each day (i.e. 2 people from 8am-10am, 4 people from 10am-2pm, 2 people from 2pm-4pm, etc.) Let the students "bid" on shifts (i.e. first come first serve) or pick the shifts based on a lottery. For shifts that aren't popular, use the hammer of employment (i.e. do you like your 10am-2pm shift then you will work the 6pm-10pm shift) Since your student's class schedule shouldn't change for at least 16 weeks, once you have 1 week of scheduling done copy it to the next 15 weeks. If a student employee needs to change shifts he needs to find his own replacement.
If you really got your pecker hard for a computer program try a freaking random number generator and drop students into shifts and then allow a human to correct what few openings are left. You can call it the "5th order polynomial with a 32 bit ROR" AI scheduling algorithm. (Hey, the Liberal Arts students will believe it.)
You aren't the first person that needs to schedule 400+ employees on a rotating schedule. This is how the real world does it buddy!!!
That AI degree isn't going to do anything but impress your ignorant friends at parties. Now go play in the street.
Are you this person:
http://slashdot.org/~phil%20john
I just want to know so I can add you to my foe list you freaking idiot.
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--
2 lists. one list of shifts, one list of employees. check if first employee can work first shift. match. iterate. repeat when at end of employee list.
Watching that horrible spielberg movie does not mean you have a degree.
Having done work as an S1 (Personnel) and having to figure out guard schedules the Army Solution:
Draw a grid. List all the people down the left in Alphabetical order. In the first cell of the grid number 1 all the way down. Highest person on the list with the lowest number gets the detail. Put an X in this box. Add one to everyone elses value and carry over to the next column. Repeat ad-nauseum.
Glad I don't do that anymore.
Open Source Identity Management: FreeIPA.org
Funny, but that's probably not the explanation. Sometimes the Slashdot software moves comments around. Maybe the one that is first now was second before.
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
I was thinking of writing such a piece of code for my company. I haven't got the time yet. I think it can be solved by using Annealing, which is one of the strongest optimisation methods for multivariate functions (see here for example). Basically you simulate a gas of students which under hot temperature jump from shift to shift, when cooling down the probability for a change is simulated with a bolzmann factor (which includes temperature). By modelling the energy (or money) of persons in a shift this should be a flexible way of optimisation. (shift overlaps with lectures, for example, would raise the energy so when minimizing energy, they should disappear.)
Now most of you idiots have replied saying how to implement a solution, but an answer to the question in hand is:
Who gives a fuck about the application once your gone! If they are desperate they will pay you the "cap" to come back and fix it ;)
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
Heck, just get your timetabling person to post the new timetables, student lists, etc onto slashdot, throw in some microsoft banter, then let the /.'s squabble their way to a solution. Zero development, easy to use web interface, and only a few comments directed back at you telling you that.. "If you know how to do it, why the hell are you asking us" and "you can dress it up all you like, but we aren't doing your homework for you". Perfect.
Training monkeys for world domination since 1439
You start scheduling us randomly and we'll *all* being working elsewhere so fast that you won't even have time to ask "why the hell is the boss making *me* come in and work" (& all alone, too, tee hee).Its only an option if you can constript workers. Prisions, military, and other forms of involuntary servitude.
um, these are kids who work four to six hours a week in a "study hall" as computer lab assistants or cafeteria helpers as part of their financial aid. Most of them don't show up more than half the time.
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
I think it's pretty funny how there is like ten posts that say, "GA? What are you thinking? This is obviously a job for _______. " And the blank changes each time..
There are many ways to solve this. Use a GA if that's what you are most comfortable with. Just make it well-documented and replacable, so if your successor wants to replace it with a constraint optimization solver, she can.
But really, I suspect you are getting caught up in the unimportant details. For a scheduling system like this, your users aren't going to be sitting around trying to make tricky schedules to break your AI. This isn't a programming problem.
Solve these problems, and your users will be happy:
- people want their schedules to be consistant.
- They want to be able to trade shifts easily.
- They want to know in advance when they are required to work.
- They want scheduling conflicts to be resolved fairly.
- They don't want to feel stupid when using the software
- They want a clear view of their schedule and their co-worker's schedule
You'll find that people's constraints are not so easy to encode. Things like "I'd like to work when my girlfriend is working", "I want to work nights", and "our entire shift decided to go to burning man together at the last minute".
A clear, flexible interface will serve your users better than 3 AI degrees. This is an interface problem disguised as an AI problem. If I were in charge of this, I would not include a solver at all.
So many of the people over here seem to think that this is a trivial problem. I beg to differ...
I ran into a similar, if somewhat simpler problem recently. 13 employees. 6 shifts per day. Various assorted constraints. In particular, there were frequent vacation constraints (on the order of 1-2 weeks per person per month).
Ignoring these constraints, there are 720 possible ways to assign 6 people to 6 different shifts. There are 1,716 possible ways to choose 6 people from a set of 13. Given 31 days in a month, that's 7*10^188 possible schedules forming the search space.
The problem domain is NP complete. To examine every possible solution, we are looking at a computational time beyond the eventual heat-death of the universe.
If we don't need an optimal solution, but merely a solution, the problem becomes much more tractable. Until we consider the constraints.
The constraints may very well dictate that no valid solution exists. The catch is proving that no valid solution exists, for the non-trivial case, without examining every possible solution. I have not yet investigated how feasible this may be. It is certainly very domain, or rather constraint, specific.
GA's and other evolutionary programming techniques won't guarantee that you will ever find a valid solution, let alone the running time.
On the other hand, exploring the space from the most constrained timepoint outwards to the next most constrained timepoint, and so forth, backtracking as necessary, may have the unfortunate effect of exploring the entire search space. Properly coded, an interactive UI could permit the user to pause the work and "assist" by adding additional constraints, thereby limiting the search space.
On the other hand, provided you don't get into an over-constrained scenario, you can get awfully far with a simple greedy algorithm that attempts to load-balance.
Then there are the more mundane aspects: The UI itself. Data storage and retrieval. Adjusting the schedule to changing constraints (replanning). Printing and publishing the results. Providing the status of the search currently in progress.
They will occupy a fair bit of coding time as well.
I suggest you design the system. Figure out all the data entry, output, and UI bits. Don't implement. Just plan it all out. Then estimate how much time each part will take to write, code, and test. Especially test. Add up all the times, and see whether it's even possible to complete this software before you leave...
... 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
Click here for the algorithms.
Disclaimer: I haven't used them.
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....