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

Рис. 6. Введение фиктивной работы.

 

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

В сетевом графике не должно быть:

- «висячих» событий (т.е. не имеющих предшествующих событий), кроме исходного;

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

- циклов

 

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

 

Таблица 11. Исходные данные для задачи сетевого планирования.

 

Работа	Содержание работы	Непосредственно предшествующая работа	Время выполнения работы, нед.
A	Подготовить конструкторский проект	-
B	Разработать маркетинговый план	-	1,5
C	Подготовить описание технологического процесса	A
D	Построить прототип	A
E	Подготовить рекламную брошюру	A
F	Подготовить оценки затрат	C
G	Провести предварительно тестирование	D
H	Выполнить исследование рынка	B, E	3.5
I	Подготовить доклад о ценах	H
J	Подготовить заключительный доклад	F, G, I

 

Рис. 5. Сетевой граф (график)

 

Путь – последовательность взаимосвязанных работ, ведущая из одной вершины проекта в другую вершину. Например, на нашем сетевом графике, {A, C, F} и {B, H, I} — два различных пути.

Длина пути – суммарная продолжительность выполнения всех работ пути.

Полный путь – это путь от исходного к завершающему событию. Например: 1, 3, 6, 7, 8.

Критический путь – полный путь, суммарная продолжительность выполнения всех работ которого является наибольшей.

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

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

Метод критического пути (CPM — Critical Path Method) позволяет получить критический путь намного проще.

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

Tp(i) — ранний срок наступления события i, минимально необходимый для выполнения всех работ, которые предшествуют событию i;

Tn (i) — поздний срок наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети;

R(i)= Tn(i)- Tp(i) — резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения.

Рис. 8. Оформление вершины в сетевом графике.

 

Ранние сроки наступления событий рассчитываются от исходного S к завершающему F по алгоритму

1) для исходного события S: ;

2) для остальных событий, вершин i: , где максимум берется по всем работам (k,i), входящим в событие i; t(k,i) – длительность работы (k,i)

 

Рис. 9. Определение ранних сроков наступления события.

 

Рис. 10. Ранние сроки окончания работ после расчета наносят на граф.

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

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

 

1) для завершающего события F: ;

2) для остальных событий, вершин i: , где миниимум берется по всем работам (i,j), выходящим из события i; t(i,j) – длительность работы (i,j)

Рис. 11. Определение поздних сроков наступления события.

 

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

Условия критического пути:

Необходимое – резервы событий, лежащих на критическом пути нулевые R(i)=0

Достаточное – полные резервы работ на критическом пути нулевые .

Полный резерв работ по формуле показывает максимальное время, на которое можно увеличить длительность работы t(i, j)или отсрочить ее начало без нарушения плановых сроков

 

 

Рис. 13 Резервы времени на сетевом графе