Метод критического пути

Метод критического пути ис­пользуется для управления технологическим процессом с фиксированным временем выполнения работ.

Метод позволяет выяснить:

1. Сколько времени потребуется на выполнение всего технологического процесса?

2. В какое время должны начинаться и заканчиваться отдельные работы?

3. Какие работы являются критическими и должны быть выполнены в точно определенное графиком время, чтобы не сорвать установленные сроки технологического процесса в целом?

4. На какое время можно отложить выполнение некри­тических работ, чтобы они не повлияли на сроки технологического процесса?

Основные временные параметры сетевых графиков и их расчет.

Обозначение t(i, j) – продолжительность работы с на­чальным событием i и конечным событием j.

Ранний срок t_p(j) свершения события j – это самый ранний момент, к которому завершаются все работы, пред­шествующие этому событию.

Правило вычисления: t_p(j) = max {t_p(i) + t(i, j)}, где максимум берется по всем событиям i, непосредствен­но предшествующим событию j.

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

Правило вычисления: t_п(i) = min {t_п(j) – t(i, j)}, где минимум берется по всем событиям j, непосредственно следующим за событием i.

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

Правило вычисления: R(i) = t_п(i) – t_p(j).

Критические события резервов не имеют.

Полный резерв времени работы R^{i → j}_п между событиями (i, j) определяет время, на которое можно отложить выполнение некритических работ.

Правило вычисления: R^{i → j}_п = t_п(j) – t_р(i) – t(i, j).

Пример расчета сетевого графа.

Определить:

1. сколько времени потребуется на выполнение всего технологического процесса?

2. какие работы являются критическими?

3. на какое время можно отложить выполнение некритических работ?

Решение

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

1. Определение раннего срока свершения события t_р(j)

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

Расчетная формула: t_р(j) = max {t_р(i) + t_р(i, j)}

t_р(0) = 0

t_р(1) = t_р(0) + t_р(0,1) = 0 + 4 = 4

t_р(2) = t_р(1) + t_р(1,2) = 4 + 3 = 7

t_р(3) = t_р(1) + t_р(1,3) = 4 + 5 = 9

t_р(4) = max {t_р(2) + t_р(2,4); t_р(3) + t_р(3,4)} = max {7+ 9; 9 + 6} = max {16; 15} = 16

t_р(5) = t_р(2) + t_р(2,5) = 7 + 2 = 9

t_р(6) = t_р(3) + t_р(3,6) = 9 + 8 = 17

t_р(7) = max {t_р(5) + t_р(5,7); t_р(4) + t_р(4,7); t_р(6) + t_р(6,7) } =

= max {9 + 1; 16 + 10; 17 + 3} = max {10; 26; 20} = 26

2. Определение позднего срока свершения события tп(I)

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

Расчетная формула: t_п(j) = min {t_п(i) – t_п(i, j)}

t_п(7) = t_р(7) = 26

t_п(6) = t_п(7) – t_п(6,7) = 26 – 3 = 23

t_п(5) = t_п(7) – t_п(5,7) = 26 – 1 = 25

t_п(4) = t_п(7) – t_п(4,7) = 26 – 10 = 16

t_п(3) = min {t_п(4) – t_п(3,4); t_п(6) – t_п(3,6)} = min {16 – 6; 23 – 8} = min {10; 15} = 10

t_п(2) = min {t_п(5) – t_п(2,5); t_п(4) – t_п(2,4)} = min {25 – 2; 16 – 9} = min {23; 7} = 7

t_п(1) = min {t_п(2) – t_п(1,2); t_п(3) – t_п(1,3)} = min {7 – 3; 10 – 5} = min {4; 5} = 4

t_п(0) = t_п(1) – t_п(0,1) = 4 – 4 = 0

Проверка: