2. Пример. В таблице записаны работы ( I , j ) и время их выполнения tij ;

i , j	1, 2	1, 3	2, 3	2, 5	3, 4	3, 6	4, 5	4, 6	4, 7	5, 7	6,7
tij	2	8	5	4	7	23	12	4	5	10	8

Начертить сетевой график и найти параметры сетевого графика по событиям и работам.

РЕШЕНИЕ По данным работам i, j строим сетевой график. Событий всего 7, значит рисуем 7 вершин. Надо так расположить вершины, чтобы работы i , j не пересекались.

27

2 4 5 2

2 1 29 10

3

2 12 39

7 0

0 15 39

1 0 5 4 2 5

0 17 8

7 4

8 8

3 0 23 31

8 6 0

t _p 31

N R

t _n

Находим параметры по событиям.

1) Ранний срок наступления события i, t_p ( i ) (ещё одно обозначение − t^j_p).Это максимальный путь от начального события до i - го события:

t_p( 1 ) = 0; t_p( 2 ) = t_1,2 = 2

В третье событие входят 2 работы : (2,3) и (1,3), значит

t_p(3)=max{t_p(2) + t_2,3 ; t_p(1) + t_1,3}=max{2+5, 8}= 8

В четвертое событие входит одна работа (3,4)

t_p(4) = t_p(3)+t_3,4 = 8+7=15

В пятое событие входят 2 работы : (2,5) и (4,5), значит

t_p(5)=max{t_p(2) + t_2,5 ; t_p() + t_4,5}=max{2+4, 15+12}= 27

В шестое событие входят две работы : (4,6) и (3,6), значит

t_p(6)=max{t_p(4) + t ; t_p(3) + t_3,6}= max{15+4, 8+23}= 31

В седьмое событие входят три работы : (5,7); (4,7); (6,8) значит

t_p(7)=max{t_p(5) + t_5,7 ; t_p(4) + t_4,7; t_p(6) + t_6,7}=

max{5+5, 27+10,31+8}= 39

2) Поздний срок наступления события i, t_n ( i ) (ещё одно обозначение − tⁱ_п)— это разность между продолжительностью максимального пути l_max и пути наибольшей продолжительности от данного события i до конечного события.

Рассчитывается t_n ( i ) по обратной схеме t_p ( i ). Значит, расчет начинаем от конечного события, ориентируемся на выходящие работы, берем минимум разности.

Для конечного события

t_n(7) = t_p(7)=39

Из шестого события выходит одна работа : (6,7)

t_n(6) = t_n­­­­­­­_­(7) - t_6,7 = 39 - 8 = 31

Из пятого события выходит одна работа : (5,7)

t_n(5) = t_n­­­­­­­­(7) - t_5,7 = 39 - 10 = 29

Из четвертого события выходит 3 работы : (4,5); (4,6); (4,7)

t_n(4) = min{ t_n­­­­­­­_­(5) - t_4,5 ; t_n­­­­­­­_­(6) - t_4,6 ; t_n­­­­­­­_­(7) - t_4,7 }=

min{29 - 12; 31 - 4; 39 - 5}= 17

Из третьего события выходит 2 работы : (3,4);(3,6)

t_n(3)=min{t_n­­­­­­­_­(4) - t_3,4 ; t_n­­­­­­­_­(6) - t_3,6}=min{17 - 7;31 - 23}= 8

Из второго события выходит 2 работы : (2,5);(2,3)

t_n(2)=min{t_n­­­­­­­_­(5) - t_2,5 ; t_n­­­­­­­_­(3) - t_1,3}=min{8 - 5;29 - 4}= 3

Из начального события выходит 2 работы : (1,2);(1,3)

t_n(1)=min{t_n­­­­­­­_­(2) - t_1,2 ; t_n­­­­­­­_­(3) - t_1,3}=min{3 - 2;8 - 8}= 0

Для начального события должно выполняться условие:

t_p( 1 ) = t_n ( 1 ) = 0 .

3) Находим резерв времени по событиям:

R( i ) = t_n( i ) - t_p( i ).

R(1) = 0; R(2) = 3-2 =1; R(3) = 8-8 = 0;

R(4) = 17-15 = 2; R(5) = 29-27 = 2; R(6) = 31-31 = 0;

R(7) = 39-39 = 0.

4) Критический путь проходит по событиям с нулевым резервом времени R( i ) = 0, т.е. 1, 3, 6, 7, (выделено на графе). Длина критического пути L_кр — это самый длинный путь от начального события до конечного :

L_кр = t_p(7) = 39.

Рассчитаем необходимые параметры по работам.

5) Ранний срок окончания работы ( i , j ) :

t_p.o( i , j )=t_p( i ) + t_i,j

t_p.o(1,2)=t_p(1) + t_1,2 = 0+2 = 2;

t_p.o(1,3)=t_p(1) + t_1,3 = 0+8 = 8;

t_p.o(2,3)=t_p(2) + t_2,3 = 2+5 = 7;

t_p.o(2,5)=t_p(2) + t_2,5 = 2+4 = 6;

t_p.o(3,4)=t_p(3) + t_3,4 = 8+7 = 15;

t_p.o(3,6)=t_p(3) + t_3,6 = 8+23 = 31;

t_p.o(4,5)=t_p(4) + t_4,5 = 15+12 = 27;

t_p.o(4,6)=t_p(4) + t_4,6 = 15+4 = 19;

t_p.o(4,7)=t_p(4) + t_4,7 = 15+5 = 20;

t_p.o(5,7)=t_p(5) + t_5,7 = 27+10 = 37;

t_p.o(6,7)=t_p(6) + t_6,7 = 31+8 = 39;

6) Поздний срок наступления окончания работы ( i , j ):

t_n.o (1,2) = t_n(2) = 3; t_n.o (2,3) = t_n(3) = 8;

t_n.o (1,3) = t_n(3) = 8; t_n.o (2,5) = t_n(5) = 29;

t_n.o (3,4) = t_n(4) = 17; t_n.o (4,5) = t_n(5) = 29;

t_n.o (3,6) = t_n(6) = 31; t_n.o (4,6) = t_n(6) = 31;

t_n.o (5,7) = t_n(7) = 39; t_n.o (4,7) = t_n(7) = 39.

t_n.o (6,7) = t_n(7) = 39;

7) Полный резерв времени работы i , j — это время, на которое можно увеличить продолжительность данной работы, не изменяя при этом продолжительность критического пути L_кр.

R_n( i , j ) = t_n ( j ) - t_p( i ) - - t_i,j;

R_n(1,2) = t_n (2) - t_p(1) - t_1,2 = 3-0-2 = 1;

R_n(1,3) = t_n (3) - t_p(1) - t_1,3 = 8-0-8 = 0;

R_n(2,3) = t_n (3) - t_p(2) - t_2,3 = 8-2-5 = 1;

R_n(2,5) = t_n (5) - t_p(2) - t_2,5 = 8-2-4 = 2;

R_n(3,4) = t_n (4) - t_p(3) - t_3,4 = 17-8-7 = 2;

R_n(3,6) = t_n (6) - t_p(3) - t_3,6 = 31-8-23 = 0;

R_n(4,5) = t_n (5) - t_p(4) - t_4,5 = 29-15-12 = 2;

R_n(4,6) = t_n (6) - t_p(4) - t_4,6 = 31-15-4 = 12;

R_n(5,7) = t_n (7) - t_p(5) - t_5,7 = 39-27-10 = 2;

R_n(6,7) = t_n (7) - t_p(6) - t_6,7 = 39-31-8 = 0;

Работа (4,7) имеет большой резерв времени (12), значит можно с этой работы снять на данном этапе ресурсы и перебросить их на работы лежащие на критическом пути. Аналогично, работы (2,5),(3,4),(4,5),(5,7) имеют резерв времени равный 2 . Работу (2,3) считаем под критической, а работы с нулевым резервом времени — критические. На рисунке критический путь отмечен жирной линией.