Аннотация:
Рассматривается задача календарного планирования инвестиционных проектов с ограниченными ресурсами (RCPSP) и критерием максимизации чистой приведенной стоимости (NPV). Мы предлагаем два эвристических алгоритма для RCPSP, основанных на методах идемпотентной алгебры. Для оценки качества работы алгоритмов была построена бинарная модель целочисленного линейного программирования для рассматриваемой задачи. Эта модель позволяет находить точные решения задачи с помощью программного комплекса IBM ILOG CPLEX. Эксперименты показывают, что разработанные нами эвристические алгоритмы демонстрируют высокую результативность. В серии экспериментов были получены в том числе расписания, соответствующие точным решениям.