Правила построения сетевых графиков

1. Завершающее событие лишь одно.

2. Исходное событие лишь одно.

3. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой. Если два события связаны более чем одной работой, рекомендуется ввести дополнительное событие и фиктивную работу:

ТО)

В

4. В сети не должно быть замкнутых циклов.

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

Например, для начала работы D достаточно окончания рабо­ты А. Для начала же работы С нужно окончание работ А и В.

• 35.3. МЕТОД КРИТИЧЕСКОГО ПУТИ

Метод критического пути (Сгitiсаl Раth Меthod — СРМ) используется для управления проектами с фиксированным временем вы­полнения работ. Он позволяет ответить на следующие вопросы:

1. Сколько времени потребуется на выполнение всего проекта?

2. В какое время должны начинаться и заканчиваться отдельные работы?

3. Какие работы являются критическими и должны быть выпол­нены в точно определенное графиком время, чтобы не сорвать уста­новленные сроки выполнения проекта в целом?

4. На какое время можно отложить выполнение некритических работ, чтобы они не повлияли на сроки выполнения проекта?

Самый продолжительный путь сетевого графика от исходного со­бытия к завершающему называется критическим. Все события и рабо­ты критического пути также называются критическими. Продолжи­тельность критического пути и определяет срок выполнения проекта. Критических путей на сетевом графике может быть несколько.

Рассмотрим основные временные параметры сетевых графиков.

Обозначим t(i, j) — продолжительность работы с начальным событием i и конечным событием j

Ранний срок t_Р(j) свершения события j — это самый ранний момент, к которому завершаются все работы, предшествующие этому событию. Правило вычисления:

(t_Р(j) = mах { t_Р(i) + t(i,j) },

где максимум берется по всем событиям i, непосредственно предшествующим событию j (соединены стрелками).

Поздний срок t_n(i) свершения события i— это такой предельный момент, после которого остается ровно столько времени, сколько необходимо для выполнения всех работ, следующих за этим событием/ Правило вычисления:

t_n(i) = min { t_n(j) - t_n(I,j) },

где минимум берется по всем событиям j, непосредственно следующим за событием i.

Резерв R(i) события I показывает, на какой предельно допустимый срок может задержаться свершение события i без нарушения срока наступления завершающего события:

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

Критические события резервов не имеют.

При расчетах сетевого графика каждый круг, изображающий событие, делим диаметрами на четыре сектора:

Пример 15. Рассмотрим сеть проекта, представленную следую­щими данными. Найти критический путь. Сколько времени потребуется для завершения проекта? Можно ли отложить выполнение рабо-

ты D без отсрочки завершения проекта в целом? На сколько недель можно отложить выполнение работы С без отсрочки завершения проекта в целом?

Работа	Непосредственный предшественник	Продолжительность работы, нед.
А	—
В.	—
С	A
D	А
Е	В
F	D,Е
G '	D,Е
Н	С,F

Рисуем сетевой график.

I этап. При вычислении (_р(1) перемещаемся по сетевому графику от исходного события 1 к завершающему событию б.

>,(!) = 0.

В событие 2 входит только одна работа: (_р(2) = 1^(1) + /(1, 2) = = 0 + 5 = 5.

Аналогично /,(3) = К,(1) + 1(1, 3) = 0 + 3 = 3.

В событие 4 входят две работы =>

Г,(4) - тах {/,(2) + 1(2, 4), ГДЗ) + 1(3, 4)} - тах {5 + 6, 3 + 7} = 11.

1„(5) = тах {1_р(2) +»<2, 5), Г,(4) + «4, 5)} = тах {5 + 7,11 -Н 3} = 14.

Г/6) = тах (1_р(4) + /(4,6), /Д5) + 1(5, 6)} = тах {11 + 10,14 + 8} = 22

=> I критическое = 22.

II этап. При вычислении 1_п(1) перемещаемся от завершающего со­бытия 6 к исходному событию 1 по сетевому графику против стрелок.

Далее рассматриваем непосредственно предшествующее событие 5, из которого выходит только одна работа (5, 6):

',(5) = /„(6)- 1(5, 6) = 22- 8 =14.

Из события 4 выходят две работы: (4, 5) и (4, 6). Поэтому опреде­ляем /„(4) по каждой из этих работ:

/,(4) = пил {(„(5) - 1(4, 5), /„(6) - 44, 6)} = птг {14 - 3, 22 - 10} = = тт{11, 12} = 11.

Г„(2) = тт {/„(5) - К2, 5), 1„(4) - 1(2, 4)} = тт {14 - 7, 11 - 6} = = тт{7₎5} = 5.

/„(1) = тт {/„(2) - {(I, 2), Г„(3) - <1, 3)} = тт {5 - 5, 4 - 3} = = тт {0, 1} = 0.

Шэтап. Вычисляем К(1) = („(() - /,(/) — резерв времени собы­тия /, то есть из чисел, полученных на этапе II, вычитаем числа, по­лученные на этапе I.

ТУ этап. У критических событий резерв времени равен нулю, так как ранние и поздние сроки их свершения совпадают. Критические события 1,2,4,5, 6 и определяют критический путь 1—2-4-5-6, ко­торый на сетевом графике мы покажем двумя чертами. Теперь можно ответить на вопросы задачи.

Для завершения проекта потребуется 22 недели. Работа О = (2, 4) расположена на критическом пути. Поэтому ее нельзя отложить без отсрочки завершения проекта в целом. Работа С- (2,5) не расположе­на на критическом пути, ее можно задержать на /„(5) - 1_Р(2) -1(2, 5) = = 14-5- 7 = 2(недели).

Задача 15. Проект пусконаладки компьютерной системы состо­ит из восьми работ.

Работа	Непосредственный предшественник	Продолжительность работы, нед.
А	—
В	—	6
С	А	2
D	В, С	5
Е	D
F	Е
G	В, С
Н	F,G

Найти критический путь. Сколько времени потребуется для завер­шения проекта? Можно ли отложить выполнение работы С без от­срочки завершения проекта в целом? На сколько недель можно отло­жить выполнение работы Р без отсрочки завершения проекта в целом?