Предшествующее событие

Предшествующее событие

h

Данная таблица аналогична таблицам, используемым при решении задачи о кратчайшем или максимальном пути с проведением расчетов в направлении «от начала к концу». Запоминать работы можно, например, расставляя пометки (в виде стрелок или засечек на соответствующих дугах сети) либо отмечая в таблице знаками «/» предшествующие события. После завершения расчетов критический путь определяется как и в задаче о кратчайшем или максимальном пути, начиная с завершающего события.

Поздний срок свершения события і (будем обозначать его через tn(i))—наиболее поздний момент времени, с которого все последовательности работ, начинающиеся с события і и заканчивающиеся завершающим событием F, могут завершиться в пределах критического срока. Таким образом, поздний срок свершения события определяется из соотношения

t„(*)+ max{T(L(i,F))} = Ткр,

L{i,F)

где максимум берется по всем путям L(i,F) от события і до завершающего события F. Данная формула имеет отношение к трудоемкому методу перечисления путей. В то же время идеи, лежащие в основе метода ДП, позволяют получить иную существенно более эффективную методику вычисления поздних сроков, основанную на формуле

*п(г)= .min {tu(j) -T(i,j)},

в которой минимум берется по всем событиям j, следующим за событием г. Расчет начинается с завершающего события F и условия tn(F) = Ткр (критический срок уже известен после расчета ранних сроков), а заканчивается исходным событием /; при этом должно получиться tn(I) — 0. Заметим, что критический путь уже построен при расчете ранних сроков; следовательно, в ходе расчета поздних сроков нет необходимости запоминать последующие за событием і работы, на которых достигается вычисляемый минимум.

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

Резерв времени события і (будем обозначать его через г (і)) — наибольший срок задержки события, не приводящий к нарушению критического срока. После вычисления ранних и поздних сроков резервы времени событий рассчитываются по формуле

г (г) = tn(i) tp(i).

При этом г (і) ^ 0, а критические события имеют нулевой резерв времени.

В заключение раздела покажем, каким образом может быть установлена приведенная выше формула для расчета поздних сроков (в ней впервые среди формул подобного типа встречается знак «минус»). Для этого учтем, что любой путь L(i,F) от текущего события і к завершающему событию F обязательно проходит через одно из последующих к г событий j Є V+(i); следовательно,

T(L(i,F))=T(i,j)+T(L(j,F)).

Максимумы обеих частей последнего равенства также' равны:

max {T(L(i,F))} = max{T(i,j)+T(L(j,F))}.

L(i,F) L{i,F)

Выделяя первую работу (i,j) на пути L(i,F), преобразуем правую часть полученного равенства:

max {Т(г, j) + Т (L(j, F)) — max { max [T(i,j) +T(L(j, F))}}.

L(i,F) "J j&V+U) (L(j,F)

Слагаемое T(i,j) в правой части последнего равенства можно вынести за знак внутреннего максимума, поскольку оно не зависит от после-

i^o{^№j') + r(L(j,F))}} =

= ^Ъ{Т{^) + н^){ТШГ))}У

Таким образом, получаем соотношение

max {Т (L(i, F))} = max {T(i,j)+ max {T (L(j, F))}.

По определению позднего срока свершения события имеем: *п(0 = Гкрmax{T(L(t,F))}.

L(i,F)

С учетом полученного выше соотношения можно записать: tu(i) = Ткр max {T(i,j) + max {T(L(j,F))}}.

Используя общую формулу

—max{F(a:)} = min{—F(x)},

X X

уже упоминавшуюся в гл. 1, получаем:

tn(i) = Ткр + min {-T(i,j) max {Т (L(j, F))}}.

Критический срок Ткр не зависит от выбора промежуточного состояния j Є V+(i), так что его можно внести под знак минимума:

t„(t) = min {Ткрmax {T(L(j,F))} -T(i,j)}.

jeV+(i) L(j,F)

Поскольку

Ткр max{T(L(i,F))}=rn(j),

L{],F)

то окончательно получаем требуемую формулу для вычисления поздних сроков.