Рассматривается задача календарного планирования инвестиционных проектов с ограниченными ресурсами в денежной форме. Критерием оптимального расписания начала для каждой из работ проекта выступает максимум чистой приведённой стоимости, при котором выполняются ограничения на достаточность средств и учитываются технологические взаимосвязи между работами. Данная задача является NP-трудной в сильном смысле. Доказано, что расписание проекта представимо в виде решения линейного уравнения над идемпотентным полукольцом. Установлено достаточное условие допустимости расписания с точки зрения частичного порядка работ и срока реализации проекта. Доказано, что каждое из расписаний проекта может быть представлено в виде произведения матрицы специального вида, рассчитанной на основе матрицы частичного порядка проекта, и вектора из идемпотентого полумодуля. Для координат вектора определены ограничения сверху и снизу, учитывающие сроки реализации работ. Приводится описание генетического алгоритма решения задачи. В его основе лежит эволюция популяции, особи которой представляют собой решения идемпотентного уравнения для матрицы частичного порядка проекта. Проведённые вычислительные эксперименты демонстрируют эффективность предложенного алгоритма.
Скачать электронную версию публикации
Загружен, раз: 35
- Title Применение методов идемпотентной алгебры в генетическом алгоритме для решения задачи календарного планирования
- Headline Применение методов идемпотентной алгебры в генетическом алгоритме для решения задачи календарного планирования
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 58
- Date:
- DOI 10.17223/20710410/58/11
Ключевые слова
задача календарного планирования, инвестиционный проект, NPV, идемпотентная алгебра, генетический алгоритмАвторы
Ссылки
Гимади Э. Х., Пузынина Н. М. Задача календарного планирования крупномасштабного проекта в условиях ограниченных ресурсов: Опыт построения математического обеспечения // Управляемые системы. 1983. Вып.23. С. 24-32.
Гимади Э. Х., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7. Вып. 1. С. 9-34.
Гончаров Е. Н., Леонов В. В. Генетический алгоритм для задачи календарного планирования с ограниченными ресурсами // Автоматика и телемеханика. 2017. №6. С. 173-179.
Гончаров Е. Н., Мишин Д. В. Точный алгоритм для задачи календарного планирования с ограниченными ресурсами // Прикладная математика и фундаментальная информатика. 2017. Т. 4. №1. С. 43-53.
Hartmann S. and Briskorn D. An updated survey of variants and extensions of the resource-constrained project scheduling problem // Eur. J. Operat. Res. 2022. Iss. 1. P. 1-14.
Habibi F., Barzinpour F., and Sadjadi S. Resource-constrained project scheduling problem: review of past and recent developments //j. Project Management. 2018. V. 3. Iss. 2. P. 55-88.
Казаковцева Е. А., Сервах В. В. Сложность задачи календарного планирования с кредитованием // Дискретный анализ и исследование операций. 2015. Т. 22. №4. С. 35-49.
Сервах В. В., Сухих С. Л. Гибридный алгоритм для задачи календарного планирования с учетом реинвестирования прибыли // Автоматика и телемеханика. 2004. Вып. 3. С.100-107.
Bulavchuk A. M. and Semenova D. V. Genetic algorithm based on idempotent algebra methods for RCPSP // IEEE 15th Intern. Conf. AICT. 2021. P. 1-4.
Литвинов Г. Л., Маслов В. П., Соболевский А. Н. Идемпотентная математика и интервальный анализ // Вычислительные технологии. 2001. Т. 6. №6. С. 41-70.
Кривулин Н. К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем. СПб.: Изд-во С.-Петерб. ун-та, 2009. 256с.
Омельченко А. В. Теория графов. М.: МЦНМО, 2018. 416с.
Кочетов Ю.А., Столяр А. А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. 2005. Т 12. №1. С. 12-36.
https://www.om-db.wi.tum.de/psplib/- Project scheduling problem library. 2022.
Применение методов идемпотентной алгебры в генетическом алгоритме для решения задачи календарного планирования | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/11
Скачать полнотекстовую версию
Загружен, раз: 88