Effective Timetabling Algorithm

Question

I've got a job that I've been asked to do which involves writing a program to determine where various people are to work on a given day.

For example the input may be:
4-6pm, Site A
1-2pm, Site B
9-11am & 2-4pm Site A

Essentially there can be many sites and people can work during multiple blocks. I get the feeling that this kind of problem has been solved long ago so rather than reinventing the wheel I was hoping somebody could point me in the direction of an elegant solution.

Edit: Reading similar questions I get the feeling that the problem may be NP complete. I don't need the most efficient solution only something that works and is reasonably ok.

Edit 2: To clarify, the output should be a timetable with people allocated such that gaps (instances where nobody is working) is as small as possible.

Answer 1

Looks like you are trying to solve a problem for which there are quite specialized software applications. If your problem is small enough, you could try to do a brute force approach like this:

• Determine the granularity of your problem. E.g. if this is for a school time table, your granularity can be 1 hour.
• Make instances for every time slot divided by the granularity. So for Site B there will be one instance (1-2pm), for size A there will be many instances (4-5pm, 5-6pm, 9-10am, 10-11am, ...).
• Make instances for all the persons you want to assign
• Then iteratively assign a person to a free time slot taking all of your constraints into account (like holiday, lunch break, only being able to do one thing at a time, maximum number of people per site, ...) until:
  • you have a valid solution (fine, print it out and exit the application)
  • you enter a situation where you still need to place persons but there is no valid time slot anymore. Then backtrack (undo the last action and try to find an alternative for it).

If your problem is not too big you could find a solution in reasonable time.

However, if the problem starts to get big, look for more specialized software. Things to look for are "constraint based optimization" and "constraint programming".

E.g. the ECLIPSe tool is an open-source constraint programming environment. You can find some examples on http://eclipseclp.org/examples/index.html. One nice example you can find there is the SEND+MORE=MONEY problem. In this problem you have the following equation:

    S E N D
+   M O R E
-----------
= M O N E Y

Replace every letter by a digit so that the sum is correct. This also illustrates that although you can solve this brute-force, there are more intelligent ways to solve this (see http://eclipseclp.org/examples/sendmore.pl.txt).