4H-06
タスクスケジューリング問題におけるDF/IHS法のハッシュテーブルを用いた探索ノード数削減
○松瀬弘明，中村あすか，富永浩文，前川仁孝（千葉工大）
本研究では，タスクスケジューリング問題におけるDF/IHS(Depth First/Implicit Heuristic Seach)法を高速化するために，ハッシュテーブルを用いて探索ノード数を削減する手法を提案する．
タスクスケジューリング問題は，マルチプロセッサシステム環境でタスクをプロセッサに割り当てる際に実行時間が最小となるようなスケジュールを求める問題である．
DF/IHS法で生成する探索木は，実行可能なスケジュールを列挙するため，探索済みノードと同じタスクを割り当てたスケジュール長の長い部分問題を生成する場合がある．
このような部分問題は，探索する必要がない．このため，提案手法では探索済みの部分問題情報を格納したハッシュテーブルを用いて枝刈りする．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会