Генерация расписаний - нужен хороший алгоритм

Question

Вчера, пытаясь заснуть, я начал думать о том, как решить проблему ниже, и понял, что не могу придумать хороший алгоритм. Это не школьное задание, даже если оно может выглядеть так, я просто хочу найти ответ. :)

По существу давайте представим график работы сотрудников в магазине. Программа должна генерировать предложения по расписанию на основе набора требований.

Требования:

• В каждую неделю работает только один сотрудник.
• Сотрудник не может работать две недели подряд.
• Должен быть способ предотвратить получение сотрудником намечена работа на определенную неделю (отпуск).
• Распределение должно быть как можно более равномерным, т.е. если мы имеем сотрудникам A, B и C они должны получить примерно одинаковую сумму недель и эти недели должны быть распределены возможно.

Как лучше всего решить эту проблему? Возможно, функциональное программирование лучше для решения этой проблемы?

РЕДАКТИРОВАТЬ : Теперь я знаю, что этот тип проблем называется «планирование с ограниченными ресурсами». Это немного сложно поглотить, поскольку «планирование» часто относится к таким вещам, как запланированные задачи или многопоточность. Для людей, которые все еще думают, что я спрашиваю о решениях для домашней работы (несмотря на то, что я явно заявляю об обратном выше), вы можете проверить мои предыдущие вопросы, я думаю, они ясно указывают, что я не студент ...

Answer 1

Первые две точки являются ограничениями для задачи.Третий пункт указывает способ сортировки возможных решений, если вы формализуете его, вы получите проблему оптимизации.На самом деле вы пытаетесь свести к минимуму различия в рабочих распределениях.

Обратите внимание, что из-за ограничений проблема может не иметь приемлемого решения.

Это проблема комбинаторной оптимизации, которую вы можете решитьэто точно с помощью методов целочисленного линейного программирования или приблизительно с помощью методов стохастического локального поиска (они также известны как метаэвристика или многие другие имена), таких как генетические алгоритмы, имитационный отжиг, поиск по табу, повторный локальный поиск, оптимизация колоний муравьев и т.1005 *

Этот специфический класс проблем известен как планирование работы, и есть много литературы об этом с большим количеством вариантов.

Если это не домашняя работа, я думаю, этого должно быть достаточно для удовлетворения вашего любопытства, если это так, я думаю, что я сказал вам, что вы можете посмотреть.

Answer 2

Даже если кажется, что это домашнее задание, я предпочитаю верить вам.

Вот что я придумал:

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

Например:

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

Вывод (мне кажется разумным):

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