Generating schedules - need good algorithm

Yesterday while trying to fall asleep I started thinking about how to solve the problem below and realized I couldn't come开发者_StackOverflow up with a good algorithm. This is not a school assignment even if it might look like one, I just want to find an answer. :)

Basically let's imagine a work schedule for employees in a store. The program should generate schedule suggestions based on a set of requirements.

The requirements are:

• Only one employee works any given week.
• An employee can't work two weeks in a row.
• There should be a way to prevent an employee from getting scheduled to work a certain week (vacation).
• The distribution should be as even as possible, i.e. if we have employees A, B and C they should get approximately the same ammount of weeks off and those weeks should be as evenly distributed as possible.

What would be the best way to attack this problem? Perhaps functional programming is better for solving this?

EDIT: Now I know this type of problems is called "resource constrained scheduling". Is a bit hard to goole for this as "scheduling" often refers to things like scheduled tasks or threading. For the people who still think I'm asking for homework solutions (despite me explicitly claiming otherwise above), you can check out my previous questions, I think they clearly indicate I'm not a student...

The first two points are constraints for the problem. The third point indicates a way to sort the candidate solutions, if you formalize it you get an optimization problem. In fact you are trying to minimize the differences on the work distributions.

Note that because of the constraints the problem might have no acceptable solution.

It is a combinatorial optimization problem, you can solve it exactly with Integer Linear Programming methods, or approximately with Stochastic Local Search methods (they are also known as metaheuristics or many other names) such as genetic algorithms, simulated annealing, tabu search, iterated local search, ant colony optimization and so on.

This specific class of problems are known as Job Scheduling and there is a lot of literature about it with many variants.

If this is not a homework I think this should be enough for satisfying your curiosity, if it is I think I told you what you can look at.

Even though it seems as if this is homework, I prefer to believe you.

Here is what I've come up with:

let rec assignWork n upTo last workers =
    if n <= upTo then
        let checkNameIsEqualToLast =
            match last with
            | Some n -> ((=) n)
            | _ -> fun _ -> false
        let (name, _, _) as worker =
            workers
            |> List.filter (not << fun (name, _, v) -> checkNameIsEqualToLast name || List.exists ((=) n) v)
            |> List.sortBy (fun (_, w, _) -> w)
            |> List.head
        workers
        |> List.map (function
            | n, w, v when n = name -> n, w + 1, v
            | w -> w)
        |> assignWork (n + 1) upTo (Some name)
        |> fun t -> name::t
    else []

For example:

let workers =
    List.zip
        [ 'A' .. 'E' ]
        [
            []
            [ 2 .. 4 ]
            [ 3 .. 5 ]
            [ 1 .. 10000 ]
            [ 3 ]
        ]
    |> List.map (fun (c, v) -> c, 0, v)

assignWork 1 16 None workers

The output is (seems reasonable to me):

val it : char list =
  ['A'; 'C'; 'A'; 'E'; 'B'; 'C'; 'B'; 'E'; 'A'; 'B'; 'C'; 'E'; 'A'; 'B'; 'C'; 'E']