О сложности одной задачи календарного планирования со складируемыми ресурсами

Abstract

В работе рассматривается задача календарного планирования проектов с учетом ограничений на складируемые ресурсы и критерием чистой приведенной прибыли. Доказано, что данная задача является NP-трудной в сильном смысле. Исследован частный случай задачи при независимых работах. Для этого случая предложен точный алгоритм решения, основанный на методе динамического программирования. Получены необходимые условия, при которых алгоритм является псевдополиномиальным.