Понятие о пути

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

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

2) путь от начального события до данного события сети называется путем, предшествующим этому событию, а путь, соединяющий это событие с завершающим событием сети, — путем, следующим за данным событием;

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

Если известна продолжительность каждой работы t_ij то для каждого пути может быть вычислена его длина (продолжительность) t(L). Длина каждого пути равна сумме продолжительностей составляющих его работ. Дадим формализованную постановку расчета длины пути. Пусть весь комплекс работ уже изображен в виде пронумерованного сетевого графика, и пусть для каждой работы (Р_i, Р_j) задана продолжительность t_ij³0 ее выполнения, которую будем считать длиной этой работы (дуги). Тогда под длиной пути (Р_i, Р_ji), (Р_ji, Р_j2),..., (P_jk, Р_j) из Р_i в Р_j будем понимать продолжительность выполнения всей последовательности работ, составляющих этот путь, т.е. число t_ij1+t_ij2+...+t_ikj.

Счет времени будем вести от наступления начального события Р₀, т.е. время Т₀ наступления события Р₀ будем считать равным нулю. Временем Т_j наступления (свершения) любого события Р_j будем считать время окончания всех работ, входящих в Р_j. Минимальное (т.е. наиболее раннее) время возможного наступления события P_j равно максимальной длине пути из Р₀ в Р_j. Оно же, следовательно, является наиболее ранним временем начала всех работ, выходящих из Р_j. Обозначим это время через Т_j⁽⁰⁾.

Критическим временем проекта назовем минимальное время Т_n⁽⁰⁾ наступления последнего события Р_n. Другими словами, критическое время — это минимальное количество времени, необходимое для выполнения всего комплекса работ.

Критический путь — наиболее продолжительный путь в сетевом графике. Причем критическим путем называют любой путь из Р₀ в Р_n, имеющий максимальную длину.

Алгоритм вычисления минимальных времен и критического времени.

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

Предварительный шаг. Каждому событию Р_j приписываем число l_j=0; однако, в отличие от предыдущего, каждой работе (Р_i, Р_j) ставим теперь в соответствие не число у_ij=1, а число t_ij — продолжительность выполнения этой работы.

Общий шаг. Просматриваем всю пронумерованную сеть последовательно от Р₀ до Р_n, вычисляем новые значения I'_jчисел I_j по формуле (2.3):

(2.3)

и записываем около каждого вычисленного I'_j номера i₁, i₂,..., i_v тех событий Р_i, для которых был достигнут максимум. Эти пометки будут затем использованы при отыскании критического пути. Убедимся, что в рассматриваемом случае пронумерованной сети второй шаг не изменит ни одного из чисел l'_j=l⁽¹⁾_j, полученных после первого шага.

Действительно, так как сеть просматривается в порядке Р₀, P₁,…, Р_i,..., Р_j,..., Р_n, то число l'_j вычисляется лишь после того, как определены все числа l'_i, участвующие в вычислении l'_j (i<j). Далее, поскольку числа t_ij одни и те же на всех шагах, то число l⁽²⁾_j может оказаться больше числа l⁽¹⁾_j лишь тогда, когда l⁽²⁾_j>l⁽¹⁾_j, при некотором i<j. Но l⁽²⁾₀=l⁽¹⁾₀=0, следовательно, l⁽²⁾₁=l⁽¹⁾₁. Но тогда l⁽²⁾₂=l⁽¹⁾₂, и т.д.

Каждое из чисел l'_j (у=1,..., n), полученное после единственного шага, определяет максимальную продолжительность пути из Р₀ в P_j и, по определению, равно минимальному времени T_j⁽⁰⁾ наступления события Р_j. Наконец, число l'_n=T_n⁽⁰⁾ дает критическое время проекта.