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

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

Специальные случаи

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

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

Если имеется всего один агент, задача сводится к задаче о ранце.

Определение

Имеется n работ $x_{1},\dots ,x_{n}$ и m исполнителей $b_{1},\dots ,b_{m}$. Каждый исполнитель $b_{i}$ имеет бюджет $w_{i}$. Для каждой пары исполнитель $b_{i}$ и работа $x_{j}$ задан доход $p_{i,j}$ и вес $w_{i,j}$. Решением является подмножество работ U и распределение работ из U по исполнителям. Решение допустимо, если сумма затрат на назначенные работы исполнителя $b_{i}$ не превосходит бюджета $w_{i}$. Доходом от решения является сумма всех доходов всех распределений работа-исполнитель.

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

maximize $\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.$

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

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

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

Обобщённая задача о назначениях является NP-трудной и даже APX-трудной.

Фляйшер, Гоманс, Мирокни и Свириденко предложили комбинаторный алгоритм локального поиска с аппроксимацией $(2+\varepsilon )$ и алгоритм на основе линейного программирования с аппроксимацией $({\frac {e}{e-1}}+\varepsilon )$.

Аппроксимация $({\frac {e}{e-1}}+\epsilon )$ является лучшей известной аппроксимацией обобщенной задачи о назначениях.

Жадный аппроксимирующий алгоритм

Используя алгоритм $\alpha$-аппроксимации задачи о назначениях, можно создать ($\alpha +1$)-аппроксимацию для обобщенной задачи о назначениях на манер жадного алгоритма используя концепцию остатка дохода. Алгоритм итерационно создает предварительную последовательность, в которой на итерации $j$ предполагается закрепить работы за исполнителем $b_{j}$. Выбор для исполнителя $b_{j}$ может быть изменён в дальнейшем при закрепление работ за другими исполнителям. Остаток дохода работы $x_{i}$ для исполнителя $b_{j}$ равен $p_{ij}$, если $x_{i}$ не отдана другому исполнителю, и $p_{ij}$ – $p_{ik}$, если работа отдана исполнителю $b_{k}$.

Формально:

Используем вектор $T$ для предварительного выбора и в этом векторе

$T[i]=j$ означает, что на работу $x_{i}$ предполагается назначить исполнителя $b_{j}$,

$T[i]=-1$ означает, что на работу $x_{i}$ никто не назначен.

Остаток дохода на итерации $j$ обозначается через $P_{j}$, где

$P_{j}[i]=p_{ij}$, если работа $x_{i}$ не выбрана (т.е. $T[i]=-1$)

$P_{j}[i]=p_{ij}-p_{ik}$, если работу $x_{i}$ предполагается отдать исполнителю $b_{k}$ (т. е. $T[i]=k$).

Таким образом, алгоритм выглядит следующим образом:

Присваиваются начальные значения $T[i]=-1$ для всех $i=1\ldots n$

Для всех $j=1...m$ выполнить:

Используется алгоритм аппроксимации для получения распределения работ для исполнителя $b_{j}$, используя функцию остатка дохода $P_{j}$. Обозначаются выбранные работы $S_{j}$.

Подправляется $T$, используя $S_{j}$, т. е. $T[i]=j$ для всех $i\in S_{j}$.

конец цикла

См. также

• Задача о назначениях

Ссылки

• Reuven Cohen, Liran Katzir, and Danny Raz, "An Efficient Approximation for the Generalized Assignment Problem", Information Processing Letters, Vol. 100, Issue 4, pp. 162–166, November 2006.
• Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko, "Tight Approximation Algorithms for Maximum General Assignment Problems", SODA 2006, pp. 611–620.
• Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems , 2005. Springer Verlag ISBN 3-540-40286-1