RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2022, номер 58, страницы 112–124 (Mi pdm790)

Эта публикация цитируется в 2 статьях

Вычислительные методы в дискретной математике

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

А. М. Булавчук, Д. В. Семенова

Сибирский федеральный университет, г. Красноярск, Россия

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

Ключевые слова: задача календарного планирования, инвестиционный проект, NPV, идемпотентная алгебра, генетический алгоритм.

УДК: 519.8

DOI: 10.17223/20710410/58/11



© МИАН, 2024