§3.3 Временные параметры сетевых графиков и их оптимизация. Расчет временных параметров сетевого графика.
Основным временным параметром сетевого графика является продолжительность критического пути. Расчет критического пути состоит из двух этапов. Можно выделить:
- Прямой проход. Вычисление начинают с исходного события и продолжают до тех пор, пока не будет достигнуто завершающее событие. Для каждого события вычисляется одно число, соответствующее раннему сроку наступления этого события;
- Обратный проход. Вычисления начинают с завершающего события и рподлжают, пока не будет достигнуто исходное событие. Для каждого события вычисляется поздний срок его настуления.
Рассмотрим прямой проход.
Введем обозначения:
- ранний срок начала всех работ, следующих за событием i;
- ранний срок начала всех работ, предшествующих событию j;
- продолжительность работы (i,j);
;
- ранний срок окончания работы;
- поздний срок окончания всех работ, предшествующих событию i;
- поздний срок начала работ;
n – завершающее событие сети;
для всех (i,j).
Пример.
Определим ранние сроки начала всех работ из предыдущего примера.
;
;
;
;
;
.
Найдем ранние сроки окончания работ. Этот срок является наиболее ранним (минимальным) из возможных моментов окончания работы при заданной продолжительности работ, т.е. 
. Поэтому
;
;
;
;
=5;
;
;
;
;
;
Расчитаем обратный проход.
Если i=n, то
и является отправной точкой обратного прохода. Т.о. 
для всех работ (i,j)и поэтому 
;
;
;
;
;
Вычислим поздние сроки начала работ. Эти сроки являются наиболее поздними (максимальными) из допустимых моментов начала данной работы, при которых еще возможно выполнение всех последующих работ в установленный срок, т.е. 
. Следовательно,
;
;
;
;
;
;
;
;
;
;
Все расчеты запишем в таблицу.
| Ра-бота (i,j) | Продолжительность | Ранее | Позднее | Полн-ый резерв | Сво-бодный резерв | ||
| начало | окончание | начало | Оконча-ние | ||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| (0,1) (0,2) (1,3) (2,3) (2,4) (3,5) (4,5) (3,6) (4,6) (5,6) | 2 3 2 3 2 3 7 2 5 6 | 0 0 2 3 3 6 5 6 5 12 | 2 3 4 6 5 9 12 8 10 18 | 5 0 7 6 3 9 5 16 13 12 | 7 3 9 9 5 12 12 18 18 18 | 5 0 5 3 0 3 0 10 8 0 | 0 0 2 0 1 4 0 11 8 0 |
Существует два вида резерва времени: полный резерв (
) и свободный резерв 
.
. Результаты вычислений: 
;
;
;
;
;
;
;
;
;
.
Свободный резерв времени – максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы, при условии, что все события наступают в ранние сроки: 
. вычислим свободные резурвы для всех работ:
;
;
;
;
;
;
;
;
.
Следует отметить, что критические работы имеют нулевой полный резерв времени, при этом свободный резерв также должен быть равен нулю.
Используя результаты вычислений при прямом и обратном проходах, можно определить работы критического пути. Работа (i,j)принадлежит критическому пути. Если для нее выполняются условия
, 
, 
.
В рассматриваемом примере критический путь включает в себя работы (0,2), (2,4), (4,5), (5,6) с общим временем выполнения работ 18 недель.
При небольшом числе работ критические операции могут быть найдены перебором возможных путей.