Некоторые оптимизационные задачи сетевого планирования (оптимизация проекта во времени, по ресурсам, по стоимости)

После расчёта временных параметров сетевого графика анализируют можно ли использовать его в качестве плана выполнения работ. Чаще всего требуется улучшение качества сетевых графиков с целью изменения сроков выполнения работ и рационального использования материалов, трудовых, денежных ресурсов.

Задача оптимизации проекта по времени с использованием дополнительных средств имеет 2 постановки:

1) необходимо определить величину дополнительных вложений в отдельные работы проекта с тем, чтобы общий срок его выполнения не превышал заданной величины, а суммарный расход дополнительных средств был минимальным.

Пусть задан сетевой график,

где E -событие;

e – работа.

Продолжительность каждой работы равняется. Известно, что вложение дополнительных средств в отдельные работы уменьшает продолжительность до,которая равна = - *

- коэффициенты использования дополнительных средств x_ij.

Продолжительность работы не может быть меньше величины. Требуется определить количество дополнительных средств, которые необходимо вложить в конкретные работы, а также установить время начала и время окончания каждой работы, чтобы проект завершился не позже, а суммарный расход дополнительных средств был минимальным.

Математическая модель будет иметь следующий вид:

условная функция

(3)

(4)

(5)

Первое ограничение означает, что время завершения проекта не должно быть >

Второе ограничение показывает зависимость продолжительности каждой работы от вложенных в него дополнительных средств

Третье ограничение означает, что продолжительность каждой работы должна быть равна либо больше минимальной её продолжительности

Четвертое ограничение выполнение условия предшествующих работ, то есть время начала каждой работы должно быть не меньше времени окончания предшествующих ей работ

Пятое ограничение – условие неотрицательности.

Вторая постановка задачи оптимизации проекта по времени с использованием дополнительных средств предполагает сокращение срока проекта насколько это возможно за счёт вложения суммы денежных средств не превышающей величины В.

Целевая функция будет иметь вид

Остальные ограничения (2)-(5) такие же как в предыдущей задачи.

Оптимизация проекта по ресурсам.

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

Оптимизация проекта по стоимости.

В общем случае стоимость выполнения работы зависит от её продолжительности. Пусть нормальная продолжительность работы. Ей соответствует минимальная стоимость выполнения работы. минимально возможная продолжительность работы. При этой стоимости работы будет максимальной.

Если при планировании проекта будет взята её наибольшая продолжительность, то есть, то стоимость проекта будет минимальной и наоборот.

Предположим, что затраты выполнения работ находятся в обратной зависимости от продолжительности их выполнения. Коэффициент дополнительных затрат h_ij покажет насколько увеличилась стоимость работы при уменьшении её продолжительности на единицу и рассчитывается по формуле

При фиксированном сроке проекта выполнения оптимизация выполняется следующим образом. Необходимо минимизировать стоимость проекта при фиксированном сроке его завершения за счёт увеличения времени выполнения отдельных работ увеличение продолжительности работ по сравнению с минимальным сроком её выполнения

Уменьшение продолжительности на величину приведёт к экономии средств на величину

В данном случае математическая модель задачи примет вид

Если, то оптимизация осуществляется за счёт увеличения продолжительности некритических работ; если >, то за счёт всех работ проекта.

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

Для этого используется алгоритм, при котором сокращается продолжительность работ, так как сокращение некоторых работ увеличит стоимость выполнения всего комплекса работ не влияя на длину критического пути.