| 大会名称 |
|---|
| 2010年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2010 |
| 発行日 |
| 2010/8/20 |
| セッション番号 |
| 7A |
| セッション名 |
| アルゴリズム・コンピュテーション(3) |
| 講演日 |
| 2010/09/09 |
| 講演場所(会議室等) |
| A会場（総合学習プラザ1F 第5講義室） |
| 講演番号 |
| A-029 |
| タイトル |
| 通信を考慮したタスクスケジューリング問題の探索解法のための高速化手法 |
| 著者名 |
| 宇都宮 雅彦, 塩田 隆二, 甲斐 宗徳, |
| キーワード |
| タスクスケジューリング, 並列処理, 組み合わせ最適化問題, ヒューリスティックアルゴリズム, 並列探索, 通信オーバーヘッド最小化 |
| 抄録 |
|
通信を考慮したタスクスケジューリング問題は強NP困難な組み合わせ最適化問題である。 この問題の探索を、実処理の実行時間最小化を目指して行うとき、「部分タスク集合をグループ化することによって見かけ上のタスク数を減らすこと」、また「各タスクから処理全体が終了するまでに最低でも必要となる時間を下限値として探索空間の枝刈りを行う際の、下限値の精度を向上させること」によって、探索の高速化が可能である。 本研究では、内部の並列性を考慮して行うタスクのグループ化と、通信を考慮した下限値の導出法の2つのヒューリスティックアルゴリズムを提案し、その評価結果について報告する。 |
| 本文pdf |
| PDF download (553.8KB) |