АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ
Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на эти...
Saved in:
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2018-10-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/557 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849336324306239488 |
|---|---|
| collection | DOAJ |
| description | Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что NP-трудная многомерная задача о назначениях сводится к задаче поиска в n-дольном взвешенном гиперграфе максимального полного подгиперграфа, имеющего минимальную сумму весов вершин и ребер. Предлагаются жадные алгоритмы решения задачи и алгоритмы локального поиска в окрестности начального решения. |
| format | Article |
| id | doaj-art-1e6efdd7d31a4c819772b2e373644f36 |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2018-10-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-1e6efdd7d31a4c819772b2e373644f362025-08-20T03:45:01ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012018-10-0102(18)513523АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ0Научно-исследовательский институт средств автоматизацииРассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что NP-трудная многомерная задача о назначениях сводится к задаче поиска в n-дольном взвешенном гиперграфе максимального полного подгиперграфа, имеющего минимальную сумму весов вершин и ребер. Предлагаются жадные алгоритмы решения задачи и алгоритмы локального поиска в окрестности начального решения.https://inf.grid.by/jour/article/view/557 |
| spellingShingle | АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ Informatika |
| title | АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ |
| title_full | АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ |
| title_fullStr | АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ |
| title_full_unstemmed | АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ |
| title_short | АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ |
| title_sort | алгоритмы решения многомерной задачи о назначениях |
| url | https://inf.grid.by/jour/article/view/557 |