Расчет и анализ параметров сетевого графика

Лабораторная работа 7

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

Представление проекта в виде сети называется сетевым графиком. Ориентированные дуги представляют работы. Вершины (события) пред­ставляют последовательность выполнения работ. В сетевом графике должно быть одно начальное и одно конечное событие.

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

Пример.

Данный график задает 10 работ: (0,1),(1,2),(1,3),... и 8 событий, свя­занных с началом и завершением работ. Числа у дуг означают продол­жительность перехода от одного события к другому.

1. Расчет наиболее раннего возможного времени наступления каждого события

«p »— раннее

Формула:

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

Для нашего графика:

(*)

Таким образом установлено время начала каждой работы при соблю­дении плановых сроков и время выполнения всех работ — 12 единиц вре­мени (например, месяцев).

2. Определение критического пути.

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

Путь, для которого начало совпадает с исходным событием, а ко­нец с завершающим, называется полным путем. Указанный путь име­ет 5 полных путей: , , , , . Длиной пути называется сумма продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называется критическим путем. Поиск критического пути ведется от последнего события сети. В качестве собы­тия, предшествующего событию с номером j в критическом пути прини­мается событие с номером k, для которого

Эти номера k выбираем, начиная с последней строки формул (*): 7,6,5,4,3,1,0.

Таким образом, в нашем примере критический путь L_кр = L₅ — (0,1,3,4,5,6, 7). Длина L_кр = 12 (единицам времени).

3. Определение наиболее позднего возможного времени. Критический путь определяет общую продолжительность работ по созданию объекта, для которого составлен сетевой график. Чтобы сокра­тить срок создания объекта нужно сократить время выполнения работ на критическом пути.

Возникает вопрос о резервах времени выполнения работ. Наличие таких резервов позволяет перераспределить силы для выполнения парал­лельных работ.

Для определения резервов времени предварительно вычисляется наи­более позднее возможное время начала выполнения каждого события, не изменяющее сроки выполнения всей разработки. Эти величины обозначим t_n(j) (" n " — позднее). Для их определения предварительно рассчи­тываются величины t^’_n(j) — длина наибольшего пути от события j до конца разработки. Величины t^’_n(j) определяются от последнего события по алгоритму:

Для данного примера имеем:

Величины t_n(j) определяются из соотношения:

Имеем: t_n(0)=12-12=0; t_n(1)=1; t_n(2)=4;t_n(3)=7; t_n(4)=8; t_n(5)=9; t_n(6)=11; t_n(7)=12.

4. Определение полного резерва времени.

Для работы (i, j) полный резерв времени R_n(i,j) определяется зави­симостью:

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

Имеем:

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

Так . Но если использовать резерв , то величина станет равной 4.

5. Свободный резерв времени.

Если для работы (i, j) выполняется условие: , то работа обладает свободным резервом времени . Использование величины не влияет на величину резервов вре­мени остальных работ сети.

Задание. Произвести расчет и анализ показателей сетевого графика.