Почему вес критического пути обеспечивает нижнюю границу общего времени выполнения всех работ?

Во Введении в алгоритмы P657, 3-е издание, говорится:

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

Я понимаю первое предложение. Но во втором предложении говорится

критический путь обеспечивает нижнюю границу

Почему он предоставляет нижнюю границу вместо верхней границы общего времени выполнения всех работ?

Я думаю, что могу неправильно понять критический путь ??


graph algorithm clrs
person fuiiii    schedule 06.12.2015    source источник
comment
Потому что предполагается, что все задачи выполняются в оптимальном порядке с максимальным распараллеливанием. Если ослабить любое из этих предположений, общее время выполнения всех работ увеличится.   -  person Pieter Geerkens    schedule 06.12.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person mcdowella    schedule 06.12.2015