О сложности одной задачи комбинаторной оптимизации

• Published in: Математичні машини і системи
• Date: 2016
• Main Author: Савельев, М.В.
• Format: Article
• Language: Russian
• Published: Інститут проблем математичних машин і систем НАН України 2016
• Subjects: Моделювання і управління
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/113762
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос.

В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к 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.