Slashdot Mirror

← Back to Stories (view on slashdot.org)

Timetabling Algorithms?

Posted by Cliff on from the code-that's-maintanable-by-someone-else dept.

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!"

3 of 60 comments (clear)

  1. You're a hammer, and everything is a nail by Laplace · · Score: 4, Informative

    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!
  2. Design Tip: SQL Based Scheduling Systems by malakai · · Score: 2, Informative

    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
  3. (Useful?) Resources by Nalfein · · Score: 2, Informative

    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