algorithm - クリティカル パスの重みによって、すべてのジョブを実行する合計時間の下限が決まるのはなぜですか?

Question

Introduction to Algorithms P657、第 3 版には、次のように記載されています。

クリティカル パスは、一連のジョブを実行するための最長時間に対応する、dag を通る最長パスです。したがって、クリティカル パスの重みによって、すべてのジョブを実行する合計時間の下限が決まります。

最初の文はわかりました。しかし、2番目の文では、

クリティカル パスは下限を提供します

すべてのジョブを実行する合計時間の上限ではなく下限を提供するのはなぜですか?

クリティカルパスを誤解しているのではないかと思います??

Answer 1

パス内の前のジョブを完了する前に、クリティカル パス内のジョブを開始することはできません。したがって、法的なスケジュールでは、クリティカル パス上のすべてのジョブを実行するために重みの合計が必要になります。したがって、クリティカル パスは、すべてのジョブを実行する時間の下限です。

(現在開始可能なすべてのジョブを同時に処理するのに十分なリソースが常にある場合、最長のクリティカル パスは、すべてのジョブを完了する時間でもあります)。