АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ
Аннотация
Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что NP-трудная многомерная задача о назначениях сводится к задаче поиска в n-дольном взвешенном гиперграфе максимального полного подгиперграфа, имеющего минимальную сумму весов вершин и ребер. Предлагаются жадные алгоритмы решения задачи и алгоритмы локального поиска в окрестности начального решения.
Об авторе
А. А. Карпук
Научно-исследовательский институт средств автоматизации
Беларусь
Список литературы
1. Карпук, А.А. Задача оптимизации использования радиочастотного ресурса при присвоении частот радиолиниям / А.А. Карпук // Информатика. - 2006. - № 4 (12). - С. 5-13.
2. Сергеев, С.И. Квадратичная задача назначения / С.И. Сергеев // Автоматика и телемеханика. - 1999. - № 8. - С. 127-147.
3. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. - М.: Мир, 1982. - 416 с.
4. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман. - М.: Издательский дом «Вильямс», 2000. - 384 с.
5. Кочетов, Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации / Ю.А. Кочетов // Дискретная математика и ее приложения: сб. лекций молодежных и научных школ по дискретной математике и ее приложениям. - М.: МГУ, 2001. - С. 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. Карпук, А.А. Задача о назначениях с учетом коллизий / А.А. Карпук // Информационный бюллетень Ассоциации математического программирования: тез. докл. конф. «Математическое программирование и приложения». - Екатеринбург: УрО РАН, 2007. - № 11. - С. 178.
Для цитирования:
Карпук А.А.
АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ. Информатика. 2008;(2(18)):5-13.
Просмотров: 629
Послать статью по эл. почте 