CODEWITHSUNDEEP
c#algorithmf#
rickythefox
rickythefox

Reputation: 6851

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

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

Upvotes: 1

Views: 2391

Answers (2)

Ramon Snir
Ramon Snir

Reputation: 7560

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']

Upvotes: 2

Teudimundo
Teudimundo

Reputation: 2670

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.

Upvotes: 5

Related Questions