Решение задачи минимизации общей продолжительности проекта

Сетевой график составляется после распределения всех ресурсов по каждой работе. Эти ресурсы определяют время выполнения работ. На сетевом графике не все работы критические. Поэтому можно уменьшить время за счет резервов на некритические работы, можно уменьшить время их выполнения и тем самым получить новый срок выполнения работ, меньший . Оптимальный сетевой план будет такой, когда получится наименьшим из всех возможных в данных условиях.

Обозначим ресурсы по работам а₁, а₂…., соответственно b₁, b₂ ….

Пусть работа а_i со временем ее выполнения t_i, лежит на критическом пути, а а_k – некоторая работа, лежащая на некритическом пути, и время ее выполнения – t_k.

Механизм перераспределения средств включает уменьшение средств работы а_k на некоторую величину x_i< b_k, что приводит к увеличению ее времени выполнения = φ(x_k)> t_k.

Средства x_k, вложенные в работу а_i, то есть x_k= x_i, приводят к уменьшению времени ее выполнения: < t_k.

В практике выполнения расчетов φ(x_k) и обычно представляют приближенными линейными выражениями вида:

; (14)

Обозначают - коэффициент пересчета.

Тогда формулы (14) примут вид:

;

При таких операциях должно выполняться условие: сумма снятых с некритических работ средств должна равняться сумме вложенных средств на критические работы: , где М – число работ, на которые средства вкладывались, а N – число работ, с которых средства снимались.

Общий срок выполнения всего комплекса работ определяется целевой функцией:

(15)

Здесь i – номера тех работ критического пути, средства которых не изменились.

Требуется так перераспределить средства с некритических работ на критические, чтобы функция (15) приняла наименьшее значение.

Сколько средств можно взять с некритической работы? Ясно, что все взять нельзя. Снимаемые средства определяют наличием резервов времени. Пусть свободный резерв времени работы а_k равен R_C (а_k). Тогда должно выполняться условие t_k x_kс_к ≤ R_C (а_k), откуда x_k≤ - ограничение на снимаемые с работы а_k средства.

Замечание. Если снимаются средства с работы а_k, лежащей на пути L, то нельзя вкладывать данные средства в другую работу, лежащую на этом пути, которая является также частью критического пути.

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

Пример

Провести оптимизацию сетевого графика (рис.9) по критерию минимума времени выполнения всех работ комплекса; построить оптимальный сетевой план работ; определить экономию. При условии, что с₁= 0,1; с₂= 0,2; с₃= 0,3; с₄= 0,4; с₅= 0,5; с₆= 0,6; с₇= 0,7; с₈= 0,9; с₉= 0,8; с₁₀= 1,0; с₁₁= 1,1; с₁₂= 1,2.