АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ
Abstract
Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что NP-трудная многомерная задача о назначениях сводится к задаче поиска в n-дольном взвешенном гиперграфе максимального полного подгиперграфа, имеющего минимальную сумму весов вершин и ребер. Предлагаются жадные алгоритмы решения задачи и алгоритмы локального поиска в окрестности начального решения.
About the Author
А. Карпук
Научно-исследовательский институт средств автоматизации
Belarus
References
1. Karpuk, A.A. Zadacha optimizatsii ispol'zovaniya radiochastotnogo resursa pri prisvoenii chastot radioliniyam / A.A. Karpuk // Informatika. - 2006. - № 4 (12). - S. 5-13.
2. Sergeev, S.I. Kvadratichnaya zadacha naznacheniya / S.I. Sergeev // Avtomatika i telemekhanika. - 1999. - № 8. - S. 127-147.
3. Geri, M. Vychislitel'nye mashiny i trudnoreshaemye zadachi / M. Geri, D. Dzhonson. - M.: Mir, 1982. - 416 s.
4. Akho, A. Struktury dannykh i algoritmy / A. Akho, D. Khopkroft, D. Ul'man. - M.: Izdatel'skii dom «Vil'yams», 2000. - 384 s.
5. Kochetov, Yu.A. Veroyatnostnye metody lokal'nogo poiska dlya zadach diskretnoi optimizatsii / Yu.A. Kochetov // Diskretnaya matematika i ee prilozheniya: sb. lektsii molodezhnykh i nauchnykh shkol po diskretnoi matematike i ee prilozheniyam. - M.: MGU, 2001. - S. 87-117.
6. Special software for electromagnetic compatibility simulation and frequency assignment to radio sets of fixed-mobile radio communication systems / V. Voloshin [et al.] // Proc. 4th European Symposium on electromagnetic compatibility. - Brugge, 2000. - Vol. 2. - P. 119-122.
7. Karpuk, A.A. Zadacha o naznacheniyakh s uchetom kollizii / A.A. Karpuk // Informatsionnyi byulleten' Assotsiatsii matematicheskogo programmirovaniya: tez. dokl. konf. «Matematicheskoe programmirovanie i prilozheniya». - Ekaterinburg: UrO RAN, 2007. - № 11. - S. 178.
For citations:
. Informatics. 2008;(2(18)):5-13.
(In Russ.)
Views: 630
Email this article 