О сложности одной задачи комбинаторной оптимизации
В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится м...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2016
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/113762 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-113762 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1137622017-02-14T03:02:24Z О сложности одной задачи комбинаторной оптимизации Савельев, М.В. Моделювання і управління В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к NP-полной задаче «о ранце» для случая, когда на подмножестве работ отсутствуют ограничения следования. У статті розглядається одне із завдань комбінаторної оптимізації, пов'язане з виникаючою на практиці проблемою розстановки персоналу по безлічі робіт у разі, якщо на безлічі робіт можуть існувати обмеження на порядок їх виконання, а персонал має нерівнозначну підготовку. Наводиться математичне формулювання такого завдання і показується його зведення до NP-повної задачі «про ранці» для випадку, коли на підмножині робіт відсутні обмеження слідування. The article considers one of the tasks of combinatorial optimization, linked with the practice problems of arrangement of staff with different competence on a variety of jobs that have restrictions on their execution order and the staff has inadequate preparation. A mathematical formulation of this problem is provided. It is shown the reduction to NP-complete “knapsack” problem for the case when the following restrictions on the subset are absent. 2016 Article О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/113762 004.02: 004.942:007 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Моделювання і управління Моделювання і управління |
| spellingShingle |
Моделювання і управління Моделювання і управління Савельев, М.В. О сложности одной задачи комбинаторной оптимизации Математичні машини і системи |
| description |
В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к NP-полной задаче «о ранце» для случая, когда на подмножестве работ отсутствуют ограничения следования. |
| format |
Article |
| author |
Савельев, М.В. |
| author_facet |
Савельев, М.В. |
| author_sort |
Савельев, М.В. |
| title |
О сложности одной задачи комбинаторной оптимизации |
| title_short |
О сложности одной задачи комбинаторной оптимизации |
| title_full |
О сложности одной задачи комбинаторной оптимизации |
| title_fullStr |
О сложности одной задачи комбинаторной оптимизации |
| title_full_unstemmed |
О сложности одной задачи комбинаторной оптимизации |
| title_sort |
о сложности одной задачи комбинаторной оптимизации |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2016 |
| topic_facet |
Моделювання і управління |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/113762 |
| citation_txt |
О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT savelʹevmv osložnostiodnojzadačikombinatornojoptimizacii |
| first_indexed |
2024-03-30T09:28:51Z |
| last_indexed |
2024-03-30T09:28:51Z |
| _version_ |
1796150021689704448 |