5.3. Задача сетевого планирования

Построить сетевую модель и произвести расчет ее временных параметров методом сетевого планирования на основе заданной структурной таблицы комплекса работ. Для этого необходимо

• построить предварительный сетевой график, упорядочить номера событий,

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

• вычислить характеристики работ, представить их в виде таблицы,

• построить линейную карту сети по ранним и поздним срокам свершения событий.

Метод решения задачи рассмотрен в [5] и [7].

Пример. Информация о проекте задана в виде табл.4.

Таблица 4

Структурная таблица комплекса работ

Работа	Опирается на работы	Продолжи-тельность Работы	Работа	Опирается на работы	Продолжи-тельность Работы
a1	-	3	a8	a3	1
a2	-	1	a9	a4,a5,a7	1
a3	a1	2	a10	a4,a5,a7	3
a4	a1	4	a11	a6,a9	1
a5	a2	3	a12	a6,a9	5
a6	a2	2	a13	a8,a10,a11	2
a7	a3	1

Решение. Сетевая модель комплекса работ представляется сетевым графиком, изображенным на рис.5.

Рис.5. Предварительный сетевой график комплекса работ

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

Минимальное время, необходимое для выполнения всего комплекса работ, называется критическим временем (t_кр).

Рассмотрим любой полный путь сетевого графика, то есть путь от исходного события до завершающего. Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути. Обычно на сети существует несколько полных путей различной продолжительности. Критическое время равно продолжительности самого длительного по времени полного пути. Такой путь называется критическим (L_кр). Таким образом, полный путь сетевого графика, имеющий наибольшую длину, является критическим. В сети может быть несколько критических путей, имеющих одинаковую длину. Критический путь имеет особое значение в системе сетевого планирования, так как работы этого пути определяют общий цикл завершения всего комплекса работ.

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

Для исходного события принимают, что его ранний срок свершения равен нулю: t_р(0)=0. Ранний срок свершения события j может быть подсчитан по рекуррентной формуле:

t_р(j)=max(t_р(i)+t_ij),

где максимум распространяется на все события i, непосредственно предшествующие событию j. Определение ранних сроков свершения событий следует вести последовательно от исходного события к завершающему. При этом около каждого вычисленного значения t_р(j) записывается номер того из предшествующих событий, для которого в рекуррентной формуле достигается максимум. Эти помеченные события служат для отыскания критического пути, а именно, двигаясь по ним от завершающего события к исходному, будет построен критический путь. Критическое время t_кр равно раннему сроку свершения завершающего события.

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

t_п(i)=min(t_п(j)-t_ij),

где минимум распространяется на все события j, непосредственно следующие за событием i. Определение поздних сроков свершения событий следует вести последовательно от завершающего события к исходному. При правильном расчете для исходного события получим t_р(0)=t_п(0)=0.

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

При работе с сетевым графиком вручную, если количество событий невелико, вычисления удобно проводить прямо на графе. Для этого каждый кружок, обозначающий событие, делят на четыре сектора. Верхний сектор отводится для записи номера события i, левый - для вычисляемого раннего срока свершения события t_р(i), нижний - для номера помеченного события, правый - для вычисляемого позднего срока свершения события t_п(i).

Вычисленные значения временных параметров событий проставлены в соответствующих секторах сетевого графика (рис.6). Критическое время выполнения комплекса работ равно t_кр=t_р(7)=13. Критический путь проходит через события с номерами: 0, 1, 4, 5, 7.

Рис.6. Сетевой график с указанием ранних и поздних

сроков свершения событий

Основными характеристиками работ сетевого графика являются моменты их начала и окончания, а также резервы времени.

Ранний срок начала работы равен раннему сроку свершения ее начального события: t_р.н(i,j)= t_р(i). Ранний срок окончания работы равен раннему сроку начала работы, сложенному с ее продолжительностью: t_р.о(i,j)= t_р(i)+t_ij.

Поздний срок окончания работы равен позднему сроку свершения ее конечного события: t_п.о(i,j)= t_п(j). Поздний срок начала работы равен позднему сроку ее окончания за вычетом продолжительности работы: t_п.н(i,j)= t_п(j)-t_ij. Полный резерв времени работы - это максимальное количество времени, на которое можно задержать начало работы или увеличить продолжительность ее выполнения, не изменяя срока завершения всего комплекса работ: R_п(i,j)=t_п(j)-t_р.о(i,j)=t_п(j)-t_р(i)-t_ij. Полный резерв времени у критических работ равен нулю. Некритические работы обладают ненулевым полным резервом.

Свободный резерв времени работы - это максимальное количество времени, на которое можно задержать начало работы или увеличить продолжительность ее выполнения при условии, что она начинается в свой ранний срок, не изменяя при этом ранних сроков начала последующих работ: R_с(i,j)=t_р(j)-t_р.о(i,j)=t_р(j)-t_р(i)-t_ij. Характеристики работ для сетевого графика, изображенного на рис.6, сведены в табл.5.

Таблица 5

Временные характеристики работ

Шифр работы	Продолжи-тельность	Срок начала работы		Срок окончания работы		Резерв времени работы
	работы	ранний	поздний	Ранний	поздний	полный	свободный
(0,1)	3	0	0	3	3	0	0
(0,2)	1	0	3	1	4	3	0
(1,3)	2	3	4	5	6	1	0
(1,4)	4	3	3	7	7	0	0
(2,4)	3	1	4	4	7	3	3
(2,5)	2	1	6	3	8	5	5
(3,4)	1	5	6	6	7	1	1
(3,6)	1	5	10	6	11	5	4
(4,5)	1	7	7	8	8	0	0
(4,6)	3	7	8	10	11	1	0
(5,6)	1	8	10	9	11	2	1
(5,7)	5	8	8	13	13	0	0
(6,7)	2	10	11	12	13	1	1

На основе табл.5 строится линейная карта сети (рис.7).

Р ис.7. Линейная карта сети

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

Карта сети может быть построена в среде Microsoft Excel. С этой целью в столбцы A, B, C и D заносится содержимое первой, третьей, второй и седьмой колонок табл.5 соответственно. Затем выделяется блок данных столбцов B, C, D и производится обращение к мастеру диаграмм. Выбирается линейчатая диаграмма с накоплением. В пункте меню "Ряд" в графе "Подписи оси X:" заносится диапазон ячеек с данными столбца A. Затем указываются заголовки осей координат и заполняется легенда, как показано на рис.7.