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

1. В сетевой модели: не должно быть «тупиковых» событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события; каждое событие имеет связь хотя с двумя работами (входящая и выходящая); Исходное (начальное) событие лишь одно, которое имеет только исходящие работы.

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

Рис. 11.2

3. В сети не должно быть замкнутых циклов (на рис 11.3 показан пример замкнутого цикла).

Рис. 11.3

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

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

Рис. 11.4

5. События должны быть правильно пронумерованы, т.е. для каждой работы (i, j) i < j. При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:

а) нумерация событий начинается с исходного события, которому приписывается № 1;

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

в) затем вычеркивают работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, ему присваивают № 3, так продолжают до завершающего события, номер которого должен быть равен количеству событий в сетевом графике;

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

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

Следует различать два вида пути:

1. путем (L) называется непрерывная последовательность выполнения работ от исходного до завершающего события. Продолжительность пути (t) определяется суммой продолжительностей составляющих его работ;

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

2. Временные параметры сетей. Резервы времени

Основными временными параметрами сетей являются ранние и поздние сроки наступления событий. Зная их, можно вычислить остальные параметры сети – сроки начала и окончания работ и резервы времени событий и работ.

Обозначим – продолжительность работы с начальным событием i и конечным событием j.

Ранний срок наступления события j определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем , а где N – номер завершающего события. Правило вычисления:

,

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

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

,

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

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

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

.

События лежащие на критическом пути (критические события) резервов не имеют.

Существуют различные методы расчета параметров сети: табличный и графический.

Рассмотрим графический метод.

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

Рис. 11.5

Пример. Рассмотрим проект с работами, представленными в табл. 11.11.

Таблица 11.11

№ пп	Работа	Предшествующие работы	Продолжительность, час
1	А	-	5
2	В	-	3
3	С	A	7
4	D	A	6
5	E	B	7
6	F	D, E	3
7	G	D, E	10
8	H	C, F	8

Построить сетевой график, найти резервы событий, работ, критический путь. Сколько времени потребуется для завершения проекта? Можно ли отложить выполнение роботы D без отсрочки завершения проекта в целом? На сколько недель можно отложить выполнение работы C без отсрочки завершения проекта в целом?

Решение

Построим сетевой график (рис. 11.6).

Рис. 11.6

На графике события представлены кругами, а работы – стрелками. Работа может обозначаться либо буквой, надписанной на графике рядом с соответствующей работе стрелкой, либо номером события, из которого начинается и заканчивается работа.

1-й этап. При вычислении раннего срока наступления события перемещаемся от исходного события 1 к завершающему событию 6.

.

В событие 2 входит только одна работа: .

Аналогично .

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

.

.

.

Отсюда следует, что критическое время выполнения проекта t = 22.

Внесем соответствующие данные в сетевой график (рис. 11.7).

Рис. 11.7

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

.

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

.

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

.

.

.

Внесем полученные данные в сетевой график (рис. 11.8).

Рис. 11.8

3-й этап. Вычисляем резерв события i , т.е. из чисел, полученных на этапе 2, вычитаем числа, полученные на этапе 1 (рис 11.9).

Рис. 11.9

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

Рис. 11.10

Теперь можно ответить на вопросы задачи.

Для завершения проекта потребуется 22 недели. Работа D расположена на критическом пути, поэтому ее нельзя отложить без отсрочки завершения проекта в целом. Работа C не расположена на критическом пути, ее можно задержать на (недели).