О сложности одной задачи комбинаторной оптимизации
В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится м...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2016 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/113762 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-113762 |
|---|---|
| record_format |
dspace |
| spelling |
Савельев, М.В. 2017-02-13T16:57:03Z 2017-02-13T16:57:03Z 2016 О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/113762 004.02: 004.942:007 В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к 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. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління О сложности одной задачи комбинаторной оптимизации Про складність однієї задачі комбінаторної оптимізації On complexity of the problem of combinatorial optimization Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О сложности одной задачи комбинаторной оптимизации |
| spellingShingle |
О сложности одной задачи комбинаторной оптимизации Савельев, М.В. Моделювання і управління |
| title_short |
О сложности одной задачи комбинаторной оптимизации |
| title_full |
О сложности одной задачи комбинаторной оптимизации |
| title_fullStr |
О сложности одной задачи комбинаторной оптимизации |
| title_full_unstemmed |
О сложности одной задачи комбинаторной оптимизации |
| title_sort |
о сложности одной задачи комбинаторной оптимизации |
| author |
Савельев, М.В. |
| author_facet |
Савельев, М.В. |
| topic |
Моделювання і управління |
| topic_facet |
Моделювання і управління |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Про складність однієї задачі комбінаторної оптимізації On complexity of the problem of combinatorial optimization |
| description |
В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к 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.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/113762 |
| citation_txt |
О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. |
| work_keys_str_mv |
AT savelʹevmv osložnostiodnoizadačikombinatornoioptimizacii AT savelʹevmv proskladnístʹodníêízadačíkombínatornoíoptimízacíí AT savelʹevmv oncomplexityoftheproblemofcombinatorialoptimization |
| first_indexed |
2025-12-07T19:58:59Z |
| last_indexed |
2025-12-07T19:58:59Z |
| _version_ |
1850880860609314816 |