Development of mathematical models and algorithms for optimizing the schedule of independent project activities
Authors: Россихина Л.В. 
Published: July 2024

Планирование является одним из важных процессов для проекта. К основным процессам планирования относятся определение работ, планирование ресурсов, определение продолжительности работ, разработка расписания. В статье рассматриваются проекты с независимыми работами. Целью исследования является оптимизация графика выполнения работ по периодам. Рассмотрены три частные задачи. Первая задача состоит в распределении работ по периодам таким образом, чтобы достичь максимального суммарного эффекта от их реализации с учетом ограничения затрат в каждом периоде и возможности частичного выполнения работ в данном периоде. Алгоритм решения основан на методе «Затраты – эффект». Доказана обоснованность предложенного алгоритма. Во второй задаче рассматривается распределение работ по периодам при запрете переноса части работ в другие периоды и ограничении затрат в каждом периоде. На основе метода дихотомического программирования предложен алгоритм решения задачи для двух периодов. Для количества периодов больше двух предложен приближенный алгоритм. Для случая, когда информация о невыполненных работах в ходе реализации проекта изменяется, рассмотрена задача максимизации суммарного эффекта от реализации работ проекта в текущем периоде. Причем эффект от реализации множества работ появляется после их завершения и определенный эффект появляется от частичной реализации другого множества работ. При этом получаемый эффект пропорционален части выполненного объема работ. Предложен алгоритм решения задачи, основанный на получении параметрических зависимостей суммарного эффекта для каждого множества работ от величины затрат. Доказана обоснованность алгоритма. Приведены примеры, иллюстрирующие применение предложенных алгоритмов.

Planning is an important process for a project. The main planning processes include defining activities, planning resources, determining the duration of work, and developing a schedule. The paper examines projects with independent activities. The purpose of the study is to optimize project schedule by period. Three particular problems are considered. The first problem is to distribute activities over periods in order to achieve the maximum total effect of their implementation taking into account cost constraints in each period and the possibility of partial implementation of the activities in a given period. The solution algorithm is based on the Cost-Effect method. The validity of the proposed algorithm has been proved. The second problem deals with the distribution of work over periods with the prohibition of transferring part of the work to other periods and limitation of costs in each period. Based on the method of dichotomous programming, we propose an algorithm for solving the problem for two periods. For the number of periods greater than two, an approximate algorithm is suggested. For the case when information on unperformed activities in the course of project implementation changes, the problem of maximizing the total effect from the implementation of project activities in the current period is considered. Additionally, the effect from the implementation of a set of activities is visible after their completion and a certain effect manifests from the partial implementation of another set of activities. The effect obtained is proportional to the part of the amount of work performed. An algorithm for solving the problem based on obtaining parametric dependences of the total effect for each set of activities on the value of costs is proposed. The validity of the algorithm has been proved. Examples illustrating the application of the proposed algorithms are presented.