Лабораторная работа 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кр = L5 — (0,1,3,4,5,6, 7). Длина Lкр = 12 (единицам времени).
3. Определение наиболее позднего возможного времени. Критический путь определяет общую продолжительность работ по созданию объекта, для которого составлен сетевой график. Чтобы сократить срок создания объекта нужно сократить время выполнения работ на критическом пути.
Возникает вопрос о резервах времени выполнения работ. Наличие таких резервов позволяет перераспределить силы для выполнения параллельных работ.
Для определения резервов времени предварительно вычисляется наиболее позднее возможное время начала выполнения каждого события, не изменяющее сроки выполнения всей разработки. Эти величины обозначим tn(j) (" n " — позднее). Для их определения предварительно рассчитываются величины t’n(j) — длина наибольшего пути от события j до конца разработки. Величины t’n(j) определяются от последнего события по алгоритму:
Для данного примера имеем:
Величины tn(j) определяются из соотношения:
Имеем: tn(0)=12-12=0; tn(1)=1; tn(2)=4;tn(3)=7; tn(4)=8; tn(5)=9; tn(6)=11; tn(7)=12.
4. Определение полного резерва времени.
Для работы (i, j) полный резерв времени Rn(i,j) определяется зависимостью:
и определяют насколько может быть затянуто выполнение работы (i,j) без удлинения сроков выполнения проекта.
Имеем:
Для работ критического пути . Использование одного из полных резервов работ может влиять на величину другого.
Так . Но если использовать резерв , то величина станет равной 4.
5. Свободный резерв времени.
Если для работы (i, j) выполняется условие: , то работа обладает свободным резервом времени . Использование величины не влияет на величину резервов времени остальных работ сети.
Задание. Произвести расчет и анализ показателей сетевого графика.