トミナガ　ヒロブミ   TOMINAGA HIROBUMI   富永　浩文    所属   明治大学  総合数理学部    職種   助教
言語種別	日本語
発行・発表の年月	2017/03
形態種別	学術雑誌
査読	査読あり
標題	タスクスケジューリング問題におけるレディ状態の割当て削減によるPDF/IHSの高速化
執筆形態	共著(筆頭者以外)
掲載誌名	情報処理学会論文誌
掲載区分	国内
巻・号・頁	58(3),654-662頁
著者・共著者	中村, あすか, 富永, 浩文, 前川, 仁孝
概要	本論文は，タスクスケジューリング問題の厳密解法であるPDF/IHS（Parallel Depth First/Implicit Heuristic Search）の探索ノード数を削減するアルゴリズムを提案する．PDF/IHSは，階層的挟み撃ち探索を用いた分枝限定法の並列探索アルゴリズムであり，大規模なタスクスケジューリング問題を高速に解くためには探索ノード数の削減が必要となる．PDF/IHSの分枝操作は，スケジュールが未確定となる時刻に実行可能なタスクの処理またはレディ状態を割り当てる全組合せを部分問題として生成する．このため，不必要なレディ状態が割り当てられた部分問題が生成されることがある．そこで，本論文では，PDF/IHSの探索ノード数を削減するために，レディ状態を割り当てる部分問題のうち，最適解が得られないことが保障できる部分問題を枝刈りする．提案するアルゴリズムは，分枝操作で割り当てられたタスクの処理時間の情報から探索する必要のない部分問題を判定する．評価の結果，提案手法は，PDF/IHSに対して最大約96倍高速に求解できることを確認した．
ISSN	18827764
NAID	170000148472