Критический путь и его анализ
В каждом графе существует несколько возможных путей. Общее время, необходимое для того, чтобы пройти какой-либо путь, есть сумма выполнения всех операций, принадлежащих данному пути. Продолжительность выполнения всего проекта занимает наибольшее время. Более длительные операции называются критическими.
Критический путь - максимальный по продолжительности полный путь в сети (в сетевой модели) называется критическим; работы, лежащие на этом пути, называются критическими работами. Именно длительность критического пути определяет наименьшую общую продолжительность работ по проекту в целом. Как правило, критические работы составляют небольшую часть всех работ сети, но именно они определяют продолжительность выполнения комплекса в целом. Длительность выполнения всего проекта в целом может быть сокращена за счет сокращения длительности задач, лежащих на критическом пути. Соответственно, любая задержка выполнения задач критического пути повлечет увеличение длительности проекта.
Существуют также работы с очень маленькими резервами времени. Они являются субкритическими и на них нужно обращать столько же внимания, сколько и на критические работы.
В каждом графе найдется по крайней мере один критический путь. Для того, чтобы найти общую продолжительность выполнения проекта, нужно определить продолжительность критического пути. В большинстве графов идентифицировать все идущие сквозь граф пути, чтобы выявить среди них тот, который занимает наибольшее время, достаточно трудно.
Метод критического пути (КМП)- является основным математическим средством для вычисления ранних и поздних начал и окончаний работ и резервов времени.
Существует два возможных метода, позволяющих отследить движение времени в графе:
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 |
.