ЗАДАНИЕ 7

Решить задачу по теме «Сетевое планирование». Для заданной сетевой модели некоторого комплекса работ определить время и критический путь.

Решение:

Коды работ	Длительность работ (дни)
1-2
2-3
3-8
1-4
4-6
4-7
6-7
7-8
1-5
5-8
2-4
5-6

 

 

Рассмотрим прямой ход. Пусть Tj означает минимальное время окончания всех работ, конец которых изображается вершиной с номером j. Очевидно, T₁ =0, далее последовательно находим

^Tj = ^{max (T}i + j ^j = ^2,N^,

где i - номер вершин сетевого графика, из которых выходят векторы, входящие в вершину с номером j; t_ij - длительность работ с началом в вершине i и концом в вершине j, N - количество вершин сетевого графика. При j=N получаем минимальное время графика T^=T_N.Tj являются ранними сроками начала (окончания) работ, конец (начало) которых изображается вершиной j. Итак,

T^p = 0,

T2 = max(Ti^p + t₁₂) = 7,

T₃^p = max(T₂^p + 1 ₂₃) = 8,

T₄^p = max(T^p + 1₁₄, T^p + 1 ₂₄) = max(8,7) = 8,

T₅^p = max(T₁ ^p +1₁₅) = 4,

T₆^p = max(T₅^p + 1 ₅₆, T₄^p + 1 ₄₆) = max(4,16) = 16,

T₇^p = max(T₄^p + 1 ₄₇, T₆^p +1 ₆₇) = max(17,21) = 21,

T₈^p = max(T₃^p + 1 ₃₈, T₇^p +1 ₇₈, T₅^p +1 ₅₈) = max(12,24,16) = 24.

Тогда Ткр = 24 - минимальное время графика.

Рассмотрим обратный ход. Пусть T_iⁿ означает наибольшее время окончания всех работ, входящих в вершину i, Ткр=Т^.

Ti = min (Tjⁿ - -_ц), i = N2,

где j - номер вершины, к которой направлены векторы, выходящие из вершины с номером i.

T₈ⁿ = 24,

^T7 = min(^T₈ⁿ - 1 ₇₈) = ²1,

^T6 = ^min(T7^{n - t} ₆7⁾ = ^16,

T₅ⁿ = min(T₈ⁿ -1₅₈, T₆ⁿ - t_S6) = min(12,16) = 12,

T₄ⁿ = min(T₇ⁿ - 1 ₄₇, T₆ⁿ -1 ₄₆) = min(12,8) = 8,

T₃ⁿ = min(T₈ⁿ -1₃₈) = 20,

T₂ⁿ = min(T₃ⁿ - 1 ₂₃, T₄ⁿ -1₂₄) = min(19,8) = 8,

T"; = min(T₂ⁿ -1₁₂, T₄ⁿ -1₁₄, T₅ⁿ -1₁₅) = min(1,0,8) = 0.

T_iⁿ - поздние сроки начала (окончания) работ, начало которых изображается вершиной i.

Для определения критического пути составим таблицу.

 

Работа	Продолжит.	Ранние сроки	Поздние сроки	Полный Резерв	Свободн. Резерв
(ij)	tii	Tip	Tip	Tin	Tin	Rii	rii
1,2
2,3
3,8
1,4
4,6
4,7
6,7
7,8
1,5
5,8
2,4
5,6

 

Здесь R_H = Tn -? -1.., r= Tf - T^p - t _H, - полный и свободный резерв. Критический путь сетевого графика составляют работы, для которых R _ij =r _ij Получаем путь (1,4)-(4,6)-(6,7)-(7,8), время - 24 дня.