Назначение рабочих мест работникам

Question

Есть N водопроводчиков и M рабочих мест для них, где M> N в целом.

Если N> М, тогда пришло время увольнений! :)

Свойства работы:

1. Каждая работа должна быть выполнена в определенном временном окне, которое может изменяться за работу.
2. Расположение каждого задания зависит от работы.
3. Некоторые работы требуют особого мастерства. Навыки, необходимые для выполнения задания, могут варьироваться в зависимости от заданий
4. Некоторые задания имеют более высокий приоритет, чем другие. «Награда» за некоторые рабочие места выше, чем у других.

Свойства водопроводчика:

1. сантехников должны ездить с одной работы на другую, которая занимает много времени. Скажите, что известно, что время в пути от каждой работы до каждого другого места работы.
2. Некоторые водопроводчики обладают навыками, которые другие не имеют.

Задача состоит в том, чтобы найти оптимальное назначение работ сантехникам, чтобы вознаграждение было максимально.

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

Я имею в виду жадный алгоритм, который работает следующим образом:

sort jobs by reward 
while true: 
    for each job: 
    find plumbers that could potentially handle this job 
     make a note of the association, used in next loop 
    if each plumber is associated with a different job, break 
    for each job that can be handled by a plumber: 
    assign job to a plumber: 
     if more than one plumber can handle this job, break tie somehow: 
     for instance if plumber A can do jobs X,Y but 
     plumber B can only do X, then give X to B. 
     else just pick a plumber to take it 
    remove assigned job from further consideration 
    if no jobs got assigned: 
    break out of "while true" loop 

Мой вопрос: есть ли лучший способ? Похоже на NP-трудную проблему, но у меня нет доказательств этого. :)

Я думаю, это похоже на Assignment Problem.

Кажется, что это немного по-другому, хотя из-за пространства/времени морщины: водопроводчик мог делать либо A, либо B, но не оба из-за расстояния между ними (не может добраться до B после окончания A). И задания должны быть завершены в определенные временные окна.

Также водопроводчик не может выполнять обе работы, если они слишком близки по времени (даже если они близки в пространстве). Например, если B необходимо запустить до времени_A_finished + time_to_travel_A_to_B, тогда B не может быть сделано после A.

Спасибо за любые идеи! Любые указатели на хорошие вещи для чтения в этой области также приветствуются.

Answer 1

Даже прокладка только одного водопроводчика между рабочими местами трудна, как проблема с продавцом NP-hard.

Я могу предложить два общих подхода для улучшения вашего жадного алгоритма. Первый - это локальный поиск. Получив жадное решение, посмотрите, есть ли какие-либо небольшие улучшения, связанные с назначением/перераспределением/не назначением нескольких заданий. Повторяйте до тех пор, пока не будет очевидных улучшений или закончится время процессора.

Другим подходом является линейное программирование с генерацией столбцов. Это более мощное, но гораздо более активное участие. Идея состоит в том, чтобы создать основную программу, в которой мы стараемся как можно больше захватить вознаграждение, выбирая использовать или не использовать каждый возможный график водопроводчика, при условии, что ограничения на упаковку будут выполняться только один раз и не использовать больше навыков водопроводчика, чем доступный. На каждом этапе решения основной программы двойные значения, соответствующие рабочим местам и сантехникам, отражают альтернативную стоимость выполнения конкретной работы/использования конкретного водопроводчика. Подзадача понимает, как направлять водопроводчика, чтобы захватить больше (скорректированную) награду, чем «затраты» водопроводчика. Эта подзадача NP-hard (в примечании выше), но она может поддаваться динамическому программированию или дальнейшим методам линейного программирования в зависимости от количества заданий. Вы быстро столкнетесь с внешними пределами исследований академических операций по этому пути.