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

Abstract

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