Применение методов идемпотентной алгебры в генетическом алгоритме для решения задачи календарного планирования

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