Задача о назначении минимального количества исполнителей

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

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

Имеется n исполнителей и m работ. Для каждой пары исполнитель и работа заданы затраты на выполнения работы ${\displaystyle w_{i,j}}$. Имеется общий бюджет ${\displaystyle w}$ на выполнения всего комплекса работ. Решением является подмножество исполнителей U и распределение назначения исполнителей из U по работам. Решение допустимо, если назначены исполнители для всех работ и сумма затрат для этого не превосходит бюджета ${\displaystyle w}$. Требуется минимизировать количество назначенных исполнителей (L). Другими словами, требуется подобрать минимальное по размеру (мощности) множество исполнителей, которые вместе смогут выполнить все работы.

Задача может решаться путем разбиения на две задачи:

1. Подбор минимальной по численности группы исполнителей, которые вместе смогут выполнить все работы и уложатся в бюджет ${\displaystyle w}$. Данная проблема NP-трудная, т.к. является обобщением NP-полной задачи о покрытии множества.
2. Назначение в подобранной группе исполнителей по работам.

Математически задачу о назначениях минимального количества исполнителей можно сформулировать следующим образом^[1]:

minimize ${\displaystyle L=\mid U\mid =\sum _{i=1}^{n}\max _{j=1}^{m}x_{ij}}$

subject to ${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}w_{ij}x_{ij}\leq w.}$

${\displaystyle \sum _{i=1}^{n}x_{ij}=1\qquad j=1,\ldots ,m}$;

${\displaystyle x_{ij}\in \{0,1\}\qquad i=1,\ldots ,n,\quad j=1,\ldots ,m}$.

В данной постановке целевая функция задачи нелинейна, что не позволяет напрямую найти оптимальное решение точными методами линейного программирования, включая симплекс-метод. Однако, задачу можно линеаризовать, включив дополнительные переменные ${\displaystyle y_{i}}$, показывающие факт выбора в группу исполнителя ${\displaystyle i}$, ${\displaystyle y_{i}\in \{0,1\}\qquad i=1,\ldots ,n}$. Требуется также связать переменные ${\displaystyle y_{i}}$ и ${\displaystyle x_{ij}}$. Тогда целевая функция примет вид

minimize ${\displaystyle L=\mid U\mid =\sum _{i=1}^{n}y_{i}}$.

Связь же переменных можно задать следующим условием:

${\displaystyle y_{i}\leq \sum _{j=1}^{m}x_{ij}\leq my_{i}\qquad i=1,\ldots ,n}$

Для быстрого решения задач большой размерности целесообразно использовать приближенные алгоритмы: алгоритм максимального количества минимальных элементов (МКМЭ) и алгоритм максимального количества допустимых элементов (МКДЭ)^[2].

• Задача о назначениях
• Обобщённая задача о назначениях