Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
×
Programming IT Technology

Timetabling Algorithms? 60

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!"
This discussion has been archived. No new comments can be posted.

Timetabling Algorithms?

Comments Filter:
  • The information you need should be easily obtainable from Google [google.com].

    Good luck, it sounds like you'll need it!
  • by pythorlh ( 236755 ) <pythor@@@gmail...com> on Monday June 24, 2002 @03:54PM (#3759122) Journal
    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.


    • 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?

      • Oops... You caught me. When I wrote the post, I was thinking of an optimal solution. Since, as another poster has pointed out, he really only needs a solution, not necessarily optimal, it probably is not NP.

        Incidentally, I was also assuming normal considerations, such as prefering one long tour over several short ones.

  • by Laplace ( 143876 ) on Monday June 24, 2002 @04:01PM (#3759160)
    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.
    • Yeah, I also thought of simplex method and operations research when I first read the question. And, like others have pointed out this must be one boring college if there isn't going to be anyone left to support such a far out concept of scheduling...
    • Greedy add.

      The coward's way out. Often works on real world problems.
      • Greedy add.

        Schedle For Week of 6/22:

        • Abe Aableson
          • 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
        • Bobby Boring
          • Mon: none
          • Tue: none
          • Wed: none
          • Thr: none
          • Fri: 3:30 p.m. - 4:15 p.m.
          Total Hours: 0.75
        • Zippy Zzyzzix
          • Mon: none
          • Tue: none
          • Wed: none
          • Thr: none
          • Fri: none
          Total Hours: 0
        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.

        It'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.

  • 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 [skinewyork.com]

    Note, I haven't used this system (yet) but I enjoy the elegance of the bit-field query.

    Good luck,
    -malakai
  • Sure (Score:5, Funny)

    by You'reAFuckingMoron ( 587707 ) on Monday June 24, 2002 @04:05PM (#3759183)
    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
  • Genetic?? (Score:4, Insightful)

    by Tom7 ( 102298 ) on Monday June 24, 2002 @04:07PM (#3759193) Homepage Journal
    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.
  • by larry bagina ( 561269 ) on Monday June 24, 2002 @04:08PM (#3759206) Journal
    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.
  • by Anonymous Coward
    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.
  • Aha! (Score:4, Insightful)

    by Nyarly ( 104096 ) <nyarly@redfivellc. c o m> on Monday June 24, 2002 @05:02PM (#3759480) Homepage Journal
    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 crulx ( 3223 )
      This looks like a path finding problem to you? You can connect all the nodes (ie timerequests) together in some meaningful way AND you have a function that always returns a weight less than the sum of the path?

      Nice try with the A*. Next time look up what it means.

      In AI, this problem gets called "Constraint Satisfaction." Typically, a logic based programing language gets used, such as Prolog. While he can write the program in C, the nonintuitive way he would have to handle backtracking would seem difficult for other coders to understand. Prolog seems understandable to anyone who knows logic (ie any programmer). Writing backtracking programs in Prolog becomes very easy since Prolog has backtracking as a fundimental component. Let us look at how this program would look in Prolog.

      We have 5 days to fill and 4 workers to do it. Ann can work on Thu. Betty can work Mon-Tue. Joe can work Mon and Fri. Katie can work Tue - Thu.
      available(betty,1).
      available(betty,2).
      availabl e(joe,1).
      available(joe,5).
      available(katie,2).
      available(katie,3).
      available(katie,5).
      availab le(ann,4).

      % Something fits the schedule iff.
      schedule(Mon,Tue,Wed,Thu,Fri) :-
      % Every day has someone available
      available(Mon,1),
      available(Tue,2),
      available(Wed,3),
      available(Thu,4),
      available(Fri,5).

      % ask about who can work when.
      ?- schedule(Mon,Tue,Wed,Thu,Fri).
      Mon = betty
      Tue = betty
      Wed = katie
      Thu = ann
      Fri = joe ;

      Mon = betty
      Tue = katie
      Wed = katie
      Thu = ann
      Fri = joe ;
      That finishes the program! You cannot do that as easily and as simply in almost any other language. You can also continue to ask for alternatives for the schedule (the program lists 9 plans). He can extend this by adding times (obviously) and even preferences for times. The system should feel simple and seems easy to maintain.

      I don't mean to dethrone your CS knowledge, but A* doesn't even apply in this domain. Logic planning can take a great amount of time in other language. He needs the right tools for the job.

      ---
      Crulx

      • Unfortunately the prolog program (as usual) is extremely inefficient. It'll work for a few people, but for hundreds, exhaustive backtracking search is really slow. Matching solves it (at least the problem you describe, which may be different from the "timetabling" problem) in polynomial time.
      • This looks like a path finding problem to you? You can connect all the nodes (ie timerequests) together in some meaningful way AND you have a function that always returns a weight less than the sum of the path?

        Yes, this does look like a path finding problem to me. Every unit of time (your example used days, but more likely we're talking about hour/position combination) needs to be filled. Sort them arbitrarily (honestly, for optimization, you probably want to sort them from fewest options to most.) The goal state is every block being filled. The path between nodes is assigning a worker to a time/position block.

        So, now it's defined as a path searching problem. As far as a heuristic goes, I'm not sure I can provide on that's necessarily h*(), so you may be right: it might not be an A* problem, but I think some h() might be found for a best-first search, and that the choice of that heuristic could lead to a system that is fair to everyone. For instance, an open node that involves assigning work to someone over the ideal number of hours (either in a local preference kind of way, or in a global fairness kind of way) sorts lower than someone under the ideal hours, for instance. Similarly, workers with high availability sort lower than low availablity workers (since they're more valuable in filling time blocks.)

        Incidentally, how did you think Prolog solved this problem? Quite apart from responding to an algorithmic suggestion with a programming language, Prolog has to do something along these lines behind the scenes. And while I'll freely admit that my academic programming was done with Scheme, Lisp and Verilog (for variety), I wouldn't expect much in the performance arena from Prolog, mostly from the complaints of my colleges. As a result, it might not be the best solution for 400+ student employees.

        On the other hand, it sounds like it would be quick to test it out, and if it works, the job's nearly done. If it doesn't it can be abandoned for C or C++ with some nice design.

        Parting shot: whether it's a job for Prolog or a best-first search in C, it's still not a very good candidate for the more difficult to code and understand genetic algorithms, from which you can't even guarantee a result.

    • 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.
      • You know, I posted to a fairly dumb Ask Slashdot, not expecting to have to defend my flippant remarks from all and sundry. Okay, round two: Do you know what NP-hard means?

        Strictly speaking, yes, I do know. I also know that path search is, strictly speaking, NP-complete, and so no worse that exponential. I also tend to use the non-academic's (admittedly) lazy shorthand of NP to mean anything in the NP set of complexity. Certainly, P is a subset of NP, but if I knew the problem was P I would have said P, n'est pas? Secondly, even though I say that the problem is NP doesn't mean that anyone can prove that it isn't P, yet.

        Finally, without more work on the problem, neither of us can definitively say what the time complexity of this particular problem is - while it's almost certainly exponential, the exponent might be quite small, so that 400 staff might be well within the feasible solution range. However, theoretical and imperical limits should probably be put on the use of the system, and every optimization possible applied. I still laud the suggestion of reusing last week's data as a basis for todays.

        • Ok, that's all cool. I'm just reacting to the implicit suggestion that exponential algorithms are a-ok if we just give them enough time. The very nature of exponential algorithms is that extra time doesn't help much.
  • 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.
  • 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.
  • 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.
    • First, the Army way doesn't scale well to 400 people with many shifts, so I doubt if it'll work for this problem.

      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 [army.mil] and to fill out DA Form 6 [army.mil].

      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...

  • 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 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 [ox.ac.uk] 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.)
  • by billcopc ( 196330 )
    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.
  • 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.
  • (Useful?) Resources (Score:2, Informative)

    by Nalfein ( 472106 )
    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 [csubak.edu] I did on why TT is NP-Complete,

    - I spoke about a GA approach [csubak.edu] 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.

  • 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
  • See the Job Scheduling Algorithms [sunysb.edu] from The Stony Brook Algorithm Repository [sunysb.edu], an excert of which follows:

    "Devising a proper schedule to satisfy a set of constraints is fundamental to many applications. A critical aspect of any parallel processing system is the algorithm mapping tasks to processors. Poor scheduling can leave most of the expensive machine sitting idle while one bottleneck task is performed. Assigning people to jobs, meetings to rooms, or courses to final exam periods are all different examples of scheduling problems.

    "Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. For this reason, several other catalog problems have a direct application to various kinds of scheduling.

    "We focus on precedence-constrained scheduling problems for directed acyclic graphs. These problems are often called PERT/CPM, for Program Evaluation and Review Technique/Critical Path Method. Suppose you have broken a big job into a large number of smaller tasks. For each task you know how long it should take (or perhaps an upper bound on how long it might take). Further, for each pair of tasks you know whether it is essential that one task be performed before another. The fewer constraints we have to enforce, the better our schedule can be. These constraints must define a directed acyclic graph, acyclic because a cycle in the precedence constraints represents a Catch-22 situation that can never be resolved.

    "The best book available for this problem is Intelligent Scheduling [amazon.com] by Mark Fox."

    Click here [sunysb.edu] for the algorithms.

    Disclaimer: I haven't used them.

If you think nobody cares if you're alive, try missing a couple of car payments. -- Earl Wilson

Working...