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

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

Статья представлена к публикации членом редколлегии: В. В. Кульба