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

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

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

В случае, когда бюджеты исполнителей и все стоимости работ равны 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}\le w_{i}i=1,\dots ,m$;

$\sum _{i=1}^m{x}_{ij}\le 1j=1,\dots ,n$;

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

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

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

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

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

Используя алгоритм $\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\dots 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