О сложности одной задачи комбинаторной оптимизации
В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится м...
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| _version_ | 1862737453418283008 |
|---|---|
| author | Савельев, М.В. |
| author_facet | Савельев, М.В. |
| citation_txt | О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| 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.
|
| first_indexed | 2025-12-07T19:58:59Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-113762 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T19:58:59Z |
| publishDate | 2016 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| 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 |
| spellingShingle | О сложности одной задачи комбинаторной оптимизации Савельев, М.В. Моделювання і управління |
| title | О сложности одной задачи комбинаторной оптимизации |
| title_alt | Про складність однієї задачі комбінаторної оптимізації On complexity of the problem of combinatorial optimization |
| title_full | О сложности одной задачи комбинаторной оптимизации |
| title_fullStr | О сложности одной задачи комбинаторной оптимизации |
| title_full_unstemmed | О сложности одной задачи комбинаторной оптимизации |
| title_short | О сложности одной задачи комбинаторной оптимизации |
| title_sort | о сложности одной задачи комбинаторной оптимизации |
| topic | Моделювання і управління |
| topic_facet | Моделювання і управління |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113762 |
| 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 |