7 つのタスク t1-t7 があり、各タスクには実行時間が関連付けられています (t1 は 1 時間単位、t2 は 5 など)。
t1 と t2 の間の通信コストは、同じプロセッサ内で実行する場合に支払う必要はありません。p1 で t1 を実行し、p2 で t2 を実行する場合、p1 から p2 にデータを転送するには 5 時間単位が必要です。(5 はエッジ t1-t2 の重み)
右の図に示すように、通信 c(1,2) と c(3,4) は同時に行うことができ、両方とも 5 時間単位の終わりに終了します。
makespan は、7 つのタスクすべてを完了するのにかかる時間です。必要なだけ多くのプロセッサがある場合、最小の makespan (または少なくとも最小のものに近い) でスケジューリング結果を見つけるためにどのアルゴリズムを使用できますか?
右の画像の結果は最適化されていない可能性があることに注意してください。
