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

Имеется 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].

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