Тип публикации: статья из журнала
Год издания: 2022
Идентификатор DOI: 10.17223/20710410/58/11
Ключевые слова: scheduling problem, investment project, idempotent mathematics, genetic algorithm, задача календарного планирования, инвестиционный проект, npv, идемпотентная алгебра, генетический алгоритм
Аннотация: Рассматривается задача календарного планирования инвестиционных проектов с ограниченными ресурсами в денежной форме. Критерием оптимального расписания начала для каждой из работ проекта выступает максимум чистой приведённой стоимости, при котором выполняются ограничения на достаточность средств и учитываются технологические взаимосПоказать полностьювязи между работами. Данная задача является NP-трудной в сильном смысле. Доказано, что расписание проекта представимо в виде решения линейного уравнения над идемпотентным полукольцом. Установлено достаточное условие допустимости расписания с точки зрения частичного порядка работ и срока реализации проекта. Доказано, что каждое из расписаний проекта может быть представлено в виде произведения матрицы специального вида, рассчитанной на основе матрицы частичного порядка проекта, и вектора из идемпотентого полумодуля. Для координат вектора определены ограничения сверху и снизу, учитывающие сроки реализации работ. Приводится описание генетического алгоритма решения задачи. В его основе лежит эволюция популяции, особи которой представляют собой решения идемпотентного уравнения для матрицы частичного порядка проекта. Проведённые вычислительные эксперименты демонстрируют эффективность предложенного алгоритма. The resource-constrained project scheduling problem in monetary form is considered. The criterion for the optimal start schedule for each project activity is the maximum net present value, which fulfills the constraints on sufficiency of funds and takes into account the technological relationship between the activities. This problem is NP-hard in a strong sense. It is proved that the project schedule can be represented as a solution of a linear equation over an idempotent semiring. A sufficient condition has been established for the admissibility of the schedule in terms of the partial order of work and the duration of the project. It is proved that each of the project schedules can be represented as a product of a matrix of a special form, calculated on the basis of the partial order matrix of the project, and a vector from an idempotent semimodule. For the coordinates of the vector, upper and lower limits have been determined, taking into account the timing of the activity. A description of the genetic algorithm for solving the problem is given. The algorithm is based on the evolution of a population whose individuals represent solutions of an idempotent equation for a partial order matrix of the project. The computational experiments demonstrate the effectiveness of the algorithm.
Журнал: Прикладная дискретная математика
Выпуск журнала: №58
Номера страниц: 112-124
ISSN журнала: 20710410
Место издания: Томск
Издатель: Национальный исследовательский Томский государственный университет