通信を考慮したタスクスケジューリング問題の探索解法

カテゴリ: 部門大会

論文No: GS19-4

グループ名: 【C】平成17年電気学会電子・情報・システム部門大会講演論文集

発行日: 2005/09/06

タイトル(英語): An Algorithm Based Branch-and-Bound Method for Task Scheduling Problems taking account of Communication Overhead

著者名: 尾高 輝(成蹊大学),綾部 翼(成蹊大学),津田 耕治(成蹊大学),甲斐 宗徳(成蹊大学)

著者名(英語): Akira Odaka(Seikei University),Tsubasa Ayabe(Seikei University),Kouji Tsuda(Seikei University),Munenori Kai(Seikei University)

キーワード: タスクスケジューリング|並列処理|最適化問題|分枝限定法|ヒューリスティックアルゴリズム|Task scheduling|Parallel Processing|Optimizing problem|Branch and Bound method|Heuristic algorithm

要約(日本語): 通信を考慮したタスクスケジューリング問題は、通信を考慮しない場合でさえ強NP困難である問題をさらに上回る、求解困難な問題である。本発表では、最適解を求めるために、アイドルタスクを必要な時だけ考慮するアルゴリズムと、通信の組合せによる重複解を探索から省くアルゴリズムを提案する。また、これらのアルゴリズムを組み合わせて用いることにより、通常の深さ優先の全探索方式に比べ、大幅に探索空間を削減して、より短時間で最適スケジュールを求めることが可能となったので、その評価結果について報告する。

PDFファイルサイズ: 4,027 Kバイト