Временные параметры сетевых графов

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

Минимальное время выполнения проекта = длине критического пути.

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

Найти критический путь – перебрать все пути и выбрать ТОТ/ТЕ, который имеет наибольшую суммарную продолжительность выполнения работ.

Для реальных проектов возникают сложности перебора.

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

Введем обозначения:

i и j - вершины или события проекта,

(i, j) - работа проекта,

s - событие «начало проекта»,

f - событие «окончание проекта»,

T - длина критического пути,

t(i,j) - время выполнения работы (i,j),

ES(i,j)- наиболее раннее время начала работы (i,j),

EF(i,j)- наиболее раннее время окончания работы (i,j),

LS(i,j) - наиболее позднее время начала работы (i,j),

LF(i,j) -наиболее позднее время окончания работы (i,j),

Ei - наиболее раннее время наступления события i,

Li - наиболее позднее время наступления события i,

R(i,j) – полный резерв времени работы (i,j),

r(i,j) – свободный резерв времени работы (i,j),

Если (i,j) - работа проекта, то имеет место соотношения:

ES(i,j) = E i для любого j

LS(i,j) = Li для любого i

Для того, чтобы использовать метод CPM (метод критического пути) для нахождения критического пути, необходимо для каждой работы (i,j) определить величины:

наиболее раннее время начала работы (i,j)- ES(i,j)

наиболее раннее время окончания работы (i,j)- EF(i,j)

наиболее позднее время начала работы (i,j) - LS(i,j)

наиболее позднее время окончания работы (i,j)- LF(i,j)

Метод СРМ описывается следующими соотношениями:

1. ES(s,j) = 0 для любой работы (s,j), выходящей из стартовой вершины проекта

2. EF(i,j) = ES(i,j) + t(i,j) = Ei + t(i,j):

наиболее раннее время окончания работы (i,j) превышает наиболее раннее время начала этой работы (время наступления предшествующего события i) на время ее выполнения.

3. ES(q,j) = max(i) EF(i,q) = Eq:

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

4. T = Ef = max(i) EF(i, j):

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

5. LF(i,f) = T

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

6. LS(i,j) = LF(i,j) - t(i,j) = Lj - t(i,j)

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

7. LF(i,q) = min(j) LS(q,j) = Lq

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

8. R(i,j) = LS(i,j) - ES(i,j) = LF(i,j) - EF(i,j) = L j - t(i,j) - L i

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

9. r(i,j)= L j - ES(i,j) - t(i,j) = L i =

= L j - EF(i,j) = L j – Ei - t(i,j)

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

Из приведенных выше определений и соотношений непосредственно следует:

1. Длина критического пути равна Т.

2. Если R (i,j) = 0, то работа (i,j) лежит на критическом пути;

если R (i,j) > 0, то работа (i,j) не лежит на критическом пути.

3. Если время начала работы (i,j), которая не лежит на критическом пути, отложит на срок меньший, чем r(i,j), то наиболее раннее время наступления последующего события не изменится.

4. Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем R (i,j), то время, необходимое на выполнение всего проекта, не увеличивается.