トミナガ　ヒロブミ   TOMINAGA HIROBUMI   富永　浩文    所属   明治大学  総合数理学部    職種   助教
言語種別	日本語
発行・発表の年月	2018/08
形態種別	学術雑誌
査読	査読あり
標題	タスクスケジューリング問題における探索ノード数削減によるPDF/IHS法の高速化
執筆形態	共著(筆頭者以外)
掲載誌名	情報処理学会論文誌コンピューティングシステム（ACS）
掲載区分	国内
巻・号・頁	11(2),17-26頁
著者・共著者	松瀨, 弘明, 中村, あすか, 富永, 浩文, 前川, 仁孝
概要	本論文では，タスクスケジューリング問題を高速に解くために，レディ状態を削減したPDF/IHS（Parallelized Depth First/Implicit Heuristic Search）法の探索ノード数を削減するアルゴリズムを提案する．PDF/IHS法は，階層的挟み撃ち探索を用いた並列探索アルゴリズムであり，実行可能なタスクをPE（Processing Element）に割り当てる組合せをすべて列挙することで分枝限定法の探索木を生成する．このため，問題規模が大きくなるほど探索ノード数が膨大になり，探索ノード数の削減が必要となる．PDF/IHS法の探索ノード数を削減するために，不必要なレディ状態を割当てた部分問題を枝刈りする手法が提案されている．不必要なレディ状態を割り当てた部分問題を枝刈りする法は，割り当てたタスク情報のみを用いて枝刈りするため，探索する必要のない部分問題のすべてを枝刈りできない．そこで本論文では，探索する必要のないすべての部分問題を枝刈りするために，探索済みノード情報を利用する．評価の結果，探索済みノードを利用した枝刈りをすることで，スレッド数2のとき相乗平均約1.39倍高速に求解できることを確認した．
ISSN	18827829
NAID	170000149667