Критический путь и его анализ

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

Критический путь - максимальный по продолжительности полный путь в сети (в сетевой модели) называется критическим; работы, лежащие на этом пути, называются критическими работами. Именно длительность критического пути определяет наименьшую общую продолжительность работ по проекту в целом. Как правило, критические работы составляют небольшую часть всех работ сети, но именно они определяют продолжительность выполнения комплекса в целом. Длительность выполнения всего проекта в целом может быть сокращена за счет сокращения длительности задач, лежащих на критическом пути. Соответственно, любая задержка выполнения задач критического пути повлечет увеличение длительности проекта.

Существуют также работы с очень маленькими резервами времени. Они являются субкритическими и на них нужно обращать столько же внимания, сколько и на критические работы.

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

Метод критического пути (КМП) - является основным математическим средством для вычисления ранних и поздних начал и окончаний работ и резервов времени.

Существует два возможных метода, позволяющих отследить движение времени в графе:

1. Определение для каждой операции наиболее ранних сроков начала и окончания ее выполнения.

2. Определение для каждого события наиболее раннего срока его наступления.

Второй метод применим только в случае стрелочных графов.

Анализ критического пути с применением вершинных графов - приводится в виде примера 4.

Пример 4

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

Операции	Непосредственно предшествующая операция	Время, дней
A	-
B	-
C	-
D	A, B
E	B,C
F	C
G	D, E
H	F, G

Операция	Продолжи-тельность, дней	Наиболее ранний срок начала	Наиболее ранний срок окончания	Комментарий
A			0 +8 = 8
B			0 + 10 = 10
C			0 + 6 = 6
D			10 + 8 = 18	Нельзя начать, пока не завершены А и В
E			10 +9 = 19	Нельзя начать, пока не завершены В и С
F			14 + 6 = 20	Нельзя начать, пока не завершена С
G			14 + 19 = 33	Нельзя начать, пока не завершены D и E
H			33 + 6 = 39	Нельзя начать, пока не завершены F и G

.

Дата добавления: 2014-01-04