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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

Приближённые алгоритмы

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

См. также

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