УДК: 519.854.2

Реферат:

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