問題の説明：はグラフの問題で並列処理プログラミングを適用する方法は？
n tasksがあり、そしてAが終了される前にAがBに依存している場合を意味し、これらのタスク、one might be dependent on the others、で、その後、Bが終了しなければなりません。
1.できるだけ早くこれらのタスクを完了する方法を見つけましたか？
2.if take parallelism into account、どのようにこれらのタスクを完了するためのプログラムを設計するのですか？
質問：
どうやら、最初の質問への答えは、トポロジカルソートこれらのタスクは、その順序でそれらを終えます。
しかし、並列性を考慮すると、どのように仕事をするのですか？
私の答えは、これらのタスクトポロジカル・ソート第一号だった、そして独立しているこれらのタスクを選択し、それらを最初に終え、その後、残りの部分では、これらの独立したものを選んで、仕上げ...
は、私は右ですか？
トポロジカルな並べ替えアルゴリズムは、さまざまな結果の順序を与える場合があるため、最初のいくつかの要素を取り、それらを独立したものとみなすことはできません。
トポロジカルソートの代わりに、着信依存エッジの数でタスクを並べ替えることをお勧めします。たとえば、A - > B、A - > C、B - > C、D - > Cのグラフの場合、A [0]、D [0]、B [1] 、C [3]ここで、[i]は入力エッジ数である。
トポロジカルソートでは、A、B、D、Cを得ることもできます。その場合、AとDを並行して実行できることがわかりにくいでしょう。
タスクが完全に処理された後、残りのタスク、特に、完了したタスクに依存していたタスクを更新する必要があることに注意してください。しかし、タスクに入る依存関係の数が比較的少ない数（たとえば数百）に制限されている場合、radix/bucket-sortのようなものに簡単に依存して、ソート構造を一定の時間内に更新し続けることができます。
このアプローチでは、1つの並列タスクが完了すると、新しいタスクを簡単に開始することもできます。依存関係の数を更新して、依存関係が0になるすべてのタスクを開始するだけです。
この方法では、同時に依存関係のないすべてのタスクを処理するのに十分な処理能力があることを前提としています。リソースが限られており、処理時間の点で最適なソリューションを気にかけているなら、問題はNP困難になります（既に述べたように）。
元の質問に答えるには：はい、基本的には正しいですが、これらの独立したタスクを効率的に判断する方法は説明できませんでした（上記の例を参照）。
ありがとうフランク、私は掘り下げようとしています。 – Alcott
Critical Path Methodをご覧ください。これはproject managementです。それは基本的にあなたが必要としていることを行います。従属性と持続性を備えたタスクがあれば、それはどれくらいの時間がかかり、各タスクをいつ活性化するかが決まります。
（*）この手法は、最適解を得るために無限の数のリソースを想定しています。限られたリソースの場合、GPRW [現在+作業時間後]またはMSLK [最小total slack時間]のような欲張りアルゴリズムのヒューリスティックがあります。
（*）各タスクの所要時間を知ることが必要です。
依存するタスクを実行する前に、各依存関係を並列で繰り返し実行することはどうでしょうか？各作業が一度だけ実行されることを確認するにはいくつかの帳簿が必要ですが、それ以外の場合は単純で効率的です。 –