Расчет временных параметров

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

Временем Т_j наступления (или свершения) события j считается момент окончания всех работ, входящих в это событие.

Минимальное (самое раннее) время Т_j^о наступления события j равно длине максимальному из путей, предшествующих данному событию. Очевидно, что это время является и самым ранним временем начала работ, выходящих из этого события. Например, в последнем примере событие 3 может свершиться не ранее, чем через 11 дней от исходного события, т.к. наибольшая длина пути, предшествующего данному событию (пути (0,2)-(2,3)) равна 11.

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

Для вычисления Т_j^о необходимо сначала рассмотреть все события i, соединенные дугой (i,j) с данным событием j, вычислить для них ранние времена и при этом на каждом шаге использовать формулу

Т_j^о =maxí Т_i^о + t_ijý (1)

^"i

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

Проиллюстрируем алгоритм вычисления ранних времен на последнем примере.

Принимаем Т₀^о =0. Поскольку в событие 1 входит только одна работа (0,1) продолжительностью t₀₁=2, то Т₁^о = Т₀^о + t₀₁ =0+2=2.

Рассмотрим далее событие 2 (Заметим, что событие 3 пока рассматривать нельзя, так как срок Т₂^о еще неизвестен). Таким образом, Т₂^о =Т₀^о + t₀₂ =0+5=5. Перейдем теперь к событию 3. Поскольку в него входят три дуги (0,3),(2,3) и (1,3), то

Т₃^о =maxí Т_i^о + t_i3ý= maxí 0 + 3; 2+4; 5+6ý=11.

^i=0,1,2

Вычисления продолжаем аналогичным образом, пока не будут определены значения Т_j^о для всех событий j. Имеем

Т₄^о = Т₂^о + t₂₄ = 5 + 2 = 7,

Т₅^о = Т₂^о + t₂₅ = 5 + 1 = 6,

Т₆^о = Т₃^о + t₃₆ = 11 + 3 = 14,

Т₇^о =maxí Т_i^о + t_i7ý= maxí7+10; 6+8ý=17,

^i=4,5

Т₈^о =maxí Т_i^о + t_i8ý= maxí6+4; 14+3; 17+5ý=22.

^i=5,6,7

На этом вычисления Т_i^о заканчиваются.

Теперь от завершающего события к исходному (справа налево) определяем Т_i¹ - максимально допустимый (поздний) срок завершения всех работ, входящих в данное событие, при котором критическое время выполнения всего комплекса работ останется неизменным. Если обозначить n– завершающее событие сети, то Т_n¹ = Т_n⁰ является отправной точкой алгоритма вычисления поздних сроков. В общем виде для любого события i,

Т_i¹ =min í Т_j¹ - t_ijý для всех дуг (i,j). (2)

^"j

Вычислим значения Т_i¹ на последнем примере (рис.5).

Т₈¹ = Т₈⁰=22,

Т₇¹ = Т₈¹ - t₇₈ = 22 – 5 = 17,

Т₆¹ = Т₈^о - t₆₈ = 22 – 3 = 19,

Т₅¹ =min í Т_j¹ – t_5jý= miní17–8; 22 - 4ý=9,

^j=7,8

Т₄¹ = Т₇¹ - t₄₇ = 17 – 10 = 7,

Т₃¹ = Т₆¹ - t₃₆ = 19 – 3 = 16,

Т₂¹ =min íТ_j^о - t_2jý= miní16–6; 7 – 2; 9 - 1ý=5,

^j=3,4,5

Т₁¹ = Т₃¹ - t₁₃ = 16 - 4 = 12,

Т₀¹ =min íТ_j¹ – t_0jý= miní12–2; 5 – 5; 16 – 3ý=0.

^j=1,2,3

Определим резерв времени R_i i-го события как разность между поздним и ранним сроками его свершения:

R_i = Т_i¹ - Т_i⁰ (3)

Резерв времени события показывает, на какой допустимый период времени можно задержать наступление данного события, не вызывая при этом увеличения срока выполнения комплекса работ. Сведем результаты вычислений значений Т_i¹ , Т_i^о и R_i в табл1:

Таблица 1

Теперь, используя данные табл. 1, можно определить работы критического пути (без полного перебора полных путей). Работа (i,j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям:

Т_i⁰=Т_i¹

Т_j^о = Т_j¹ (4)

Т_j^о - Т_i^о =Т_j¹ - Т_i¹ = t_ij

По существу, эти условия означают, что между ранним сроком начала (окончания) и поздним сроком начала (окончания) критической работы запас времени отсутствует. Условиям (4) удовлетворяют работы (0,2), (2,4), (4,7) и (7,8), т.е. они образуют критический путь, в чем мы и ранее убедились перебором всех полных путей.

Временные параметры работ.

Различают несколько разновидностей резервов времени работ, мы рассмотрим два основных вида: полный резерв и свободный резерв. Полный резерв работы (i,j) определяется по формуле:

R^п_ij=Т_j¹ - Т_i⁰ - t_ij (5)

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

Полный резерв критических работ равен 0. У некритических работ R^п_ij > 0. При использовании полного резерва времени только для одной работы резервы времени остальных работ, лежащих на максимальном пути, проходящем через нее, будут полностью исчерпаны, т.е. увеличение продолжительности некритической работы за счет использования всего ее полного резерва обязательно влечет появление нового критического пути, в состав которого войдет эта работа.

Опоздание начала некритической работы (i,j) по сравнению с Т_i⁰ на всю величину ее полного резерва влечет за собой необходимость начинать все работы, выходящие из события j в наиболее позднее допустимое время Т_j¹ наступления этого события.

Свободный резерв времени R^с_ij работы (i,j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершаются в свои самые ранние сроки.

R^с_ij=Т_j⁰ - Т_i⁰ - t_ij (6)

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

Для рис. 5 проведем вычисления по формулам (5), (6):

Таблица 2

В табл. 2 приведены результаты расчетов временных параметров работ. Она содержит всю необходимую для построения календарного плана (графика) информацию. Когда полный резерв равен 0, свободный резерв также должен быть равен 0. Однако обратное неверно, поскольку свободный резерв некритической работы также может быть нулевым (например, работы (0,1), (2,3)).